Pith. sign in

REVIEW 5 minor 34 references

Max-Bisections of graphs without even cycles

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Every even-cycle-free graph with minimum degree at least k has a bisection of size m/2 + Ω(m^{(2k+1)/(2k+2)}).

desk verdict A solid, genuinely new bisection analogue of the AKS theorem; the reader's counterexample misreads the sign, and the proof is sound up to minor quantifier cleanups. read the letter →

arxiv 2505.21694 v2 pith:5RMPGGJ6 submitted 2025-05-27 math.CO

Jianfeng Hou , Siwei Lin , Qinghou Zeng This is my paper
classification math.CO MSC 05C3505C70
keywords max-bisectionevencyclesC_{2k}-freegraphsminimumdegreesemidefiniteprogrammingsparseneighborhoodsextremalgraphtheorybalancedbipartition
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 a bisection version of the Alon–Krivelevich–Sudakov theorem: for every integer $k \ge 2$, any graph with $m$ edges, no cycle of length $2k$, and minimum degree at least $k$ has a balanced bipartition, a bisection, with at least $m/2 + \Omega(m^{(2k+1)/(2k+2)})$ edges. The exponent matches the one known for unrestricted cuts, so the balance constraint costs nothing in this regime. This answers a problem of Fan, Hou, and Yu about $C_4$-free graphs and sharpens a recent result that required excluding both $C_4$ and $C_6$ along with $C_{2k}$. The proof works through a semidefinite-programming-inspired rounding lemma for bisections and a new degree-sequence bound for graphs whose vertex neighborhoods are sparse.

What carries the argument

The engine is a bisection analogue of the Goemans–Williamson hyperplane rounding: Lemma 3.2 shows that for any assignment of unit vectors to vertices, a random hyperplane cut, followed by moving a bounded number of low-degree vertices to equalize the parts, yields a bisection whose expected size is at least $m/2$ minus a sum of arcsin inner products plus a small imbalance penalty. The paper then chooses vectors that encode each vertex and its neighborhood, so that the arcsin sum telescopes against the number of edges inside neighborhoods. This yields Theorem 1.7, the key bound for graphs with sparse neighborhoods. In Section 4 the sparse-neighborhood bound is combined with the Bondy–Simonovits even-cycle edge bound and a degeneracy labelling to get the $m/2 + \Omega(m^{(2k+1)/(2k+2)})$ excess, with Lee–Loh–Sudakov's bisection theorem handling the case of a very large maximum degree.

What would settle it

A family of $C_{2k}$-free graphs with minimum degree at least $k$ and maximum bisection at most $m/2 + o(m^{(2k+1)/(2k+2)})$ would refute the main theorem. The known extremal examples for $2k \in \{4,6,10\}$ instead match the exponent, so the open test cases are other even cycle lengths.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.5: for $k \ge 2$, a $C_{2k}$-free graph with minimum degree at least $k$ has a bisection of size at least $m/2 + \Omega(m^{(2k+1)/(2k+2)})$. The theorem is tight for $2k \in \{4,6,10\}$, inheriting the tightness examples of the max-cut theorem, and the minimum-degree condition is tight because $K_{k-1,n-k+1}$ has no $C_{2k}$, minimum degree $k-1$, and only a bounded bisection excess. The paper also proves a standalone result (Theorem 1.7): if each vertex's neighborhood spans at most $\epsilon d^{3/2}$ edges, then the graph has a bisection of size at least $m/2 + c\sum \sqrt{d_i} - 2m\sqrt{\Delta/n}$, with the error term essential in general. From this sparse-neighborhood bound, the main theorem follows by a degeneracy argument and a separate large-maximum-degree case.

Load-bearing premise

The argument depends on the sparse-neighborhood bisection bound: whenever each vertex neighborhood spans at most $\epsilon d^{3/2}$ edges, the graph has a bisection with excess at least $c$ times the sum of square roots of degrees minus an error that grows with maximum degree, and the proof needs that error to be $o(m^{(2k+1)/(2k+2)})$ in the $C_{2k}$-free regimes it considers.

Editorial extensions

If this is right

  • The $C_4$-free case gives every $C_4$-free graph with minimum degree 2 a bisection of size at least $m/2 + \Omega(m^{5/6})$, resolving Problem 1.3.
  • Avoiding a single even cycle $C_{2k}$ replaces the earlier need to forbid both $C_4$ and $C_6$, so the balanced guarantee holds in a wider class of graphs.
  • The exponent $(2k+1)/(2k+2)$ is the same as for max-cuts, so enforcing exact balance does not change the asymptotic gain.
  • The sparse-neighborhood bisection bound (Theorem 1.7) provides a general tool: any $C_{2k}$-free graph of bounded maximum degree automatically has a bisection with the Shearer-type degree-sequence gain.

Reading between the lines

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

  • The paper's vector-rounding template could transfer to other balanced partitioning problems where a random hyperplane cut is followed by a bounded-size correction, such as discrepancy-type guarantees for sparse hypergraphs.
  • The error term in Theorem 1.7, which the paper shows is essential for $K_{k,n}$, suggests that a sharp general bisection analogue of Shearer's bound would need a more refined dependence on the maximum degree; the present proof only needs it small in the ranges where $C_{2k}$-free graphs are sparse enough.
  • If the auxiliary sparse-neighborhood bound could be sharpened, the same proof strategy might push the exponent for $C_{2k}$-free graphs beyond $(2k+1)/(2k+2)$ or relax the minimum-degree condition; for now the paper establishes the exponent but not tightness outside $2k \in \{4,6,10\}$.
  • One could test the mechanism computationally on known $C_4$-free polarity graphs: a bisection of size $m/2 + \Theta(m^{5/6})$ would confirm the extremal behaviour, while a larger one would indicate room for improvement.
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

0 major / 5 minor

Summary. The paper studies max-bisections of C_{2k}-free graphs. Its main result, Theorem 1.5, states that for every integer k>=2, every C_{2k}-free graph with m edges and minimum degree at least k has a bisection of size at least m/2 + Omega(m^{(2k+1)/(2k+2)}), and that the exponent is tight when 2k is in {4,6,10}. The proof introduces Theorem 1.7, a bisection analogue of the Alon-Krivelevich-Sudakov sparse-neighborhood bound, proved with a semidefinite-programming lemma of Glock-Janzer-Sudakov and a hyperplane-rounding argument; it then applies this bound to C_{2k}-free graphs using the Bondy-Simonovits theorem, a degeneracy argument, and a two-tier degree decomposition. The case k=2 is treated separately with the Hou-Yan bound and a greedy deletion argument. The paper answers Problem 1.3 of Fan, Hou and Yu and generalizes a recent result of Hou, Wu and Zhong.

Significance. If the argument is correct, the paper solves an open problem and gives a natural bisection analogue of the classical AKS max-cut theorem. The proof is transparent and builds on published results rather than on new ad hoc assumptions; the main new tool, Theorem 1.7, is a reusable SDP-based bound for bisections of graphs with sparse neighborhoods. I checked the natural stress-test example K_{1,n-1} for Theorem 1.7: because (3) subtracts 2m*sqrt(Delta/n), the right-hand side is below m/2 for the star, so the asserted lower bound is trivially satisfied; the apparent counterexample comes from misreading the sign of the balance-loss term. No fitted parameters or target-inclusive assumptions appear in the proof. The paper is a solid contribution to the area.

minor comments (5)
  1. [3.1] In the proof of Lemma 3.2, the number of vertices moved to obtain a bisection should be the minimum required to bring the two part sizes within one; for odd n the expression ||X|-floor(n/2)| can overcount by one relative to the charge d|2|X|-n|. The intended inequality is recovered by moving max(0, |X|-ceil(n/2), floor(n/2)-|X|) vertices, so this is a local correction rather than a substantive flaw.
  2. [4] Lemma 4.2 states "If there is a positive constant c such that Delta <= c n/m^{1/(k+1)}", but the proof requires c to be the specific sufficiently small value c1^2/(3200k). The statement should be rephrased as "There exists a positive constant c such that if Delta <= c n/m^{1/(k+1)}" or as "for a sufficiently small constant c"; the applications in Theorems 4.1 and 5.2 are consistent with this reading.
  3. [2] Lemma 2.5 contains a typo: S subseteq V(H) should be S subseteq V(G). Also, G[T] may have isolated vertices, so the direct invocation of Theorem 2.3 needs a justification; the needed bound e(T)/2 follows from a random balanced partition of T, so no substantive change is required.
  4. [5] In the proof of Theorem 5.1, Theorem 2.4 is quoted for connected graphs, but G may be disconnected. The extension is standard by combining component bisections and flipping components to balance the global partition, but it should be stated explicitly.
  5. [1.2] The tightness clause in Theorem 1.5 is inherited from Theorem 1.1; the authors should briefly indicate why the extremal constructions for 2k in {4,6,10} can be chosen with minimum degree at least k.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation found; central bound follows from a new self-contained bisection lemma plus external extremal theorems.

full rationale

The proof of Theorem 1.5 is structured as two independent regimes: Theorem 4.1 for k≥3 and Theorem 5.1 for k=2. Both reduce to Lemma 4.2, whose proof is a new degeneracy argument relying only on the Bondy–Simonovits theorem and on the paper's own Theorem 1.7. Theorem 1.7 is proved in Section 3 from Lemma 3.2, and Lemma 3.2 is proved by a self-contained probabilistic calculation involving a random bipartition followed by a balancing move; it invokes only the external Glock–Janzer–Sudakov semidefinite lemma as inspiration, not as a hidden form of the target result. No fitted parameter is renamed as a prediction, and no step assumes the bisection bound being derived. The only author-overlap citation used inside a proof is Theorem 2.4 of Hou and Yan, which is a published external theorem applied only in the C4-free case when m≤n^{6/5}; it handles a boundary regime and the main argument does not reduce to it. The alleged star counterexample to Theorem 1.7 misreads the sign of the subtracted term; in any case, that would be a correctness issue, not circularity. The derivation chain is therefore self-contained apart from one minor non-load-bearing self-citation.

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

The proof uses several prior theorems as black boxes and one new SDP lemma. No free parameters are fitted to data, and no invented entities appear. The only substantive caveat is the incorrect balance-loss term in Theorem 1.7, which is a statement error rather than an axiom.

assumptions (5)
  • standard math Bondy-Simonovits theorem: every C_{2k}-free graph on n vertices has at most 100k n^{1+1/k} edges.
    Invoked in Lemma 4.2 and Claim 4.3 to bound m and to show degeneracy; this prior theorem is used without proof.
  • standard math Naor-Verstraete theorem: every C_{2k}-free bipartite graph with parts of sizes a at most b has the stated edge bound.
    Used in Claim 4.3 to upper-bound e(A,B) and in Theorem 5.2.
  • standard math Lee-Loh-Sudakov bisection theorem: every graph without isolated vertices has a bisection of size at least m/2 + (n - max(n/3, Delta-1))/4.
    Used in Lemma 2.5 and on G[T] in Theorem 4.1.
  • standard math Hou-Yan theorem: every connected C4-free graph with minimum degree at least 2 has a bisection of size at least m/2 + (n-1)/4.
    Used as the sparse case m at most n^{6/5} in Theorem 5.1.
  • standard math Glock-Janzer-Sudakov SDP cut lemma (Lemma 3.1): random halfspace cuts achieve m/2 - (1/pi) times the sum of arcsin terms.
    The bisection lemma 3.2 is a new variant of this prior lemma; the proof uses standard random vector techniques.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Max-Bisections of graphs without even cycles." pith.science (2026). https://pith.science/paper/5RMPGGJ6

@misc{pith2026250521694,
  author       = {Pith},
  title        = {Pith review of: Max-Bisections of graphs without even cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5RMPGGJ6}},
  note         = {Machine review of arXiv:2505.21694}
}
abstract

For an integer $k\ge 2$, let $G$ be a graph with $m$ edges and without cycles of length $2k$. The pivotal Alon-Krivelevich-Sudakov Theorem on Max-Cuts states that $G$ has a bipartite subgraph with at least $m/2+\Omega(m^{(2k+1)/(2k+2)})$ edges. In this paper, we present a bisection variant of it by showing that if $G$ has minimum degree at least $k$, then $G$ has a balanced bipartite subgraph with at least $m/2+\Omega(m^{(2k+1)/(2k+2)})$ edges. It not only answers a problem of Fan, Hou and Yu in full generality but also enhances a recent result given by Hou, Wu and Zhong. Our approach hinges on a key bound for bisections of graphs with sparse neighborhoods concerning the degree sequence. The result is inspired by the celebrated approximation algorithm of Goemans and Williamson and appears to be worthy of future exploration.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 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 ´as, M. Krivelevich, B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B 88 (2003) 329–346

    work page 2003

  3. [3]

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

    work page 2005

  4. [4]

    Bollob ´as, A

    B. Bollob ´as, A. D. Scott, Problems and results on judicious partitions, Random Structures Algorithms 21 (2002) 414–430

    work page 2002

  5. [5]

    Bondy, M

    A. Bondy, M. Simonovits, Cycles of even length in graphs, J. Combin. Theory Ser. B 16 (1974) 97–105

    work page 1974

  6. [6]

    Carlson, A

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

    work page 2021

  7. [7]

    C. S. Edwards, Some extremal properties of bipartite subgraphs, Canad. J. Math. 3 (1973) 475–485

    work page 1973

  8. [8]

    C. S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in Proceedings of Second Czechoslovak Symposium on Graph Theory (1975) 167–181

    work page 1975

Show all 34 references
  1. [9]

    Erd ˝os, On even subgraphs of graphs, Mat

    P. Erd ˝os, On even subgraphs of graphs, Mat. Lapok 18 (1967) 283–288. 14

    1967

  2. [10]

    Erd ˝os, Problem and results in graph theory and combinatorial analysis, in: Graph The- ory and Related Topics (1979) 153–163

    P. Erd ˝os, Problem and results in graph theory and combinatorial analysis, in: Graph The- ory and Related Topics (1979) 153–163

    1979

  3. [11]

    Erd ˝os, A

    P. Erd ˝os, A. Gy´arf´as, Y . Kohayakawa, The size of the largest bipartite subgraphs,Discrete Math. 177 (1997) 267–271

    1997

  4. [12]

    G. Fan, J. Hou, X. Yu, Bisections of graphs without short cycles, Comb. Probab. Comput. 27 (2018) 44–59

    2018

  5. [13]

    J. Fox, Z. Himwich, N. Mani, Making an H-free graph k-colorable, J. Graph Theory 102 (2023) 234–261

    2023

  6. [14]

    Glock, O

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

    2023

  7. [15]

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

    1995

  8. [16]

    J. Hou, S. Wu, On bisections of graphs without complete bipartite graphs,J. Graph Theory 98 (2021) 630–641

    2021

  9. [17]

    J. Hou, S. Wu, Y . Zhong, Max-Bisections of graphs without perfect matching, arXiv:2411.11013 (2024)

    2024 arXiv

  10. [18]

    J. Hou, J. Yan, Max-bisections of H-free graphs, Discrete Math. 343 (2020) 111590

    2020

  11. [19]

    Q. Hu, B. Xu, Maximum bisections of graphs without adjacent quadrilaterals, Graphs Combin. 41 (2025) Paper No. 29, 29 pp

    2025

  12. [20]

    Y . Ji, J. Ma, J. Yan, X. Yu, On problems about judicious bipartitions of graphs,J. Combin. Theory Ser. B 139 (2019) 230–250

    2019

  13. [21]

    J. Jin, B. Xu, Bisections of graphs without K2,l, Discrete Appl. Math. 259 (2019) 112–118

    2019

  14. [22]

    C. Lee, P. Loh, B. Sudakov, Bisections of graphs, J. Combin. Theory Ser. B 103 (2013) 599–629

    2013

  15. [23]

    J. Lin, Q. Zeng, Maximum bisections of graphs without short even cycles, J. Combin. Theory Ser. A 180 (2021) 105404

    2021

  16. [24]

    A. Naor, J. Verstra ¨ete, A note on bipartite graphs without 2k-cycles, Comb. Probab. Com- put. 14 (2005) 845–849

    2005

  17. [25]

    Poljak, Zs

    S. Poljak, Zs. Tuza, Bipartite subgraphs of triangle-free graphs, SIAM J. Discrete Math. 7 (1994) 307–313

    1994

  18. [26]

    M. Rao, J. Hou, Q. Zeng, Maximum bisections of graphs without cycles of length 4, Discrete Math. 345 (2022) Paper No. 112914, 11 pp

    2022

  19. [27]

    R ¨aty, I

    E. R ¨aty, I. Tomon, Bisection width, discrepancy, and eigenvalues of hypergraphs, arXiv:2409.15140 (2024). 15

    2024 arXiv

  20. [28]

    J. B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Struct. Alg. 3 (1992) 223–226

    1992

  21. [29]

    S. Wu, X. Xiong, Maximum bisections of graphs with girth at least six, Graphs Combin. 40 (2024) Paper No. 113, 17 pp

    2024

  22. [30]

    S. Wu, Y . Zhong, Maximum bisections of graphs without cycles of length four and five, Discrete Appl. Math. 360 (2025) 209–220

    2025

  23. [31]

    B. Xu, J. Yan, X. Yu, A note on balanced bipartitions, Discrete Math. 310 (2010) 2613– 2617

    2010

  24. [32]

    B. Xu, J. Yan, X. Yu, Balanced judicious bipartitions of graphs,J. Graph Theory63 (2010) 210–225

    2010

  25. [33]

    B. Xu, X. Yu, On judicious bisections of graphs, J. Combin. Theory Ser. B 106 (2014) 30–69

    2014

  26. [34]

    Q. Zeng, J. Hou, Maximum cuts of graphs with forbidden cycles, Ars Math. Contemp. 15 (2018) 147–160. 16

    2018

Pith tools

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