Independent Sets in Hypergraphs

Abstract

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)/(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\ge 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.