Semi-Inducibility of some small graphs
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- The feasible region of induced graphsJournal of Combinatorial Theory, Series B, 2022
- Maximum star densitiesStudia Scientiarum Mathematicarum Hungarica, 2018
- Tree-minimal graphs are almost regularJournal of Combinatorics, 2012
- Flag algebrasThe Journal of Symbolic Logic, 2007
- The inducibility of graphsJournal of Combinatorial Theory, Series B, 1975