Independent Sets in Hypergraphs
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.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Combinatorial Mathematics
Analytic Number Theory Research
Publication details
- Journal / source
- Random Structures and Algorithms
- Volume
- 68
- Issue
- 1
- Publication date
- 1 January 2026
- Language
- EN