For every integer r≥ 2 and every integer d≥ 1, if H is a finite simple r-uniform d-regular hypergraph, then the number of weak independent sets of H satisfies i(H)≤ i(H_r,d), where a weak independent set is a vertex subset containing no edge of H, and H_r,d is the specified natural quasi-bipartite extremal construction.

Balogh–Bollobás–Narayanan independent-set conjecture

The conjecture asserts that among $d$ -regular $r$ -uniform hypergraphs, the specified complete $r$ -partite construction maximizes the number of independent sets. The original statement is known in some cases but remains unresolved for general $r\geq 3$ .

Known results

$r=2$ : the conjecture is the Kahn–Zhao theorem; extremal graphs are disjoint unions of copies of $K_{d,d}$ .
For $r\geq 3$ , the 2020 paper proves the conjectured bound for every $d$ -regular quasi-bipartite $r$ -graph.
The 2020 paper identifies the lack of vertex-transitivity of the model hypergraph for $r\geq 3$ as an obstacle to the general case.

September 2026 partial progress and counterexample

Sarantis, Tetali, and Zheng report that the conjectured asymptotic rate holds under a twin-quotient condition, with exact results for $2$ -regular hypergraphs and further parameter ranges. They also report a counterexample, for every $r\geq 3$ , to a stronger occupancy formulation; this does not refute the original conjecture.

Current status (as of September 2026): the $r=2$ case and several subclasses are settled, the stronger occupancy formulation is reported false for every $r\geq 3$ , and the original conjecture for general $r\geq 3$ remains open.

Balogh–Bollobás–Narayanan independent-set conjecture

Primary source

Additional references

Progress summary

Solutions 0