2025/11/24 by Zachary Halberstam, Carl Schildkraut, Halberstam, Zachary +1
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2511.19678
Given a word w, what is the maximum possible number of appearances of w reading contiguously along any of the directions in \-1, 0, 1\d ∖ \0\ in a large d-dimensional grid (as in a word search)? Patchell and Spiro first posed a version of this question, which Alon and Kravitz completely answered for a large class of "well-behaved" words, including those with no repeated letters. We study the general case, which exhibits greater variety and is often more complicated (even for d=1). We also discuss some connections to other problems in combinatorics, including the storied n-queens problem.