Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

Which graphs can be counted in C4-free graphs?

Pages: 2413 – 2432

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a4

Authors

David Conlon (Department of Mathematics, California Institute of Technology, Pasadena, Calif., U.S.A.)

Jacob Fox (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

Benny Sudakov (Department of Mathematics, ETH Zürich, Switzerland)

Yufei Zhao (Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Abstract

For which graphs $F$ is there a sparse $F$-counting lemma in $C_4$-free graphs? We are interested in identifying graphs $F$ with the property that, roughly speaking, if $G$ is an $n$-vertex $C_4$-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 $\epsilon$-regular approximation of $G$. In recent work, motivated by applications in extremal and additive combinatorics, we showed that $C_5$ has this property. Here we construct a family of graphs with the property.

2010 Mathematics Subject Classification

05C99

Full Text (PDF format)

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.

Received 6 June 2021

Received revised 24 July 2022

Accepted 11 August 2022

Published 29 March 2023