Which graphs can be counted in C₄-free graphs?

Abstract

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 details