March 3, 2026Open Access

Independent Sets in Hypergraphs

Key Points

Independent sets of size at least k exist in maximum degree hypergraphs, confirming Shearer's method can extend to uniform hypergraphs.
The theorem confirms that results on triangle-free graphs apply broadly, potentially impacting combinatorial optimization.
The study examines 'locally sparse' hypergraphs, extending the scope of existing independent set results.
The findings may guide future research in graph theory and combinatorics, underpinning connections between hypergraphs and independent sets.

Abstract

ABSTRACT A theorem of Shearer states that every ‐vertex triangle‐free graph of maximum degree contains an independent set of size at least . Ajtai, Komlós, Pintz, Spencer and Szemerédi proved that every ‐uniform ‐vertex “uncrowded” hypergraph of maximum degree has an independent set of size at least for some depending only on . 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.

Independent Sets in Hypergraphs

Key Points

Abstract

Cite This Study