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...
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Article (Journal) |
| Lingua: | inglese |
| Pubblicazione: |
09 January 2025
|
| In: |
Mathematical proceedings of the Cambridge Philosophical Society
Year: 2025, Volume: 178, Fascicolo: 1, Pages: 1-14 |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004124000380 |
| Accesso online: | 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 
|
| Note sull'autore: | Frederik Garbe, Daniel Král’, Alexandru Malekshahian and Raul Penaguiao |
| Riassunto: | 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. |
|---|---|
| Descrizione del documento: | Gesehen am 22.10.2025 |
| Descrizione fisica: | Online Resource |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004124000380 |