Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 6, 2021 | Submitted
Report Open

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 Information

Part 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.

Attached Files

Submitted - 2106.03261.pdf


Files (222.4 kB)
Name Size Download all
222.4 kB Preview Download

Additional details

August 20, 2023
October 20, 2023