The dimension of the feasible region of pattern densities

Frederik Garbe, Daniel Kral, Alexandru Malekshahian, Raul Penaguiao

Published 2023-09-18Version 1

A classical result of Erd\H{o}s, Lov\'asz 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. Exploiting an interplay between algebra and combinatorics concerning Lyndon words, we determine the dimension of the feasible region of densities of permutation patterns of size at most k by proving that it is equal to the number of non-trivial Lyndon permutations of size at most k.