The regularity method for graphs with few 4-cycles

DOI10.1112/JLMS.12500MaRDI QIDQ6339172arXivFDO

Authors David Conlon, Jacob Fox, Benny Sudakov, Yufei Zhao

Publication date 21 April 2020

Published in arXiv

Full work available at URL https://doi.org/10.1112/JLMS.12500

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Density (toughness, etc.) (05C42) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Sequences and sets (11B99) Additive number theory; partitions (11P99)

arXiv classification

math.CO

Abstract: We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include: * Every $n$-vertex graph with no 5-cycle can be made triangle-free by deleting $o(n^{3/2})$ edges. * For $rgeq3$, every $n$-vertex $r$-graph with girth greater than $5$ has $o(n^{3/2})$ edges. * Every subset of $[n]$ without a nontrivial solution to the equation $x_1+x_2+2x_3=x_4+3x_5$ has size $o(sqrtn)$.

This page was built for publication: The regularity method for graphs with few 4-cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339172)