25 problems

Grytczuk–Kordulewski–Niewiadomski conjecture. There are no extremal words over an alphabet of size $4$.

A bicrucial permutation is a square-free permutation such that prepending or appending any single element creates a square. The existence conjecture. There exist arbitrarily long b…

Generalized nonchalant-word infinitude conjecture. If $\ae(N_1)>2$ for the starting word $N_1$ of the nonchalant algorithm, then the respective sequence of nonchalant words is infi…

Let $p$ and $q$ be relatively prime integers satisfying … An infinite ternary word is square-free modulo $p$ and $q$ when its subsequences with indices in each residue class modulo…

Let $p$ and $q$ be relatively prime positive integers. An infinite ternary word is square-free modulo $p$ and $q$ when its subsequences with indices in each residue class modulo…

Let $p$ and $q$ be relatively prime positive integers. An infinite ternary word is square-free modulo $p$ and $q$ when its subsequences with indices in each residue class modulo…

Square-free word conjecture. Given a sequence of alphabets $(\mathcal{A}_i)_{i\ge1}$ with $|\mathcal{A}_i|\ge3$ for all $i$, there exists an infinite square-free word that respects…

Let $L(w)$ denote the lexicographically least infinite word on $\mathbb{N}$ beginning with $w$ whose only square factors are contained in the prefix $w$. The conjecture for extensi…

The explicit limit conjecture for $L(2)$.

Let $L(w)$ denote the lexicographically least infinite word on $\mathbb{N}$ beginning with $w$ whose only square factors are contained in the prefix $w$. Let $L(\varepsilon)$ be th…

Five-letter complete bifurcate-tree conjecture. There exists a complete bifurcate tree over an alphabet of size $5$.

Quaternary bifurcate-chain conjecture. There exists an infinite sequence of quaternary bifurcate words $W_1,W_2,\ldots$ such that $W_{i+1}$ is a single-letter extension of $W_i$ fo…

List steady-word conjecture. There exists a steady word $W=w_1w_2\cdots w_n$ such that $w_i\in\mathcal{A}_i$ for every $i=1,2,\ldots,n$.

Lower-bound conjecture. Both bounds can be lowered to $4$, and this is best possible.

An extremal square-free word is a square-free word such that inserting any letter in any position introduces a square. The nonexistence conjecture. There are no extremal square-fre…

An extremal square-free permutation is a square-free permutation for which inserting any letter in any position introduces a square. The extremal-permutation conjecture. There exis…

Let $(\ell_i)_{i\ge1}$ be a sequence of alphabets, each of size $3$. An infinite word $w$ is square-free if it contains no factor of the form $uu$ for a nonempty finite word $u$. G…

Four-letter square-free extension conjecture. Every square-free word over a $4$-letter alphabet can be extended to a square-free word.

Grytczuk-type conjecture. There are no extremal square-free words over $\Sigma$.

A square-free word is a word containing no factor of the form $uu$ with $u$ nonempty, and an extremal square-free word is a square-free word that cannot be extended by inserting a…

Let $\Sigma_2=\{0,1\}$, and let $s_2(n)$ denote the number of length-$n$ words over $\Sigma_2$ having no square prefix. Here $f(n)\sim g(n)$ means that $f(n)/g(n)\to 1$ as…

Let $\Sigma$ be an ordered alphabet with $|\Sigma|\ge 3$. A word $w\in\Sigma^*$ is square-free-$M$-unambiguous when it is not $M$-equivalent to any other distinct square-free word.…

Petrova–Shur conjecture. In the tree $T$, the size of any minimal subtree of index $n$ is $O(\operatorname{log} n)$.

Let $r(n)$ be the maximum length of a rich square-free word over an alphabet of size $n$, and let $w_n$ be the recursively constructed rich square-free word over an alphabet of siz…

Let $r(n)$ be the maximum length of a rich square-free word over an alphabet of size $n$, and let $w_n$ be the recursively constructed rich square-free word described in the articl…