The structure of typical eye-free graphs and a Turan-type result for two weighted colours

Abstract

The $(a,b)$-eye is the graph $I_{a,b}=K_{a+b}-K_b$ obtained by deleting the edges of a clique of size $b$ from a clique of size $a+b$. We show that for any $a,b\ge 2$ and $p\in (0,1)$, if we condition the random graph $G\sim G(n,p)$ on having no induced copy of $I_{a,b}$, then with high probability $G$ is close to an $a$-partite graph or the complement of a $(b-1)$-partite graph. Our proof uses the recently developed theory of hypergraph containers, and a stability result for an extremal problem with two weighted colours. We also apply the stability method to obtain an exact Turán-type result for this extremal problem.

17 pages