The asymptotic maximum-appearance conjecture for distinct-letter words in two-dimensional grids

Let ww' be a word of length k2k\ge 2 whose letters are all distinct, and let f(w,n,2)f(w',n,2) denote the maximum number of copies of ww' appearing in an n×nn\times n grid. Distinct-letter word conjecture.

f(w,n,2)3k1n2.f(w',n,2)\sim \frac{3}{k-1}n^2.

The paper notes that the known bounds place f(w,n,2)f(w',n,2) roughly between 3k1n2\frac{3}{k-1}n^2 and 4k1n2\frac{4}{k-1}n^2, and suggests that the lower bound is closer to the truth; the asserted asymptotic equivalence remains open.

Sources & referencesView supporting material

Primary source

Gregory Patchell and Sam Spiro, “The Maximum Number of Appearances of a Word in a Grid”, arXiv:2207.11273 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.