On long words avoiding Zimin patterns (Q2321925)

A word \(w\) is said to contain the pattern \(P\) if there is a way to substitute a nonempty word for each letter in \(P\) so that the resulting word is a subword of \(w\). The pattern \(P\) is called unavoidable if any sufficiently long word over a fixed alphabet contains \(P\). It is known that \(P\) is unavoidable if and only if it is contained in one of the so-called Zimin words \(Z_n\), where \(Z_1=x_1\) and \(Z_n=Z_{n-1}x_nZ_{n-1}\). Let \(f(n,k)\) be the least integer such that any word of length \(f(n,k)\) over an alphabet of size \(k\) contains \(Z_n\). It is proved that \(f(n,2n-1)>\mathrm{Tower}(n-1,2)\) and \(f(n,2)>\mathrm{Tower}(n-3,2)\). Also, some new similar estimates in the abelian version of the problem are proved.