posted on 2009-06-22, 00:00authored byTom 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))( kn ) 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.
History
Publisher Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00493-010-2474-6