The dimension of the feasible region of pattern densities
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
09 January 2025
|
| In: |
Mathematical proceedings of the Cambridge Philosophical Society
Year: 2025, Volume: 178, Issue: 1, Pages: 1-14 |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004124000380 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/S0305004124000380 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/dimension-of-the-feasible-region-of-pattern-densities/8310529D821B227293D30D36184F5024 
|
| Author Notes: | Frederik Garbe, Daniel Král’, Alexandru Malekshahian and Raul Penaguiao |
| Summary: | 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=3k=3k=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. |
|---|---|
| Item Description: | Gesehen am 22.10.2025 |
| Physical Description: | Online Resource |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004124000380 |