The inducibility of 6-vertex graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914619569733632 |
|---|---|
| author | Bodnár, Levente Gao, Jun León, Jared Liu, Xizhi Pikhurko, Oleg Sun, Shumin |
| author_facet | Bodnár, Levente Gao, Jun León, Jared Liu, Xizhi Pikhurko, Oleg Sun, Shumin |
| contents | The inducibility constant $λ_{F}$ of a graph $F$ is the asymptotically maximum induced density of $F$ in a growing sequence of graphs. This paper systematically investigates the case when $F$ has 6 vertices (and there are 78 cases to consider up to isomorphism and complementation). We show that flag algebras can compute the sharp upper bound on $λ_F$ in 36 cases of which, as far as the authors know, 30 are new results. In each of the solved cases, we also prove results about the structure of large (almost) extremal graphs. In particular, we establish perfect stability in all 32 cases when the extremal construction has no quasirandom parts. We also present conjectures about the value of $λ_{F}$ for 12 further cases (where the upper and lower bounds are very close to each other). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The inducibility of 6-vertex graphs Bodnár, Levente Gao, Jun León, Jared Liu, Xizhi Pikhurko, Oleg Sun, Shumin Combinatorics 05D99, 05C35 The inducibility constant $λ_{F}$ of a graph $F$ is the asymptotically maximum induced density of $F$ in a growing sequence of graphs. This paper systematically investigates the case when $F$ has 6 vertices (and there are 78 cases to consider up to isomorphism and complementation). We show that flag algebras can compute the sharp upper bound on $λ_F$ in 36 cases of which, as far as the authors know, 30 are new results. In each of the solved cases, we also prove results about the structure of large (almost) extremal graphs. In particular, we establish perfect stability in all 32 cases when the extremal construction has no quasirandom parts. We also present conjectures about the value of $λ_{F}$ for 12 further cases (where the upper and lower bounds are very close to each other). |
| title | The inducibility of 6-vertex graphs |
| topic | Combinatorics 05D99, 05C35 |
| url | https://arxiv.org/abs/2606.00290 |