The number of \(C_{2\ell}\)-free graphs

DOI10.1016/J.AIM.2016.05.001zbMATH Open1339.05199arXiv1309.2927OpenAlexW2963811178WikidataQ105583557 ScholiaQ105583557MaRDI QIDQ291780

Robert Morris, David Saxton

Publication date: 10 June 2016

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: One of the most basic questions one can ask about a graph $H$ is: how many $H$-free graphs on $n$ vertices are there? For non-bipartite $H$, the answer to this question has been well-understood since 1986, when ErdH{o}s, Frankl and R"odl proved that there are $2^{(1+o(1))ex(n,H)}$ such graphs. For bipartite graphs, however, much less is known: even the weaker bound $2^{O(ex(n,H))}$ has been proven in only a few special cases: for cycles of length four and six, and for some complete bipartite graphs. For even cycles, Bondy and Simonovits proved in the 1970s that ex$(n,C_{2l})=O(n^{1+1/l})$, and this bound is conjectured to be sharp up to the implicit constant. In this paper we prove that the number of $C_{2l}$-free graphs on $n$ vertices is at most $2^{O(n^{1+1/l})}$, confirming a conjecture of ErdH{o}s. Our proof uses the hypergraph container method, which was developed recently (and independently) by Balogh, Morris and Samotij, and by Saxton and Thomason, together with a new 'balanced supersaturation theorem' for even cycles. We moreover show that there are at least $2^{(1+c)ex(n,C_6)}$ $C_6$-free graphs on $n$ vertices for some $c>0$ and infinitely many values of $n$, disproving a well-known and natural conjecture. As a further application of our method, we essentially resolve the so-called Tur'an problem on the ErdH{o}s-R'enyi random graph $G(n,p)$ for both even cycles and complete bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1309.2927

zbMATH Keywords

extremal graph theorybalanced supersaturationhypergraph containers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of \(B_3\)-sets of a given cardinality
• Combinatorial theorems in sparse random sets
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• Hypergraph containers
• The fine structure of octahedron-free graphs
• The number of \(K_{m,m}\)-free graphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• On the number of graphs without 4-cycles
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• An extremal problem for random graphs and the number of graphs with large even-girth
• Norm-graphs: Variations and applications
• Properties of certain families of \(2k\)-cycle-free graphs
• The number of graphs without forbidden subgraphs
• Compactness results in extremal graph theory
• Cycles of even length in graphs
• Turán's extremal problem in random graphs: Forbidding even cycles
• New asymptotics for bipartite Turán numbers
• On the Turán number for the hexagon
• Norm-graphs and bipartite Turán numbers
• On arithmetic progressions of cycle lengths in graphs
• Maximum-size antichains in random set-systems
• A note on the Turán function of even cycles
• Almost All $C_4$-Free Graphs Have Fewer than $(1-\varepsilon)\,\mathrm{ex}(n,C_4)$ Edges
• The typical structure of graphs without given excluded subgraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• The number of Bh‐sets of a given cardinality
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• Independent sets in hypergraphs
• On the Number ofB_h-Sets
• The number of K _s,t -free graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Extremal Results in Random Graphs
• Minimal Regular Graphs of Girths Eight and Twelve
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• On the structure of linear graphs

Related Items (30)

Pattern avoidance over a hypergraph ⋮ Integer colorings with no rainbow 3-term arithmetic progression ⋮ The number of hypergraphs without linear cycles ⋮ Counting H-free orientations of graphs ⋮ Counting \(r\)-graphs without forbidden configurations ⋮ Counting \(H\)-free graphs ⋮ Balanced supersaturation for some degenerate hypergraphs ⋮ Counting hypergraphs with large girth ⋮ Random polynomial graphs for random Turán problems ⋮ Turán‐type problems for long cycles in random and pseudo‐random graphs ⋮ On hypergraphs without loose cycles ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Which graphs can be counted in \(C_4\)-free graphs? ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ The Turán number of directed paths and oriented cycles ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Probabilistic hypergraph containers ⋮ Hypergraph containers ⋮ Relative Turán Problems for Uniform Hypergraphs ⋮ Cycles in graphs of fixed girth with large size ⋮ Turán theorems for even cycles in random hypergraph ⋮ \( \mathbb{Z}_2 \times \mathbb{Z}_2\)-cordial cycle-free hypergraphs ⋮ Counting arcs in \(\mathbb{F}_q^2\) ⋮ An efficient container lemma ⋮ Triangle-free subgraphs of hypergraphs ⋮ Counting Gallai 3-colorings of complete graphs ⋮ Supersaturation of even linear cycles in linear hypergraphs ⋮ Counting independent sets in graphs ⋮ Ramsey Numbers for Nontrivial Berge Cycles ⋮ On the number of union-free families

This page was built for publication: The number of \(C_{2\ell}\)-free graphs