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 2022 | public
Journal Article

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

© 2022 International Press. Special issue in honor of Fan Chung. 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.

Additional details

August 22, 2023
October 20, 2023