Maximum Independent Sets in Regular Uniform Hypergraphs

Definitions and mathematical statement

Let $r\geq 2$ and $d\geq 1$ be integers. A finite $r$-uniform hypergraph $G$ has a finite vertex set $V(G)$, and each edge contains exactly $r$ distinct vertices. It is $d$-regular if every vertex belongs to exactly $d$ edges. Write $n=|V(G)|$. A set $I\subseteq V(G)$ is independent if it contains no edge of $G$, and define \[ \operatorname{ind}(G)=\left|\{I\subseteq V(G):\text{ there is no edge }e\text{ of }G\text{ with }e\subseteq I\}\right|. \] The supplied record does not specify whether repeated edges are permitted. If they are permitted, vertex degrees count edge occurrences. This convention must be resolved when specifying the admissible class.

Extremal question. For each choice of $n,r,d$ for which an admissible hypergraph exists, determine \[ M(n,r,d)=\max\left\{\operatorname{ind}(G): |V(G)|=n,\ G\text{ is }d\text{-regular and }r\text{-uniform}\right\}. \] Conjectural bound as supplied. Does every such $G$ satisfy \[ \operatorname{ind}(G)\leq \operatorname{ind}(H_d^r)^{\,n/(rd)}? \] The source calls $H_d^r$ the canonical $d$-regular hypergraph, but supplies no construction, vertex set, edge set, or explicit order for it. Consequently, this inequality retains an undefined source symbol and cannot yet be made into a fully specified conjecture. The exponent $n/(rd)$ is reproduced exactly; it does not supply a definition of $H_d^r$. No divisibility assumption $rd\mid n$ is stated in the record, and none is imposed here.

Short English statement

Determine the largest possible number of vertex subsets containing no entire edge in a finite regular uniform hypergraph. The supplied conjecture compares this count with that of a purported canonical hypergraph $H_d^r$, whose definition is missing. The admissible convention concerning repeated edges also requires clarification.

Sources

• Local UnsolvedMath registry, supplied complete record for permanent ID $30004359$, source problem code catalogue entry, titled "Maximum Independent Sets in Regular Uniform Hypergraphs." The record belongs to the Oberwolfach Reports Open Problems collection and supplies proposed year 2020; no individual proposer is named.
• Supplied report citation: Combinatorics (2021), Oberwolfach Reports, DOI 10.4171/owr/2020/1, pp. 6--89. https://doi.org/10.4171/owr/2020/1. The background describes these reports as records of mathematical workshops and their open-problem discussions. The relevant passage has not been independently inspected.
• Supplied literature reference: Cohen--Perkins--Sarantis--Tetali. https://arxiv.org/abs/2001.00653.
• Supplied literature reference: Balogh--Bollobás--Narayanan. https://doi.org/10.1016/j.jcta.2021.105405.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open, reports substantial partial results for the regular linear hypergraph analogue, and describes the general regular $r$-uniform question and a corresponding conjectural characterization as unresolved. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; its status and cited claims require independent verification.