Contents Online

# 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 $C_4$-free graphs?

Pages: 2413 – 2432

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

#### Authors

#### 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

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