Sabotaging Mantel's Theorem

Abstract

One of the earliest results in extremal graph theory, Mantel's theorem, states that the maximum number of edges in a triangle-free graph $G$ on $n$ vertices is $\lfloor n^2/4 \rfloor$. We investigate how this extremal bound is affected when $G$ is additionally required to contain a prescribed graph $H$ as a subgraph. We establish general upper and lower bounds for this problem, which are tight in the exponent for random triangle-free graphs and graphs generated by the triangle-free process, when the size of $H$ lies within certain ranges.