Maximum-Cut Surplus in Clique-Free Graphs

Definitions and mathematical statement

Use the conventional interpretation that graphs are finite, simple, and undirected; these conventions are not explicit in the supplied record. For an integer $r\geq 3$, let $K_r$ denote the complete graph on $r$ vertices. A graph is $K_r$-free if it contains no subgraph isomorphic to $K_r$.

For $G=(V,E)$, write $m=|E|$ and define \[ \operatorname{MaxCut}(G)=\max_{A\subseteq V}\left|\{\{u,v\}\in E:u\in A,\ v\in V\setminus A\}\right|, \qquad \operatorname{surp}(G)=\operatorname{MaxCut}(G)-\frac m2. \] For each integer $m\geq 0$, define the largest universally guaranteed surplus by \[ s_r(m)=\inf\{\operatorname{surp}(G):G\text{ is }K_r\text{-free and }|E(G)|=m\}. \] The extremal question is to determine $s_r(m)$, or its sharp asymptotic order as $m\to\infty$, for each fixed integer $r\geq 3$. The record does not specify whether an exact formula or sharp asymptotic order is intended. For $m=0$, the definition gives $s_r(0)=0$.

The explicitly stated subsidiary question is whether \[ \exists\varepsilon>0\ \forall r\in{\mathbb{Z}},\ r\geq 3\ \exists c_r>0\ \exists M_r\in{\mathbb{Z}}_{\geq 1}\ \forall m\in{\mathbb{Z}}_{\geq M_r}, \qquad s_r(m)\geq c_r m^{1/2+\varepsilon}. \] Thus $\varepsilon$ must be independent of $r$, while the positive constant and threshold in $\Omega_r$ may depend on $r$. Equivalently, every $K_r$-free graph with sufficiently many edges must admit a cut with at least $m/2+c_r m^{1/2+\varepsilon}$ edges.

The supplied dated assessment labels the problem partially solved: it attributes an affirmative resolution of this absolute-$\varepsilon$ question to Zhang and a strengthening to Jin--Milojevic--Tomon, while reporting that a stronger exponent conjecture of Alon, Bollobás, Krivelevich, and Sudakov remains open. This is supplied curation, not an independently verified mathematical or literature assessment. The stronger conjecture's exponent and full statement are absent, so they cannot be reconstructed here. The original excerpt also asks about improving an unspecified preceding bound when $G$ is far from a disjoint union of cliques; neither that bound nor a meaning of distance is supplied, so this contextual question has no precise formulation in the record.

Short English statement

For each fixed $r\geq 3$, determine the greatest surplus above half the edges that every $K_r$-free graph must have in its maximum cut. The highlighted question asks for a bound $c_r m^{1/2+\varepsilon}$ with one positive $\varepsilon$ valid for all $r$. Supplied curation dated 2026-08-22 reports this subsidiary question solved and a stronger, unspecified exponent conjecture still open; these claims require independent review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30006540$, title Maximum-Cut Surplus in Clique-Free Graphs, exact source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. The record supplies the status partially_solved and statement label corrected_verified. Its verification note says that the official report was checked and the question isolated with repaired notation; this describes supplied provenance, not verification performed for this draft.
• Combinatorics (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/1, pp. 5--79. Supplied report URL: https://doi.org/10.4171/owr/2026/1. The excerpt identifies the contribution MaxCut in H-free graphs: recent results and connections by Aleksa Milojević, joint work with Zhihan Jin, István Tomon, and Shengtong Zhang. No separate proposer is supplied.
• Jin--Milojevic--Tomon, Beyond the MaxCut problem in H-free graphs: https://arxiv.org/abs/2507.13298.
• Jin--Milojevic--Tomon--Zhang, From small eigenvalues to large cuts: https://arxiv.org/abs/2509.03490.
• Literature assessment checked at 2026-08-22: supplied dated curation, not independently verified. It reports the absolute-$\varepsilon$ surplus question solved by Zhang and strengthened by Jin--Milojevic--Tomon, and the stronger Alon--Bollobás--Krivelevich--Sudakov exponent conjecture still open. The supplied background explicitly calls for independent verification of time-sensitive status and cited claims.