Semi-Inducibility of some small graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909983210209280 |
|---|---|
| author | Balogh, József Lidický, Bernard Mubayi, Dhruv Pfender, Florian Volec, Jan |
| author_facet | Balogh, József Lidický, Bernard Mubayi, Dhruv Pfender, Florian Volec, Jan |
| contents | Let $H$ be a fixed graph whose edges are colored red and blue and let $β\in [0,1]$. Let $I(H, β)$ be the (asymptotically normalized) maximum number of copies of $H$ in a large red/blue edge-colored complete graph $G$, where the density of red edges in $G$ is $β$. This refines the problem of determining the semi-inducibility of $H$, which is itself a generalization of the classical question of determining the inducibility of $H$. The function $I(H, β)$ for $β\in [0,1]$ was not known for any graph $H$ on more than three vertices, except when $H$ is a monochromatic clique (Kruskal-Katona) or a monochromatic star (Reiher-Wagner). We obtain sharp results for some four and five vertex graphs, addressing several recent questions posed by various authors. We also obtain some general results for trees and stars. Many open problems remain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03433 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Semi-Inducibility of some small graphs Balogh, József Lidický, Bernard Mubayi, Dhruv Pfender, Florian Volec, Jan Combinatorics Let $H$ be a fixed graph whose edges are colored red and blue and let $β\in [0,1]$. Let $I(H, β)$ be the (asymptotically normalized) maximum number of copies of $H$ in a large red/blue edge-colored complete graph $G$, where the density of red edges in $G$ is $β$. This refines the problem of determining the semi-inducibility of $H$, which is itself a generalization of the classical question of determining the inducibility of $H$. The function $I(H, β)$ for $β\in [0,1]$ was not known for any graph $H$ on more than three vertices, except when $H$ is a monochromatic clique (Kruskal-Katona) or a monochromatic star (Reiher-Wagner). We obtain sharp results for some four and five vertex graphs, addressing several recent questions posed by various authors. We also obtain some general results for trees and stars. Many open problems remain. |
| title | Semi-Inducibility of some small graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.03433 |