Abstract 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 "Equation missing" is a tangram with cut number one, while the word "Equation missing" 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>W</mml:mi> <mml:mo>=</mml:mo> <mml:mi>A</mml:mi> <mml:mi>T</mml:mi> <mml:mi>B</mml:mi> </mml:mrow> </mml:math> , for any words A and B (possibly empty). The famous 1906 theorem of Thue asserts that there exist arbitrarily long words avoiding squares over an alphabet with just three letters. Given a fixed number $$k\geqslant 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , which easily implies $$t(2)=3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . Curiously, these are currently the only known exact values of this function. In our main result we prove that $$t(k)=\Theta (\log _2k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . The proof uses entropy compression argument and Zimin words . Using a different method we prove that $$t(k)\leqslant k+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> <mml:mo>⩽</mml:mo> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> for all $$k\geqslant 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> , 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.

Michał Dȩbski

Jarosław Grytczuk

Bartłomiej Pawlik

Jakub Przybyło

Małgorzata Śleszyńska-Nowak

Annals of Combinatorics

ANNALS OF COMBINATORICS 发表了对组合学的杰出贡献，特别关注代数和分析组合学，以及图和拟阵理论领域。将特别关注由我们的编辑委员会代表的社区当前感兴趣的新发展和主题。ANNALS OF COMBINATORICS 的范围包括以下三个轨道：代数组合：枚举组合、对称函数、舒伯特微积分 / 组合 HOPF代数、簇代数、李代数、根系统、COXETER 群 / 离散几何、热带几何 / 离散动力系统 / POSETS 和格分析和算法组合：计数序列的渐近分析 / 双射组合 / 单变量和多变量奇点分析 / 组合和微分方程/ 通过基本使用计算机解决组合难题 / 评估计数序列或组合常数的高级方法 / 组合序列的复杂性和可判定性方面 / 算法分析的组合方面图和拟阵：结构图 T理论、图辅修、图稀疏性、分解和着色 / 平面图和拓扑图论、图的几何表示 / 有向图、偏序集 / 度量图论 / 谱和代数图论 / 随机图、极值图论 / 拟阵、定向拟阵, 拟阵未成年人 / 算法方法

The Annals of Combinatorics publishes outstanding contributions to the field of combinatorics, with a particular focus on algebraic and analytic combinatorics, as well as graph theory and matroid theory. The journal emphasizes new developments and topics of current interest to the community represented by our editorial board. The scope of the journal includes three main tracks: 1. Algebraic Combinatorics: covering enumerative combinatorics, symmetric functions, Schubert calculus, combinatorial Hopf algebras, cluster algebras, Lie algebras, root systems, Coxeter groups, discrete geometry, tropical geometry, discrete dynamical systems, posets, and lattice theory; 2. Algorithmic Combinatorics: involving asymptotic analysis of counting sequences, bijective combinatorics, univariate and multivariate singularity analysis, combinatorial and differential equations, fundamental methods for solving combinatorial problems using computers, advanced methods for evaluating counting sequences or combinatorial constants, complexity and decidability of combinatorial sequences, and aspects of combinatorial analysis in algorithms; 3. Graph Theory and Matroids: including structural graph theory, auxiliary graph theory, graph sparsity, decomposition and coloring, planar and topological graph theory, geometric representations of graphs, directed graphs, posets, metric graph theory, spectral and algebraic graph theory, random graphs, extremal graph theory, matroids, directed matroids and minors, as well as algorithmic methods.

《Annals of Combinatorics》发表了对组合学领域的杰出贡献，特别关注代数和分析组合学，以及图论和拟阵理论。期刊将特别关注由编辑委员会代表的社区当前感兴趣的新发展和主题。期刊的范围包括以下三个主要方向：1. 代数组合：涉及枚举组合、对称函数、舒伯特微积分、组合HOPF代数、簇代数、李代数、根系统、COXETER群、离散几何、热带几何、离散动力系统、偏序集和格分析等；2. 算法组合：包括计数序列的渐近分析、双射组合、单变量和多变量奇点分析、组合和微分方程、利用计算机解决组合难题的基本方法、评估计数序列或组合常数的高级方法、组合序列的复杂性和可判定性，以及算法分析的组合方面；3. 图论和拟阵：涉及结构图理论、图的辅助理论、图的稀疏性、分解和着色、平面图和拓扑图论、图的几何表示、有向图、偏序集、度量图论、谱和代数图论、随机图、极值图论、拟阵、定向拟阵及其未成年人，以及算法方法。

Category	Quartile
数学	4
数学, 应用数学	4

Words Avoiding Tangrams

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
MATHEMATICS, APPLIED	4