The dimension of the feasible region of pattern densities

Abstract

A classical result of Erdős, Lovász and Spencer from the late 1970s asserts that the dimension of the feasible region of densities of graphs with at most k vertices in large graphs is equal to the number of non-trivial connected graphs with at most k vertices. Indecomposable permutations play the role of connected graphs in the realm of permutations, and Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of permutation patterns of size at most k is at least the number of non-trivial indecomposable permutations of size at most k. However, this lower bound is not tight already for k=3. We prove that the dimension of the feasible region of densities of permutation patterns of size at most k is equal to the number of non-trivial Lyndon permutations of size at most k. The proof exploits an interplay between algebra and combinatorics inherent to the study of Lyndon words.

arXiv commentMinor update to references. Final version

References in corpus (13)

• Graph limits and exchangeable random graphs
• On the Number of Pentagons in Triangle-Free Graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Non-three-colorable common graphs exist
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Minimum number of monotone subsequences of length 4 in permutations
• A new lower bound based on Gromov's method of selecting heavily covered points
• Counting flags in triangle-free digraphs
• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Improving bounds on packing densities of 4-point permutations
• Six Permutation Patterns Force Quasirandomness
• On pattern-avoiding permutons
• The dimension of the region of feasible tournament profiles