The number of C₂-free graphs

DOI10.1016/J.AIM.2016.05.001MaRDI QIDQ291780zbMATH OpenOpenAlexWikidataFDO

Authors Robert Morris, David Saxton

Publication date 10 June 2016

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

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

zbMATH Keywords

balanced supersaturationextremal graph theoryhypergraph containers

Mathematics Subject Classification ID

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

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.

Recommendations

• Generalized Turán problems for even cycles
• On a conjecture of Erdős and Simonovits: even cycles
• The number of \(K_{s,t}\)-free graphs
• Supersaturated sparse graphs and hypergraphs
• Four-cycles in graphs without a given even cycle

Cites work

• A note on the Turán function of even cycles
• Almost all \(C_4\)-free graphs have fewer than \((1-\varepsilon)\,\text{ex}(n,C_4)\) edges
• An extremal problem for random graphs and the number of graphs with large even-girth
• Combinatorial theorems in sparse random sets
• Compactness results in extremal graph theory
• Cycles of even length in graphs
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Extremal results in random graphs
• scientific article; zbMATH DE number 5130822 (Why is no real title available?)
• scientific article; zbMATH DE number 3900799 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 1943957 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Maximum-size antichains in random set-systems
• Minimal Regular Graphs of Girths Eight and Twelve
• New asymptotics for bipartite Turán numbers
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On a problem of K. Zarankiewicz
• On arithmetic progressions of cycle lengths in graphs
• On Graphs that do not Contain a Thomsen Graph
• On the number of B_h-sets
• On the number of graphs without 4-cycles
• On the structure of linear graphs
• On the Turán number for the hexagon
• Properties of certain families of \(2k\)-cycle-free graphs
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The fine structure of octahedron-free graphs
• The history of degenerate (bipartite) extremal graph problems
• The number of B₃-sets of a given cardinality
• The number of \(K_{m,m}\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• The number of Bh‐sets of a given cardinality
• The number of graphs without forbidden subgraphs
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• The typical structure of graphs without given excluded subgraphs
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• Turán's extremal problem in random graphs: Forbidding even cycles

Cited in

(51)

• The number of hypergraphs without linear cycles
• On subgraphs of \(C_{2k}\)-free graphs
• On hypergraphs without loose cycles
• Counting \(H\)-free graphs
• \( \mathbb{Z}_2 \times \mathbb{Z}_2\)-cordial cycle-free hypergraphs
• Triangle-free subgraphs of hypergraphs
• Pattern avoidance over a hypergraph
• Integer colorings with no rainbow 3-term arithmetic progression
• A new proof of the KŁR conjecture
• Counting \(r\)-graphs without forbidden configurations
• Generalized Turán problems for even cycles
• Counting Gallai 3-colorings of complete graphs
• Counting independent sets in graphs
• On the number of union-free families
• On a conjecture of Erdős and Simonovits: even cycles
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Which graphs can be counted in C₄-free graphs?
• The Turán number of directed paths and oriented cycles
• Almost all \(C_4\)-free graphs have fewer than \((1-\varepsilon)\,\text{ex}(n,C_4)\) edges
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• Hypergraph containers
• Supersaturation of even linear cycles in linear hypergraphs
• On subgraphs of \(C_{2k}\)-free graphs and a problem of Kühn and Osthus
• Ramsey numbers for nontrivial Berge cycles
• Counting H-free orientations of graphs
• An efficient container lemma
• Relative Turán problems for uniform hypergraphs
• Cycles in graphs of fixed girth with large size
• Supersaturated sparse graphs and hypergraphs
• On the number of graphs without large cliques
• The number of \(K_{s,t}\)-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
• An asymmetric container lemma and the structure of graphs with no induced 4-cycle
• Turán theorems for even cycles in random hypergraph
• Probabilistic hypergraph containers
• Generalized Turán problems for even cycles
• Counting arcs in \(\mathbb{F}_q^2\)
• Sidorenko hypergraphs and random Turán numbers
• On the number of \(\mathcal{H}\)-free hypergraphs
• On the evolution of structure in triangle-free graphs
• Clique supersaturation
• Listing 4-cycles
• On the maximum F-free induced subgraphs in K_t-free graphs
• On the random Turán number of linear cycles
• Random Turán theorem for expansions of spanning subgraphs of tight trees
• Maximum in-general-position set in a random subset of \(\mathbb{F}_q^d\)
• Supersaturation of odd linear cycles

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

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