Some exact inducibility-type results for graphs via flag algebras
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915791962636288 |
|---|---|
| author | Bodnár, Levente Pikhurko, Oleg |
| author_facet | Bodnár, Levente Pikhurko, Oleg |
| contents | The $(κ,\ell)$-edge-inducibility problem asks for the maximum number of $κ$-subsets inducing exactly $\ell$ edges that a graph of given order $n$ can have. Using flag algebras and stability approach, we resolve this problem for all sufficiently large $n$ (including a description of all extremal and almost extremal graphs) in eleven new non-trivial cases when $κ\le 7$.
We also compute the $F$-inducibility constant (the asymptotically maximum density of induced copies of $F$ in a graph of given order $n$) and obtain some corresponding structure results for three new graphs $F$ with $5$ vertices: the 3-edge star plus an isolated vertex, the 4-cycle plus an isolated vertex, and the 4-cycle with a pendant edge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01596 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some exact inducibility-type results for graphs via flag algebras Bodnár, Levente Pikhurko, Oleg Combinatorics 05C35 The $(κ,\ell)$-edge-inducibility problem asks for the maximum number of $κ$-subsets inducing exactly $\ell$ edges that a graph of given order $n$ can have. Using flag algebras and stability approach, we resolve this problem for all sufficiently large $n$ (including a description of all extremal and almost extremal graphs) in eleven new non-trivial cases when $κ\le 7$. We also compute the $F$-inducibility constant (the asymptotically maximum density of induced copies of $F$ in a graph of given order $n$) and obtain some corresponding structure results for three new graphs $F$ with $5$ vertices: the 3-edge star plus an isolated vertex, the 4-cycle plus an isolated vertex, and the 4-cycle with a pendant edge. |
| title | Some exact inducibility-type results for graphs via flag algebras |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2507.01596 |