The dimension of the feasible region of pattern densities
| Autoři | |
|---|---|
| Rok publikování | 2023 |
| Druh | Článek ve sborníku |
| Konference | European Conference on Combinatorics, Graph Theory and Applications |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://journals.muni.cz/eurocomb/article/view/35599 |
| Doi | http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-065 |
| Klíčová slova | permutations; permutation limits; patterns |
| Popis | 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. |
| Související projekty: |