2024/07/04 by Michał Dębski, Dębski, Michał, Jarosław Grytczuk +7
Engineering · #68R15 #Architecture and Computational Design #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2407.03819
openalex publication_date 2024/07/04 · openalex created_date 2024/07/09 · openalex updated_date 2026/07/28
A tangram is a word in which every letter occurs an even number of times. Such word can be cut into parts that can be arranged into two identical words. The minimum number of cuts needed is called the cut number of a tangram. For example, the word \mathtt\colorred0102\colorblue0102 is a tangram with cut number one, while the word \mathtt\colorred01\colorblue01023\colorred023 is a tangram with cut number two. Clearly, tangrams with cut number one coincide with the well known family of words, known as squares, having the form UU for some nonempty word U. A word W avoids a word T if it is not possible to write W=ATB, for any words A and B (possibly empty). The famous 1906 theorem of Thue asserts that there exist arbitrarily long words avoiding squares over alphabet with just three letters. Given a fixed number k\geqslant 1, how many letters are needed to avoid tangrams with the cut number at most k? Let t(k) denote the minimum size of an alphabet needed for that purpose. By Thue's result we have t(1)=3, which easily implies t(2)=3. Curiously, these are currently the only known exact values of this function. In our main result we prove that t(k)=Θ(log2k). The proof uses entropy compression argument and Zimin words. By using a different method we prove that t(k)\leqslant k+1 for all k\geqslant 4, which gives more exact estimates for small values of k. The proof makes use of Dejean words and a curious property of Gauss words, which is perhaps of independent interest.