Supersaturated sparse graphs and hypergraphs

DOI10.1093/IMRN/RNY030MaRDI QIDQ5216319zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Gweneth McKinley, Wojciech Samotij

Publication date 17 February 2020

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

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

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)

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.

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

Cited in

(16)

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

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)