TOPICS
Search

Hypergraph Independent Set


An independent set of a hypergraph is a subset of its vertices containing no complete hyperedge. Its independence number alpha(H) is the largest size of such a set (Berge 1989). For a 2-uniform hypergraph, this agrees with an independent vertex set of an ordinary graph. This condition differs from requiring that every two selected vertices lie in no common hyperedge.

Delcourt et al. (2026, Theorem 1.14) obtained a bound for sparse hypergraphs with edges of mixed sizes. Fix an integer r>=3 and real constants beta,K>0. There are constants c=c(r,beta)>0 and q_0=q_0(r,beta,K) such that, for every q>=q_0 and every sufficiently large D depending on q, the following holds. Let H have N<=KqD vertices and all hyperedges of size between 2 and r. For 1<=l<=j<=r, let Delta_l(H^((j))) be the maximum number of size-j hyperedges containing an l-subset of vertices. If

 Delta_1(H^((2)))<=D,
(1)
 Delta_1(H^((j)))<=D^(j-1)lnq,
(2)

for 3<=j<=r, and

 Delta_l(H^((j)))<=D^(j-l)q^(-beta),
(3)

for 2<=l<j<=r, then

 alpha(H)>=cN/D.
(4)

The size restriction N<=KqD, the large-parameter requirements, and the separate bound on 2-element hyperedges are part of the hypotheses.


See also

Hyperedge, Hypergraph, Independence Number, Independent Vertex Set

Explore with Wolfram|Alpha

References

Berge, C. Hypergraphs: The Theory of Finite Sets. Amsterdam, Netherlands: North-Holland, 1989.Delcourt, M.; Henderson, C.; Lesgourgues, T.; and Postle, L. "Hypergraph Hajnal-Szemerédi." 19 Nov 2026. https://arxiv.org/abs/2611.26513v1.

Cite this as:

Weisstein, Eric W. "Hypergraph Independent Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HypergraphIndependentSet.html

Subject classifications