The dimension of the feasible region of pattern densities
| Authors | |
|---|---|
| Year of publication | 2023 |
| Type | Article in Proceedings |
| Conference | European Conference on Combinatorics, Graph Theory and Applications |
| MU Faculty or unit | |
| Citation | |
| Web | https://journals.muni.cz/eurocomb/article/view/35599 |
| Doi | http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065 |
| Keywords | permutations; permutation limits; patterns |
| Description | A classical result of Erdős, Lovász and Spencer from the late 1970s asserts that the dimension of the feasible region of homomorphic densities of graphs with at most k vertices in large graphs is equal to the number of connected graphs with at most k vertices. Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of k-patterns is at least the number of non-trivial indecomposable permutations of size at most k. We identify a larger set of permutations, which are called Lyndon permutations, whose pattern densities are independent, and show that the dimension of the feasible region of densities of k-patterns is equal to the number of non-trivial Lyndon permutations of size at most k. |
| Related projects: |