Randomly generated intersecting hypergraphs II

DOI10.1002/RSA.20152MaRDI QIDQ3419609zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tom Bohman, Ryan R. Martin, Miklós Ruszinkó, Cliff Smyth, Alan Frieze

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph functionalsintersecting hypergraphsonline processes

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Let $c$ be a positive constant. Suppose that $r=o(n^{5/12})$ and the members of $$ are chosen sequentially at random to form an intersecting hypergraph $mathcalH$. We show that whp $mathcalH$ consists of a simple hypergraph $mathcalS$ of size $Theta(r/n^{1/3})$, a distinguished vertex $v$ and all $r$-sets which contain $v$ and meet every edge of $mathcalS$. This is a continuation of the study of such random intersecting systems started in [Electron. J. Combin, (2003) R29] where the case $r=O(n^{1/3})$ was considered. To obtain the stated result we continue to investigate this question in the range $omega(n^{1/3})lerleo(n^{5/12})$.

Recommendations

• On randomly generated intersecting hypergraphs
• Intersections of random hypergraphs and tournaments
• On randomly generated non-trivially intersecting hypergraphs
• The intersection graph of random sets
• Almost perfect matchings in random uniform hypergraphs

Cites work

• G-intersecting families
• On the size of a random maximal graph

Cited in

(5)

• On randomly generated intersecting hypergraphs
• On randomly generated non-trivially intersecting hypergraphs
• Erdős-Ko-Rado in random hypergraphs
• On the random satisfiable process
• On the intersecting family process

This page was built for publication: Randomly generated intersecting hypergraphs II

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