posted on 2009-06-22, 00:00authored byTom Bohman, Alan FriezeAlan Frieze, Dhruv Mubayi, Oleg Pikhurko
<p>For each <em>k</em> ≥ 2, let <em>ρ</em> <em>k</em> ∈ (0, 1) be the largest number such that there exist <em>k</em>-uniform hypergraphs on <em>n</em> vertices with independent neighborhoods and (<em>ρ</em> <em>k</em> + <em>o</em>(1))( <em>k</em> <em>n</em> ) edges as <em>n</em> → ∞. We prove that <em>ρ</em> <em>k</em> = 1 − 2log<em>k/k</em> + <em>Θ</em>(log log <em>k/k</em>) as <em>k</em> → ∞. This disproves a conjecture of Füredi and the last two authors.</p>