On independent sets in hypergraphs

2011/06/15 by Alexander V. Kostochka, Kostochka, Alexander, Dhruv Mubayi +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1106.3098

openalex publication_date 2011/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove new sharp bounds on the independence number of n-vertex (r+1)-uniform hypergraphs in which every r-element set is contained in at most d edges, where 0 < d < n/(log n)^3r2. Our relatively short proof extends a method due to Shearer. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.

Related

• An Efficiently Computable Lower Bound for the Independence Number of Hypergraphs
• Sparse hypergraphs with low independence number
• Independent Sets in Hypergraphs
• Independence in Uniform Linear Triangle-free Hypergraphs
• The independence number of non-uniform uncrowded hypergraphs and an anti-Ramsey type result