Pith. sign in

REVIEW 3 major objections 5 minor 21 references

Beyond the MaxCut problem in $H$-free graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that graphs with no clique of size $m^{1/2-\delta}$ have surplus at least $m^{1/2+\varepsilon}$, and that graphs whose surplus is at most $n^{1+\varepsilon}$ are $n^{-\varepsilon}$-close to disjoint unions of cliques.

desk verdict The main theorems are real and the architecture is sound, but the proof of Theorem 1.1 has a false exponent inequality as written—easily patched—and the paper is conditional on Zhang's unreviewed preprint. read the letter →

arxiv 2507.13298 v1 pith:CV7BSTUW submitted 2025-07-17 math.CO

Zhihan Jin , Aleksa Milojević , István Tomon This is my paper · ORCID
classification math.CO MSC 05C3505C50
keywords MaxCutsurplusclique-freegraphssemidefiniteprogrammingHadamardproductspectralgraphtheorydensityincrementdisjointunionofcliques
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes two quantitative results about the MaxCut surplus of a graph, the amount by which its largest cut exceeds half the number of edges. The first says that avoiding cliques of size $m^{1/2-\delta}$ forces surplus at least $m^{1/2+\varepsilon}$, with $\varepsilon$ depending only on $\delta$; this improves an earlier polynomial gain of $m^{0.5001}$ and applies to every fixed $K_r$-free graph. The second says that if an $n$-vertex graph's surplus is at most $n^{1+\varepsilon}$, then the graph is $n^{-\varepsilon}$-close to a disjoint union of cliques, settling a question left open in a companion paper [21] about whether the stability parameter could be made polynomial. A corollary gives the same structure for graphs whose smallest adjacency eigenvalue has size at most $n^\varepsilon$. These are structural and extremal results in the theory of MaxCut, carrying the area past the $m^{1/2+o(1)}$ barrier for clique-avoiding graphs.

What carries the argument

The load-bearing object is the semidefinite relaxation $\operatorname{surp}^*(G)=\max\{-\langle A,X\rangle: X\succeq 0,\ X_{ii}\le 1\}$, which is within a $\log n$ factor of the true surplus by the graph Grothendieck inequality [8]. The proof carries a density-increment argument: starting from a dense graph with small surplus, Lemma 3.3 uses the triple Hadamard product $D=(B+E)^{\circ 3}$, where $B$ is the adjacency matrix with the principal component removed and $E$ is the negative-eigenvalue part, to find an induced subgraph on $n/4$ vertices whose edge density has improved from $1-p$ to $1-10^8p^3$; the Schur product theorem keeps $D$ positive semidefinite, and the positivity of $1_I^T D 1_I$ yields the density gain. Iterating this increment and a second boost in Section 4 produces a clique of size $n^{1-20\varepsilon}$ inside any graph with $n^{2-\varepsilon}$ edges and surplus $n^{1+\varepsilon}$. For the stability theorem, a balanced-subgraph lemma and an eigenvalue interlacing result transfer surplus bounds to the complement, and a Boolean matrix approximation step shows that a bipartite graph with small complement surplus is nearly complete or nearly empty, which forces the auxiliary clique graph to be a disjoint union of cliques.

What would settle it

A single counterexample to Lemma 4.5 would settle it: any graph with $n^{2-\varepsilon}$ edges, surplus at most $n^{1+\varepsilon}$, and no clique of size $n^{1-20\varepsilon}$ for $\varepsilon<10^{-3}$ contradicts the main clique lemma and therefore Theorem 1.1.

Watch

Extended reading notes

Core claim

The central claim is that surplus is controlled, in both directions, by closeness to a disjoint union of cliques. Theorem 1.1: for every $\varepsilon>0$ there exists $\delta>0$ such that every sufficiently large $m$-edge graph with no clique of size $m^{1/2-\delta}$ has a cut of size at least $m/2+m^{1/2+\varepsilon}$. Theorem 1.2: there exists an absolute $\varepsilon>0$ such that every $n$-vertex graph with surplus at most $n^{1+\varepsilon}$ is $n^{-\varepsilon}$-close to a disjoint union of cliques, meaning that at most $n^{2-\varepsilon}$ edges must be added or removed. Because $\operatorname{surp}(G)\le n|\lambda_n|/4$, the theorem applies directly to graphs with small smallest eigenvalue, giving the corollary that $|\lambda_n|\le n^{\varepsilon}$ implies $n^{-\varepsilon}$-closeness to a disjoint union of cliques. Together these answer the quantitative question raised in [21] of whether the stability parameter can be polynomial rather than merely positive.

Load-bearing premise

The load-bearing premise is the black-box theorem of the companion paper [21]: every sufficiently dense graph with small surplus contains a very dense induced subgraph on almost all of its vertices; the entire density-increment chain and both main theorems start from that result.

Editorial extensions

If this is right

  • For every fixed $r$, every $K_r$-free graph with $m$ edges has a cut of size at least $m/2+m^{1/2+\varepsilon_r}$ for a positive $\varepsilon_r$ depending on $r$; this delivers the polynomial surplus gain conjectured for fixed forbidden subgraphs, though still short of the $m^{3/4+\varepsilon_r}$ target mentioned in the introduction.
  • Any graph whose surplus is at most $n^{1+\varepsilon}$ can be made a disjoint union of cliques by editing at most $n^{2-\varepsilon}$ edges, so the excess cut size is a robust structural statistic rather than a delicate one.
  • Any graph with smallest eigenvalue $|\lambda_n|\le n^\varepsilon$ is $n^{-\varepsilon}$-close to a disjoint union of cliques, extending structure theorems for small smallest eigenvalue into the sparse, polynomial-\lambda regime.
  • Because the clique condition in Theorem 1.1 depends only on $m^{1/2-\delta}$, graphs with clique number up to $m^{1/2-\delta}$ receive the same surplus boost, which strengthens the earlier superlinear $\omega(m^{1/2})$ result for clique number $o(\sqrt{m})$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: the same three-term Hadamard product inequality could yield surplus bounds for graphs whose negative spectrum is controlled in $\ell^2$ norm, without the density-increment hypothesis; this is not stated in the paper.
  • Beyond the paper: the no-cherry condition used to recognize unions of cliques suggests a template for proving stability of other partition problems where a forbidden configuration of three parts is the only obstruction.
  • Beyond the paper: a natural stress test is to check whether the absolute exponent $\varepsilon$ in Theorem 1.2 can be pushed toward the $1/4$ barrier set by the equiangular-line constructions of [6], whose surplus is $O(n^{5/4})$ and whose smallest eigenvalue is $\Theta(n^{1/4})$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proves two main theorems. Theorem 1.1 states that for every ε>0 there is δ>0 such that any sufficiently large graph with m edges and no clique of size m^{1/2−δ} has a cut of size at least m/2 + m^{1/2+ε}. Theorem 1.2 states that there is an absolute ε>0 such that any n-vertex graph with surplus at most n^{1+ε} is n^{−ε}-close to a disjoint union of cliques; Corollary 1.3 extends this to graphs with smallest eigenvalue |λ_n| ≤ n^ε. The proofs use Zhang's theorem (arXiv:2507.10037) as a black box to pass to a dense subgraph, then a density-increment argument (Section 3), a spectral boost (Section 4) to locate large cliques, and a stability argument (Section 5) for the structural conclusion.

Significance. If correct, Theorem 1.1 improves Zhang's recent m^{1/2+0.0001} bound for H-free graphs under the weaker global assumption of no clique of size m^{1/2−δ}, and Theorem 1.2 answers Zhang's question on polynomial dependence of the stability parameter. The methods combine SDP relaxations, three-term Hadamard products, eigenvalue interlacing, and Boolean matrix approximation, and are presented in a clear, modular way. The paper is honest about its dependencies, and the main chain of reasoning is transparent. However, the results are conditional on an unreviewed preprint (Theorem 3.1), and the proof of Theorem 1.1 contains a false exponent inequality that leaves the dense-reduction step unsupported as written; both issues are repairable without changing the overall structure.

major comments (3)
  1. [Section 4, Proof of Theorem 1.1] In the proof of Theorem 1.1, the chain after 'If m ≤ n^{2−3ε}' reads n/6 ≥ (1/6)m^{1/(2−3ε)} ≥ m^{1/2+ε}. The second inequality is false for every 0<ε<1/6 and m>1: the exponent difference is 1/(2−3ε) − (1/2+ε) = ε(6ε−1)/(4−6ε) < 0, so (1/6)m^{1/(2−3ε)} tends to 0 relative to m^{1/2+ε} as m grows. Consequently, the contradiction that would force m ≥ n^{2−3ε} does not follow, and the subsequent application of Lemma 4.5 is not justified. Replacing 3ε by 4ε makes the exponent difference positive (4ε^2/(2−4ε) > 0) and the final clique bound still exceeds m^{1/2−O(ε)}, so the gap is repairable, but as written the proof of Theorem 1.1 is incomplete.
  2. [Section 5, Lemma 5.6] The estimate '∥B − 2λ1vuT ∥F = O(n^{3/2+ε})' is inconsistent with the preceding identity 2∥B − 2λ1uvT ∥^2_F = Σ_{i≠1,2n} μ_i^2 = O(n^{3/2+ε}); the correct order is O(n^{3/4+ε/2}) if the norm is not squared. Consequently, the application of Lemma 5.4 does not yield ∥B − xyT ∥^2_F = O(n^{5/6+ε/3}); with δ = O(n^{−1/2+ε}) the lemma gives O(n^{11/6+ε/3}). The subsequent inequality '5/6 + ε/3 < 2 − 2δ' should read '11/6 + ε/3 < 2 − 2δ', which still holds for the chosen δ = 0.05 and sufficiently small ε, so the argument is repairable, but the intermediate estimate as written is false.
  3. [Section 3, Theorem 3.1] Theorem 3.1, imported verbatim from Zhang's unreviewed preprint (arXiv:2507.10037), is the first step of both proofs: Lemma 4.5, used in Theorem 1.1 and in Lemma 5.2 for Theorem 1.2, assumes the existence of a very dense induced subgraph in any graph with n^{2−ε} edges and surplus n^{1+ε}. If Theorem 3.1 has a flaw or if its constants fail, both main theorems lose their starting point. The authors should either provide a self-contained proof of the needed case, or at minimum clarify the status of the preprint so the editor can weigh this dependency.
minor comments (5)
  1. [Abstract and Theorem 1.1 statement] The phrase 'For very ε >0' should read 'For every ε >0'.
  2. [Section 2] The word 'in particar' should be 'in particular'.
  3. [Proof of Lemma 4.1] The text 'we can apply Lemma 4.1' should read 'we can apply Lemma 4.3', and the symbol 'p_I' should be 'p_0'.
  4. [Proof of Theorem 1.2] The theorem hypothesis bounds the true surplus surp(G) ≤ n^{1+ε}, but Lemma 5.2 requires a bound on surp*(G). Since Claim 2.2 gives surp*(G) ≤ O(log n) surp(G), the proof should halve ε to absorb the logarithmic factor; this is a straightforward fix but should be stated.
  5. [References and text] Reference [13] spells 'Goethels' where the standard spelling is 'Goethals' (J. M. Goethals), and 'Cauchy-Schwartz' in the proof of Lemma 4.3 should be 'Cauchy-Schwarz'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main theorems are derived from Zhang's external black-box theorem and from lemmas proved in the paper; the only self-citations are methodological and non-load-bearing.

full rationale

The derivation chain is not circular. Theorem 1.1 is reduced to Lemma 4.5, which invokes Zhang's Theorem 3.1 as an explicitly external black box and then applies Lemmas 3.2 and 4.1; both lemmas are proved in the paper from spectral and Hadamard-product arguments that do not assume the surplus bound being proved. Theorem 1.2 is built from Lemmas 5.2, 5.6 and 5.5, again with proofs given in the paper. No parameter is fitted to the target surplus exponent, and no target conclusion is used as a hypothesis. The authors do cite their own earlier work — [4], [19], [20] — but only for technique and for the graph Grothendieck inequality; the load-bearing quantitative claims are either proved in the text (e.g., Lemma 2.3, Lemma 4.3) or belong to external authors (Zhang, Charikar-Wirth, Erdős-Gyárfás-Kohayakawa). The main caveat is a reliability concern rather than a circularity one: Theorem 3.1 is imported from a same-day unreviewed preprint by Zhang, so the present theorems stand or fall with that external result. There is also an apparent arithmetic slip in the proof of Theorem 1.1 in the step comparing n/6 with m^{1/2+ε}, but an internal error of that kind is a correctness issue, not a circular reduction. Therefore, no step reduces to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard spectral and combinatorial tools plus Zhang's externally supplied dense-subgraph theorem. No free empirical parameters or invented entities are introduced.

assumptions (4)
  • domain assumption Zhang's Theorem 3.1 (Theorem 1.7 in arXiv:2507.10037): dense graphs with small surplus contain a very dense large induced subgraph.
    Invoked as a black box at the start of Section 3, Section 4, and Lemma 4.5. The correctness of both main theorems depends on this external result, which is a same-day unreviewed preprint.
  • standard math Claim 2.2: the SDP relaxation surp*(G) and the true surplus agree up to a log n factor, via the graph Grothendieck inequality.
    Used throughout to pass between surp and surp*. The direction surp*>=surp and surp>=Omega(surp*/log n) is cited to [20] and [21].
  • standard math Schur product theorem, Weyl's inequality, and Turan's theorem.
    Standard tools invoked in Lemma 2.3, Lemma 4.2, and Lemma 4.5 without proof. Their use is routine.
  • standard math Erdos-Gyarfas-Kohayakawa result that every n-vertex m-edge graph without isolated vertices has surplus at least n/6.
    Used in the proof of Theorem 1.1 to handle the sparse case m <= n^(2-3epsilon).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond the MaxCut problem in $H$-free graphs." pith.science (2026). https://pith.science/paper/CV7BSTUW

@misc{pith2026250713298,
  author       = {Pith},
  title        = {Pith review of: Beyond the MaxCut problem in $H$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CV7BSTUW}},
  note         = {Machine review of arXiv:2507.13298}
}
abstract

In a recent breakthrough, Zhang proves that if $G$ is an $H$-free graph with $m$ edges, then $G$ has a cut of size at least $m/2+c_Hm^{0.5001}$, making a significant step towards a well known conjecture of Alon, Bollob\'as, Krivelevich and Sudakov. We show that the methods of Zhang can be further boosted, and prove the following strengthening. If $G$ is a graph with $m$ edges and no clique of size $m^{1/2-\delta}$, then $G$ has a cut of size at least $m/2+m^{1/2+\varepsilon}$ for some $\varepsilon=\varepsilon(\delta)>0$. In addition, we sharpen another result of Zhang by proving that if $G$ is an $n$-vertex $m$-edge graph with MaxCut of size at most $m/2+n^{1+\varepsilon}$ (or its smallest eigenvalue $\lambda_n$ satisfies $|\lambda_n|\leq n^{\varepsilon}$), then $G$ is $n^{-\varepsilon}$-close to the disjoint union of cliques for some absolute constant $\varepsilon>0$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 20 canonical work pages

  1. [1]

    Alon.Bipartite subgraphs.Combinatorica 16 (1996): 301–311

    N. Alon.Bipartite subgraphs.Combinatorica 16 (1996): 301–311

    work page 1996

  2. [2]

    N. Alon, B. Bollobás, M. Krivelevich, and B. Sudakov.Maximum cuts and judicious partitions in graphs without short cycles.J. Combin. Theory Ser. B, 88(2) (2003): 329–346

    work page 2003

  3. [3]

    N. Alon, M. Krivelevich, and B. Sudakov.MaxCut in H-free graphs.Combin. Probab. Comput. 14 (2005): 629–647

    work page 2005

  4. [4]

    Factorization norms and an inverse theorem for MaxCut

    I.Balla, L.Hambardzumyan, andI.Tomon. Factorization norms and an inverse theorem for MaxCut. preprint, arxiv:2506.23989 (2025). 16

    arXiv 2025

  5. [5]

    Balla, O

    I. Balla, O. Janzer, and B. Sudakov.On MaxCut and the Lovász theta function.Proc. Amer. Math. Soc. 152 (2024): 1871–1879

    work page 2024

  6. [6]

    de Caen.Large equiangular sets of lines in Euclidean space.Electronic Journal of Combinatorics 7 (2000): #R55

    D. de Caen.Large equiangular sets of lines in Euclidean space.Electronic Journal of Combinatorics 7 (2000): #R55

    work page 2000

  7. [7]

    Carlson, A

    C. Carlson, A. Kolla, R. Li, N. Mani, B. Sudakov, and L. Trevisan.Lower bounds for max-cut in H-free graphs via semidefinite programming.SIAM J. Discrete Math., 35(3) (2021): 1557–1568

    work page 2021

  8. [8]

    Charikar, and A

    M. Charikar, and A. Wirth.Maximizing quadratic programs: extending Grothendieck’s Inequality. FOCS (2004): 54–60

    work page 2004

Show all 21 references
  1. [9]

    C. S. Edwards. Some extremal properties of bipartite subgraphs. Canadian J. Math. 25 (1973): 475–485

    1973

  2. [10]

    C. S. Edwards.An improved lower bound for the number of edges in a largest bipartite subgraph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) (1975): 167–181

    1975

  3. [11]

    Erdős.Problems and results in graph theory and combinatorial analysis.Graph theory and related topics (Proc

    P. Erdős.Problems and results in graph theory and combinatorial analysis.Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, 1977), Academic Press, (1979) 153–163

    1979

  4. [12]

    Erdős, A

    P. Erdős, A. Gyárfás, and Y. Kohayakawa.The size of the largest bipartite subgraphs.Disc. Math. 177 (1997): 267– 271

    1997

  5. [13]

    P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult.Line graphs, root systems, and elliptic geometry. Journal of Algebra, 43(1) (1976): 305–327

    1976

  6. [14]

    Glock, O

    S. Glock, O. Janzer, and B. Sudakov.New results for MaxCut inH-free graphs.J. London Math. Soc. 108 (2023): 441–481

    2023

  7. [15]

    M. X. Goemans, and D. P. Williamson.Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.JournaloftheACM42(6)(1995): 1115–1145

    1995

  8. [16]

    H. K. Kim, J. H. Koolen, and J. J. Yang.A structure theory for graphs with fixed smallest eigenvalue. Lin. Alg. Appl. 504 (2016): 1–13

    2016

  9. [17]

    J. H. Koolen, M. Y. Cao, and Q. Yang.Recent progress on graphs with fixed smallest adjacency eigenvalue: A survey.Graphs and Combinatorics 37(4) (2021): 1139–1178

    2021

  10. [18]

    J. H. Koolen, J. Y. Yang, and Q. Yang.On graphs with smallest eigenvalue at least -3 and their lattices. Advances in Mathematics 338 (2018): 847–864

    2018

  11. [19]

    E. Räty, B. Sudakov, and I. Tomon.Positive discrepancy, MaxCut, and eigenvalues of graphs.to appear in Trans. AMS

  12. [20]

    Räty, and I

    E. Räty, and I. Tomon.Large Cuts in Hypergraphs via Energy.Math. Proc. Camb. Soc. 179 (1) (2025): 45–61

    2025

  13. [21]

    An Alon-Boppana type bound for very dense graphs, with applications to Max-Cut.preprint, arXiv:2507.10037 (2025)

    S.Zhang. An Alon-Boppana type bound for very dense graphs, with applications to Max-Cut.preprint, arXiv:2507.10037 (2025). 17

    2025 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.