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

2021/06/06 by Conlon, David, Fox, Jacob, Sudakov, Benny +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.03261

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.

Cited by

• Combinatorial theorems relative to sparse sets

Related

• Sparse halves in K₄-free graphs
• An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs
• The regularity method for graphs with few 4-cycles
• Cliques in C₄-free graphs of large minimum degree
• Subgraph densities in K_r-free graphs