Supersaturation for hereditary properties

DOI10.1016/J.EJC.2011.10.008MaRDI QIDQ412233zbMATH OpenOpenAlexFDO

Authors David Saxton

Publication date 4 May 2012

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Hereditary quasirandom properties of hypergraphs
• Largest subgraph from a hereditary property in a random graph
• Supersaturated graphs and hypergraphs
• Hereditary properties of hypergraphs
• Hereditary quasi-random properties of hypergraphs

Cites work

• scientific article; zbMATH DE number 3825706 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• Excluding Induced Subgraphs III: A General Asymptotic
• Hereditary properties of hypergraphs
• On a packing and covering problem
• On the entropy values of hereditary classes of graphs
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Supersaturated graphs and hypergraphs
• The number of graphs with large forbidden subgraphs
• The structure of hereditary properties and 2-coloured multigraphs
• The structure of hereditary properties and colourings of random graphs

Cited in

(3)

• scientific article; zbMATH DE number 4101817 (Why is no real title available?)
• A heredity property of sufficiency
• Hypergraph containers

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)