On Erdős-Ko-Rado for random hypergraphs I

2014/12/16 by Arran Hamm, Jeff Kahn, Hamm, Arran +1 · 1 citation
Computer Science · Mathematics · #05C65 #05D05 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1412.5085

openalex publication_date 2014/12/16 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

A family of sets is intersecting if no two of its members are disjoint, and has the Erdős-Ko-Rado property (or is EKR) if each of its largest intersecting subfamilies has nonempty intersection. Denote by H_k(n,p) the random family in which each k-subset of \1… n\ is present with probability p, independent of other choices. A question first studied by Balogh, Bohman and Mubayi asks: for what p=p(n,k) is H_k(n,p) likely to be EKR? Here, for fixed c<1/4, and k< √(cnlog n) we give a precise answer to this question, characterizing those sequences p=p(n,k) for which Pr(H_k(n,p) \textrm is EKR) → 1 \textrm as n→ ∞.

Cited by

• Asymptotic enumeration via graph containers and entropy

Related

• On Erdős-Ko-Rado for random hypergraphs II
• Erd\Hos-Ko-Rado for random hypergraphs: asymptotics and stability
• Most Probably Intersecting Hypergraphs
• On the random version of the Erdős matching conjecture
• On "stability" in the Erdős-Ko-Rado theorem