Erdős-Ko-Rado for random hypergraphs: asymptotics and stability

DOI10.1017/S0963548316000420MaRDI QIDQ5366954zbMATH OpenOpenAlexFDO

Authors Marcelo Matheus Gauy, Hệp Hàn, Igor C. Oliveira

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

random \(k\)-uniform hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We investigate the asymptotic version of the ErdH{o}s-Ko-Rado theorem for the random $k$-uniform hypergraph $mathcal{H}^k(n,p)$. For $2leqk(n)leqn/2$, let $$ and $$. We show that with probability tending to 1 as $noinfty$, the largest intersecting subhypergraph of $mathcal{H}^k(n,p)$ has size $(1+o(1))pfracknN$, for any $pggfracnkl{n}^2!left(fracnkight)D^{-1}$. This lower bound on $p$ is asymptotically best possible for $k=Theta(n)$. For this range of $k$ and $p$, we are able to show stability as well. A different behavior occurs when $k=o(n)$. In this case, the lower bound on $p$ is almost optimal. Further, for the small interval $D^{-1}llpleq(n/k{)}^{1-varepsilon}{D}^{-1}$, the largest intersecting subhypergraph of $mathcal{H}^k(n,p)$ has size $Theta(ln(pD)N{D}^{-1})$, provided that $kggsqrtnlnn$. Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in $mathcal{H}^k(n,p)$, for essentially all values of $p$ and $k$.

Recommendations

• Erdős-Ko-Rado in random hypergraphs
• On Erdős-Ko-Rado for random hypergraphs. II
• On ``stability in the Erdős-Ko-Rado theorem
• On the stability of the Erdős-Ko-Rado theorem
• On Erdős-Ko-Rado for random hypergraphs. I

Cites work

• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• An extremal problem for random graphs and the number of graphs with large even-girth
• Combinatorial theorems in sparse random sets
• Erdős-Ko-Rado in random hypergraphs
• Extremal results for random discrete structures
• Graph products, Fourier analysis and spectral techniques
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Intersecting families of discrete structures are typically trivial
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On ``stability in the Erdős-Ko-Rado theorem
• On Erdős-Ko-Rado for random hypergraphs. I
• On Erdős-Ko-Rado for random hypergraphs. II
• On the measure of intersecting families, uniqueness and stability
• On the number of graphs without 4-cycles
• On the Shannon capacity of a graph
• On the stability of the Erdős-Ko-Rado theorem
• Removal and stability for Erdős-Ko-Rado
• Stability results for random discrete structures
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• Transference for the Erdős-Ko-Rado theorem

Cited in

(16)

• Intersecting families of discrete structures are typically trivial
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Counting independent sets in graphs
• On randomly generated non-trivially intersecting hypergraphs
• Polynomial configurations in subsets of random and pseudo-random sets
• Removal and stability for Erdős-Ko-Rado
• A simple removal lemma for large nearly-intersecting families
• Erdős-Ko-Rado in random hypergraphs
• On Erdős-Ko-Rado for random hypergraphs. II
• On Erdős-Ko-Rado for random hypergraphs. I
• On the chromatic index of random uniform hypergraphs
• Large cliques in sparse random intersection graphs
• Sharp threshold for the Erdős–Ko–Rado theorem
• Sidorenko hypergraphs and random Turán numbers
• Robustness of Erdős-Ko-Rado theorems on permutations and perfect matchings
• On the matching problem in random hypergraphs

This page was built for publication: Erdős-Ko-Rado for random hypergraphs: asymptotics and stability

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