On Triangle-Free Graphs Maximizing Embeddings of Bipartite Graphs

Abstract

In 1991 Győri, Pach, and Simonovits proved that for any bipartite graph $H$ containing a matching avoiding at most $1$ vertex, the maximum number of copies of $H$ in any large enough triangle-free graph is achieved in a balanced complete bipartite graph. In this paper we improve their result by showing that if $H$ is a bipartite graph containing a matching of size $x$ and at most $\frac{1}{2}\sqrt{x-1}$ unmatched vertices, then the maximum number of copies of $H$ in any large enough triangle-free graph is achieved in a complete bipartite graph. We also prove that such a statement cannot hold if the number of unmatched vertices is $\Omega(x)$.