On Randomly Generated Intersecting Hypergraphs

  • Tom Bohman
  • Colin Cooper
  • Alan Frieze
  • Ryan Martin
  • Mikl√≥s Ruszink√≥

Abstract

Let $c$ be a positive constant. We show that if $r=\lfloor{cn^{1/3}}\rfloor$ and the members of ${[n]\choose r}$ are chosen sequentially at random to form an intersecting hypergraph then with limiting probability $(1+c^3)^{-1}$, as $n\to\infty$, the resulting family will be of maximum size ${n-1\choose r-1}$.

Published
2003-08-12
Article Number
R29