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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
09 January 2025
|
| In: |
Mathematical proceedings of the Cambridge Philosophical Society
Year: 2025, Jahrgang: 178, Heft: 1, Pages: 1-14 |
| ISSN: | 1469-8064 |
| DOI: | 10.1017/S0305004124000380 |
| Online-Zugang: | 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 
|
| Verfasserangaben: | Frederik Garbe, Daniel Král’, Alexandru Malekshahian and Raul Penaguiao |
MARC
| LEADER | 00000naa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 193911893X | ||
| 003 | DE-627 | ||
| 005 | 20251022150150.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 251022s2025 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1017/S0305004124000380 |2 doi | |
| 035 | |a (DE-627)193911893X | ||
| 035 | |a (DE-599)KXP193911893X | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Garbe, Frederik |e VerfasserIn |0 (DE-588)1348929871 |0 (DE-627)1909336661 |4 aut | |
| 245 | 1 | 4 | |a The dimension of the feasible region of pattern densities |c Frederik Garbe, Daniel Král’, Alexandru Malekshahian and Raul Penaguiao |
| 264 | 1 | |c 09 January 2025 | |
| 300 | |a 14 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 22.10.2025 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 05A05 | |
| 650 | 4 | |a 05D99 | |
| 650 | 4 | |a 28A12 | |
| 700 | 1 | |a Král’, Daniel |e VerfasserIn |4 aut | |
| 700 | 1 | |a Malekshahian, Alexandru |e VerfasserIn |4 aut | |
| 700 | 1 | |a Penaguião, Raúl |d 1993- |e VerfasserIn |0 (DE-588)122231083X |0 (DE-627)1741398916 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Mathematical proceedings of the Cambridge Philosophical Society |d Cambridge [u.a.] : Cambridge Univ. Press, 1975 |g 178(2025), 1, Seite 1-14 |h Online-Ressource |w (DE-627)300897928 |w (DE-600)1483586-1 |w (DE-576)081894880 |x 1469-8064 |7 nnas |a The dimension of the feasible region of pattern densities |
| 773 | 1 | 8 | |g volume:178 |g year:2025 |g number:1 |g pages:1-14 |g extent:14 |a The dimension of the feasible region of pattern densities |
| 856 | 4 | 0 | |u https://doi.org/10.1017/S0305004124000380 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/dimension-of-the-feasible-region-of-pattern-densities/8310529D821B227293D30D36184F5024 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20251022 | ||
| 993 | |a Article | ||
| 994 | |a 2025 | ||
| 998 | |g 1348929871 |a Garbe, Frederik |m 1348929871:Garbe, Frederik |d 110000 |d 110300 |e 110000PG1348929871 |e 110300PG1348929871 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN193911893X |e 4790790037 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"person":[{"roleDisplay":"VerfasserIn","display":"Garbe, Frederik","role":"aut","family":"Garbe","given":"Frederik"},{"role":"aut","display":"Král’, Daniel","roleDisplay":"VerfasserIn","given":"Daniel","family":"Král’"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Malekshahian, Alexandru","given":"Alexandru","family":"Malekshahian"},{"role":"aut","display":"Penaguião, Raúl","roleDisplay":"VerfasserIn","given":"Raúl","family":"Penaguião"}],"title":[{"title_sort":"dimension of the feasible region of pattern densities","title":"The dimension of the feasible region of pattern densities"}],"note":["Gesehen am 22.10.2025"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"recId":"193911893X","language":["eng"],"name":{"displayForm":["Frederik Garbe, Daniel Král’, Alexandru Malekshahian and Raul Penaguiao"]},"origin":[{"dateIssuedKey":"2025","dateIssuedDisp":"09 January 2025"}],"id":{"doi":["10.1017/S0305004124000380"],"eki":["193911893X"]},"physDesc":[{"extent":"14 S."}],"relHost":[{"title":[{"title_sort":"Mathematical proceedings of the Cambridge Philosophical Society","title":"Mathematical proceedings of the Cambridge Philosophical Society"}],"note":["Gesehen am 08.09.25"],"type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"The dimension of the feasible region of pattern densitiesMathematical proceedings of the Cambridge Philosophical Society","recId":"300897928","language":["eng"],"corporate":[{"roleDisplay":"Herausgebendes Organ","display":"Cambridge Philosophical Society","role":"isb"}],"pubHistory":["Volume 77, issue 1 (January 1975)-"],"part":{"year":"2025","pages":"1-14","issue":"1","text":"178(2025), 1, Seite 1-14","volume":"178","extent":"14"},"origin":[{"publisherPlace":"Cambridge [u.a.]","dateIssuedKey":"1975","publisher":"Cambridge Univ. Press","dateIssuedDisp":"1975-"}],"id":{"issn":["1469-8064"],"eki":["300897928"],"zdb":["1483586-1"]},"physDesc":[{"extent":"Online-Ressource"}]}]} | ||
| SRT | |a GARBEFREDEDIMENSIONO0920 | ||