2024/09/30 by Verstraete, Jacques, Wilson, Chase
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.19908
A theorem of Shearer states that every n-vertex triangle-free graph of maximum degree d ≥ 2 contains an independent set of size at least (dlog d - d + 1)/(d - 1)2 ⋅ n. Ajtai, Komlós, Pintz, Spencer and Szemerédi proved that every (r + 1)-uniform n-vertex ``uncrowded'' hypergraph of maximum degree d ≥ 1 has an independent set of size at least cr(log d)1/r/d1/r ⋅ n for some cr > 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.