28 problems

A finite word is closed-rich when it contains the maximal number of distinct closed factors among words of the same length; the exponent of a word is its maximal repetition exponen…

Let $\mathcal{TC}_{n,k}$ be the class of tree-child networks with $n$ leaves and $k$ reticulation nodes, and let $\mathcal{C}_{n-1,k}$ be the class of words over the alphabet…

A word $u$ has maximum letter $m$ and is $m$-packed if it contains at least one copy of every integer in $[m]=\{1,\ldots,m\}$. A word $u$ is $m$-stable when its centralizers satisf…

Large-alphabet shuffle-square growth conjecture. As a function of $k\in\mathbb{N}$,

Binary shuffle-square density conjecture. As $n\to\infty$, asymptotically half of all binary words of length $2n$ are shuffle squares; equivalently,

Expected-number conjecture. The expected number of letters drawn is given by these two equivalent expressions.

The generating-function conjecture. The generating function $f(z)$ is given by the displayed expression above.

Let $w_m\leq w_M$ be finite words, and let $\mathcal{S}\!ub_{w_m}(w_M)$ denote the set of words between $w_m$ and $w_M$ under the embedding order. The Insertion Chain Complex of th…

Let $A$ be the alphabet, let $n$ be a positive integer, and let $c_x(w)$ denote the number of occurrences of the character $x$ in a word $w\in A^n$. Define the signature of $w$ by…

Let $C_k^{(=2)}(n)$ be the number of occurrences of the letter $2$ in the relevant generalized Hofstadter word $x_k$ associated with $n$. Letter-2 count monotonicity conjecture. Fo…

Positive-density conjecture. The limit

Let $w$ be a word of length at least $2$. A subword is most frequent if it maximizes the number of occurrences in $w$. Short-subword conjecture. At least one most frequent subword…

For $k \geq 2$, let $\min S_{\mathrm{sw}}^{(k)}(n)$ denote the minimal subword entropy among words of length $n$. Eventual monotonicity conjecture. There is a value $N$ such that t…

Let $w$ be a word, and write $w^m$ for its $m$-fold concatenation. A subword is most frequent if it maximizes the number of occurrences in $w^m$. Periodic-structure conjecture. The…

Let $w$ be a binary word of length $n$ achieving the minimal subword entropy. Uniqueness conjecture. There are only finitely many values of $n$ for which such a word $w$ has severa…

For $k \geq 2$, let $w$ be a binary word of length $n \geq 1$ achieving the minimal subword entropy $\min S_{\mathrm{sw}}^{(k)}(n)$. A run is a maximal consecutive block of equal l…

Let $L_2$ denote the asymptotic binary subword-entropy constant, and let $\log_2$ be the logarithm to base $2$. Strict lower-bound conjecture. … This conjecture is supported by exh…

For each length, consider the set of even binary words and the subset consisting of shuffle squares. The asymptotic binary shuffle-square conjecture. As the length tends to infinit…

A binary word uses an alphabet of two letters, and an even word is a word in which every letter occurs an even number of times. A word is a cyclic shuffle square if it splits into…

For a binary even word $W$ of length $2n$, let $s(W)$ be the number of circular shifts of $W$ that are shuffle squares. Let $s_{2n}$ be the minimum of $s(W)$ over all binary even w…

Fix an alphabet of size $k$. Let $E_n$ be the set of all even $k$-ary words of length $n$, and let $S_n$ be the set of all permutations of $[n]$. Define $m_k(n)$ to be the minimum…

An even word is a word in which every letter occurs an even number of times. A ternary word uses an alphabet of three letters. A dihedral shuffle square is a word that can be split…

Let $P$ be a prime double square tile, and let $w$ be its boundary word over a four-letter alphabet $\Sigma$. A prime double square boundary-word conjecture. For every letter…

Let $n\geqslant 2$ and let $(\alpha_2,\ldots,\alpha_n)$ be an $(n-1)$-tuple of nonnegative integers. Let $\Phi$ be the map from words to multisets of conjugacy classes of primitive…

An upword for $\{0,1\}^n$ is a word containing every binary word of length $n$ as a consecutive factor, with the symbol $\mathord{\diamond}$ permitted as a wildcard according to th…