Semi-Inducibility of some small graphs

Abstract

Let $H$ be a fixed graph whose edges are colored red and blue and let ${\hat{I}}^2\in [0,1]$. Let $I(H,{\hat{I}}^2)$ 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 ${\hat{I}}^2$. 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,{\hat{I}}^2)$ for ${\hat{I}}^2\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.

24 pages, 7 figures