Independent Sets in Hypergraphs

A theorem of Shearer states that every $n$-vertex triangle-free graph of maximum degree $d\ge 2$ contains an independent set of size at least $(d\log d-d+1)\mathrm{/}(d-1{)}^2\cdot n$. Ajtai, Komlós, Pintz, Spencer and Szemerédi proved that every $(r+1)$-uniform $n$-vertex uncrowded'' hypergraph of maximum degree $d \geq 1$ has an independent set of size at least $c_r(\log d)^{1/r}/d^{1/r} \cdot n$ for some $c_r > 0$ depending only on $r$. Shearer asked whether his method for triangle-free graphs could be extended to uniform hypergraphs. In this paper, we answer this in the affirmative, thereby giving a short proof of the theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi for a wider class of locally sparse’’ hypergraphs.