Θ(√m) excess for hypergraph r-cuts

Status disproved high confidence

The conjecture that the minimum maximum $r$-cut excess over all $m$-edge $k$-graphs is $\Theta(\sqrt{m})$ for every fixed $2 \le r \le k$ is disproved by Theorem 1.2 of the source paper itself, which shows the excess is $\Omega(m^{5/9})$ for all $r \ge 3$ or $k \ge 4$—strictly larger than $\sqrt{m}$ for large $m$, while the cases $r=k=2$ and $r=2,k=3$ are known to be tight at $\Theta(\sqrt{m})$. Subsequent work has further pushed the lower bound upward: Räty and Tomon (2024) reached $m^{3/5-o(1)}$ for general hypergraphs and $m^{3/4-o(1)}$ (tight) for linear hypergraphs, and Janzer and Portier (2025) proved $m^{2/3-\varepsilon}$ for all sufficiently large $k$, progressively moving the picture far above the $\sqrt{m}$ threshold.

Cited literature (2)

• partial Large Cuts in Hypergraphs via Energy (2024)
  Eero Räty, István Tomon · Mathematical Proceedings of the Cambridge Philosophical Society · arXiv:2410.01682

  Improves the lower bound on r-cut excess from $\Omega(m^{5/9})$ to $m^{3/5-o(1)}$ for general $r$-uniform hypergraphs and to $m^{3/4-o(1)}$ (tight up to $o(1)$) for linear hypergraphs, further confirming the $\Theta(\sqrt{m})$ conjecture is false and improving the quantitative picture.

• partial Nearly tight bounds for MaxCut in hypergraphs (2025)
  Oliver Janzer, Julien Portier · arXiv preprint · arXiv:2511.08501

  Proves that for each $\varepsilon>0$ there exists $k_0$ such that for all $k>k_0$ and $2\le r\le k$, every $k$-uniform hypergraph has an $r$-cut exceeding the random cut by $\Omega(m^{2/3-\varepsilon})$, and $\Omega(m^{3/4})$ for linear hypergraphs (tight); these bounds are far above $\sqrt{m}$.

Reviewer notes. The conjecture is disproved by Theorem 1.2 of the source paper itself: the same 2019 paper that proposes it as a plausible guess immediately shows it fails for all $r\ge 3$ or $k\ge 4$, since $\Omega(m^{5/9})\gg \sqrt{m}$. The remaining cases $r=k=2$ and $r=2,k=3$ satisfy $\Theta(\sqrt{m})$ and were already known. Subsequent papers pursue the correct tight exponent, currently conjectured to be $2/3$ for general $k$-uniform hypergraphs.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).