Which graphs can be counted in C₄-free graphs?
For which graphs F is there a sparse F-counting lemma in C₄-free graphs? We are interested in identifying graphs F with the property that, roughly speaking, if G is an n-vertex C₄-free graph with on the order of n^(3/2) edges, then the density of F in G, after a suitable normalization, is approximately at least the density of F in an ε-regular approximation of G. In recent work, motivated by applications in extremal and additive combinatorics, we showed that C₅ has this property. Here we construct a family of graphs with the property.
Additional InformationPart of this work was completed in the summer of 2019 while Yufei Zhao was generously hosted by FIM (the Institute for Mathematical Research) during a visit to Benny Sudakov at ETH Zürich. David Conlon was supported by NSF Award DMS-2054452. Jacob Fox was supported by a Packard Fellowship and by NSF Award DMS-1855635. Benny Sudakov is supported in part by SNSF grant 200021_196965. Yufei Zhao is supported by NSF Award DMS-1764176, the MIT Solomon Buchsbaum Fund, and a Sloan Research Fellowship.
Submitted - 2106.03261.pdf