Bukh–Borisov deletion-distance conjecture for binary words

For a binary word $W$, let $g(W)$ be the minimum number of letters that must be deleted from $W$ to obtain a shuffle square, and let $g(n)$ be the maximum of $g(W)$ over binary words of length $n$. A shuffle square is a word containing two disjoint equal subsequences whose total length is the word's length.

Bukh–Borisov deletion-distance conjecture. There is a constant $c$ such that, for every $n$,

$$g(n)\geqslant c\sqrt n,$$

that is, there exists a binary word of length $n$ with largest twins leaving out at least $c\sqrt n$ elements.

Known bounds include $g(n)=o(n)$ and $g(n)=\Omega(n^{1/3})$. The conjecture predicts the stronger lower bound of order $\sqrt n$.