Supersaturation for hereditary properties

DOI10.1016/J.EJC.2011.10.008zbMATH Open1239.05134arXiv1104.5401OpenAlexW1996021607MaRDI QIDQ412233FDOQ412233

David Saxton

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $mathcalF$ be a collection of $r$-uniform hypergraphs, and let $0<p<1$. It is known that there exists $c=c(p,mathcalF)$ such that the probability of a random $r$-graph in $G(n,p)$ not containing an induced subgraph from $mathcalF$ is $2^{(-c+o(1))nchooser}$. Let each graph in $mathcalF$ have at least $t$ vertices. We show that in fact for every $epsilon>0$, there exists $delta=delta(epsilon,p,mathcalF)>0$ such that the probability of a random $r$-graph in $G(n,p)$ containing less than $delta{n}^t$ induced subgraphs each lying in $mathcalF$ is at most $2^{(-c+epsilon)nchooser}$. This statement is an analogue for hereditary properties of the supersaturation theorem of ErdH{o}s and Simonovits. In our applications we answer a question of Bollob'as and Nikiforov.

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Cites Work

• Projections of Bodies and Hereditary Properties of Hypergraphs
• On a packing and covering problem
• Title not available (Why is that?)
• Supersaturated graphs and hypergraphs
• Title not available (Why is that?)
• Excluding Induced Subgraphs III: A General Asymptotic
• On the entropy values of hereditary classes of graphs
• The structure of hereditary properties and colourings of random graphs
• Hereditary properties of hypergraphs
• The structure of hereditary properties and 2-coloured multigraphs
• The number of graphs with large forbidden subgraphs

Cited In (3)

• Hypergraph containers
• Title not available (Why is that?)
• A heredity property of sufficiency

This page was built for publication: Supersaturation for hereditary properties

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