Second-Order Cut Bounds for Uniform Hypergraphs

Definitions and mathematical statement

Fix integers $k\ge r\ge2$ satisfying $r\ge3$ or $k\ge4$. Under the conventional finite simple hypergraph interpretation, let $H=(V,E)$, where $V$ is finite, $E\subseteq\binom{V}{k}$, and $m=|E|$. For a partition $V=V_1\sqcup\cdots\sqcup V_r$, define its $r$-cut to consist of the edges meeting every part, with size \[ C_H(V_1,\ldots,V_r)=\left|\{e\in E:e\cap V_i\ne\varnothing\text{ for every }i\in\{1,\ldots,r\}\}\right|. \] Here parts may be empty; any cut of positive size necessarily has all parts nonempty. Let $S(k,r)$ denote the Stirling number of the second kind, the number of partitions of a $k$-element set into $r$ nonempty unlabelled blocks, and set \[ \alpha_{r,k}=\frac{S(k,r)r!}{r^k}. \] Thus $\alpha_{r,k}$ is the probability that an edge meets all $r$ classes when its vertices receive independent uniform labels from $\{1,\ldots,r\}$.

The question is whether, for every fixed admissible pair $(r,k)$, there exist a constant $c_{r,k}>0$ and an integer $m_0(r,k)\ge1$ such that every such hypergraph with $m\ge m_0(r,k)$ admits a partition satisfying \[ C_H(V_1,\ldots,V_r)\ge\alpha_{r,k}m+c_{r,k}m^{2/3}. \] The constants must be independent of $H$, $m$, and $|V|$. This is the asymptotic interpretation of the supplied term $\Omega(m^{2/3})$.

The record does not explicitly define an $r$-cut or specify finiteness and the exclusion of repeated edges. The definitions above give a conventional interpretation requiring source confirmation; they do not establish that these conventions are explicitly stated in the cited report. The supplied label partially_solved and its literature assessment are dated curation, not mathematical conclusions verified by this draft.

Short English statement

For each fixed admissible $(r,k)$, must every sufficiently large $k$-uniform hypergraph admit a partition into $r$ classes for which the number of edges meeting every class exceeds the random-partition baseline $\alpha_{r,k}m$ by at least a positive constant times $m^{2/3}$? Hypergraph and cut conventions require confirmation from the source.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004134$, source problem code catalogue entry, title Second-Order Cut Bounds for Uniform Hypergraphs; collection: Oberwolfach Reports Open Problems. Local registry paths: data/unsolvedmath/problems.json and the supplementary catalog/problems.json. The supplied proposed year is $2019$; no individual proposer is named.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, DOI 10.4171/owr/2019/19, pp. 1113--1189. https://doi.org/10.4171/owr/2019/19. The background describes these reports as documenting mathematical workshops and their open-problem discussions. This supplied citation has not been independently consulted.
• Supplied literature source: Conlon--Fox--Kwan--Sudakov, https://arxiv.org/abs/1803.08462.
• Supplied literature source: Janzer--Portier, https://arxiv.org/abs/2511.08501.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem partially solved and states that the exact conjectured $m^{2/3}$ bound is not known in general, that special cases have stronger bounds, and that recent work proves an approximate $m^{2/3-\varepsilon}$ result in broad ranges. This is supplied dated curation derived from the OWR record, not independently verified; its time-sensitive status and cited claims require independent checking.
• The supplied statement status is corrected_verified; its accompanying note says mathematical content was preserved while notation, typography, and sentence structure were repaired for publication. This is a source-record assertion, not independent mathematical verification by this draft.