Carnegie Mellon University
file.pdf (194.14 kB)

Hypergraphs with independent neighborhoods

Download (194.14 kB)
journal contribution
posted on 2009-06-22, 00:00 authored by Tom Bohman, Alan FriezeAlan Frieze, Dhruv Mubayi, Oleg Pikhurko

For each k ≥ 2, let ρ k ∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ k + o(1))( k n ) edges as n → ∞. We prove that ρ k = 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors.


Publisher Statement

The final publication is available at Springer via



Usage metrics