Efficient Algorithms for Large Hypergraph Independent Sets

Definitions and mathematical statement

Let $H=(V,\mathcal E)$ be a finite hypergraph. A set $S\subseteq V$ is independent if no edge $e\in\mathcal E$ satisfies $e\subseteq S$. The hypergraph is $r$-uniform if every edge has cardinality $r$, and $d$-regular if every vertex belongs to exactly $d$ edges.

The supplied record refers to an independent set $I(H,\omega)$ obtained by a "random-ordering construction." Write \[ q(H)=\mathbb E_{\omega}\left[|I(H,\omega)|\right]. \] This notation is conditional: the record does not specify the construction or its probability distribution, so it does not determine $q(H)$.

The intended algorithmic question is whether there exist an absolute constant $c>0$ and a polynomial-time algorithm $A$ such that, for every hypergraph $H$ in the intended class of large-girth, $d$-regular, $r$-uniform hypergraphs, the algorithm returns a set $S=A(H)$ satisfying \[ S\subseteq V,\qquad \forall e\in\mathcal E\; e\nsubseteq S, \qquad |S|\ge c\,q(H). \] Here "absolute" requires $c$ to be independent of $H$, $d$, and $r$. The admissible ranges of $d$ and $r$, the hypergraph girth convention, the required girth threshold and its parameter dependence, the input representation, and the permitted algorithmic randomness and success guarantee are not specified. Consequently, this is a conditional formulation of the requested target, rather than a complete algorithmic problem specification.

The original excerpt additionally mentions random $d$-regular graphs and reports the existence of independent sets of size $(2-o(1))\mathbb E|I|$. The applicable parameter regime, asymptotic variable, probability qualification, and scope of this existence assertion are absent; it is retained as a supplied background claim, not asserted here as a verified theorem. The excerpt also introduces quantities involving $g$, $u(d,r)$, $\epsilon$, and $f(d,r)$, but their displayed formulas are corrupted and cannot be reconstructed reliably from the record.

Short English statement

Find a polynomial-time algorithm that always produces an independent set at least an absolute positive fraction of the expected size produced by the source's random-ordering construction on the intended regular, uniform hypergraphs of large girth. The construction, girth requirements, parameter ranges, and algorithmic success conditions need clarification before this target is fully specified. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30006549$, title "Efficient Algorithms for Large Hypergraph Independent Sets," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record lists proposed year $2026$ and supplies no proposer attribution.
• Combinatorics (2026), Oberwolfach Reports, Report 1/2026, pp. 5--79, DOI 10.4171/owr/2026/1. Supplied report reference and literature source: https://doi.org/10.4171/owr/2026/1.
• Verstraete--Wilson, Independent Sets in Hypergraphs. Supplied literature source: https://doi.org/10.1002/rsa.70047.
• Literature assessment dated 2026-08-22: the supplied curation labels the problem open and states that known randomized-greedy results quantify the expected independent-set size in high-girth regular hypergraphs, while no efficient algorithm achieving a fixed positive fraction of that expectation is known in the stated generality. This is supplied dated curation, not an independently verified literature assessment.
• The registry labels its statement corrected_verified and reports that the official Oberwolfach report was checked, the question isolated, and notation repaired. These are supplied verification claims; this draft has not independently checked the report or the cited mathematical claims.