Supersaturated sparse graphs and hypergraphs

DOI10.1093/IMRN/RNY030zbMATH Open1433.05152arXiv1710.04517OpenAlexW2963846904MaRDI QIDQ5216319FDOQ5216319

Gweneth McKinley, Wojciech Samotij, Asaf Ferber

Publication date: 17 February 2020

Published in: IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Abstract: A central problem in extremal graph theory is to estimate, for a given graph $H$, the number of $H$-free graphs on a given set of $n$ vertices. In the case when $H$ is not bipartite, fairly precise estimates on this number are known. In particular, thirty years ago, ErdH{o}s, Frankl, and R"odl proved that there are $2^{(1+o(1))extex(n,H)}$ such graphs. In the bipartite case, however, nontrivial bounds have been proven only for relatively few special graphs $H$. We make a first attempt at addressing this enumeration problem for a general bipartite graph $H$. We show that an upper bound of $2^{O(extex(n,H))}$ on the number of $H$-free graphs with $n$ vertices follows merely from a rather natural assumption on the growth rate of $nmapstoextex(n,H)$; an analogous statement remains true when $H$ is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of ErdH{o}s and Simonovits. The bounds on the number of $H$-free hypergraphs are derived from it using the method of hypergraph containers.

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

Recommendations

• The number of \(C_{2\ell}\)-free graphs
• Supersaturated graphs and hypergraphs
• Supersaturation for subgraph counts
• The number of \(K_{s,t}\)-free graphs
• Balanced supersaturation for some degenerate hypergraphs

zbMATH Keywords

uniform hypergraphextremal number of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Cited In (15)

• Counting hypergraphs with large girth
• Supersaturation for subgraph counts
• Counting H-free orientations of graphs
• Independent sets in algebraic hypergraphs
• Pattern avoidance over a hypergraph
• Probabilistic hypergraph containers
• $L_p$ regular sparse hypergraphs
• On the number of error correcting codes
• Random multilinear maps and the Erd\H{o}s box problem
• Balanced supersaturation for some degenerate hypergraphs
• Supersaturated graphs and hypergraphs
• Counting \(r\)-graphs without forbidden configurations
• Turán theorems for even cycles in random hypergraph
• Asymptotic growth of sparse saturated structures is locally determined
• Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers

This page was built for publication: Supersaturated sparse graphs and hypergraphs

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