Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Max-Bisections of graphs without perfect matching

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A connected $\{C_4,C_6\}$-free graph with minimum degree at least 2 admits a bisection of size $m/2+\Omega(\sum_v\sqrt{d(v)})$.

desk verdict Strong even-order proof, but the odd-order reduction is a real gap: Theorem 1.5 is not yet established for odd n. read the letter →

arxiv 2411.11013 v1 pith:XZPRIODO submitted 2024-11-17 math.CO

Jianfeng Hou , Shufei Wu , Yuanyuan Zhong This is my paper · ORCID
classification math.CO MSC 05C0705C75
keywords max-bisectionforbiddenevencyclesminimumdegreeatleast2quasi-perfectmatchingrandombisectionalgorithmdegree-sumlowerboundC2k-freegraphsdegeneracyargument
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

A bisection is a bipartition whose two parts differ in size by at most 1, and its size is the number of crossing edges. This paper proves that every connected graph with no 4-cycle or 6-cycle, minimum degree at least 2, and $m$ edges has a bisection with at least $m/2+\Omega(\sum_{v\in V(G)}\sqrt{d(v)})$ crossing edges. Previously such a degree-sum bound was known only when the graph had a perfect matching; the paper replaces that condition by the minimum degree condition. It also derives the corollary that, for any fixed $k\ge 3$, a connected $\{C_4,C_6,C_{2k}\}$-free graph with minimum degree at least 2 has a bisection of size $m/2+\Omega(m^{(2k+1)/(2k+2)})$, settling the open problem posed in the cited literature. The result matters because guaranteed-surplus bisections are the balanced analogue of maximum-cut bounds, and the new hypothesis is much easier to check than the existence of a perfect matching.

What carries the argument

The load-bearing device is a quasi-perfect matching $M$, meaning a maximum matching together with a pairing of the leftover independent vertices into $n/2$ matched pairs, combined with a two-stage random bisection algorithm (Algorithm 1). In the first stage each matched pair is oriented randomly; in the second stage pairs classified as active, i.e. those for which $\sigma(vv')\ge 0$ fails, are re-randomized. Lemma 2.1 is the engine: for a $\{C_4,C_6\}$-free graph with even order and minimum degree at least 2, one can choose $M$ so that each edge $uv$ that is the unique edge between its matched pairs has crossing probability at least $1/2+\epsilon(\frac{1}{\sqrt{d(u)+d(u')}}+\frac{1}{\sqrt{d(v)+d(v')}})$. The proof controls the dependence between the two matched pairs by listing seven interaction types, encoding them by counts $k_1,\dots,k_6$, and reducing the probability calculation to binomial-tail expressions $\Phi(t_1,t_2)$. The four possible values of $k_1+k_2+k_3-k_4$ are handled separately using Lemmas 2.3–2.6 and Vandermonde's convolution formula.

What would settle it

Check all connected $\{C_4,C_6\}$-free graphs with minimum degree at least 2 and odd order up to, say, 12 vertices by exact maximum-bisection search; any instance with maximum bisection below $m/2+\xi\sum_v\sqrt{d(v)}$ for the paper's constant would refute Theorem 1.5. A smaller, immediate check is the reduction itself: on $C_5$ any added vertex joined to two old vertices completes a 4-cycle or a 6-cycle, so a corrected proof must handle odd $n$ directly rather than by that reduction.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central content is Theorem 1.5: every connected $\{C_4,C_6\}$-free graph with degree sequence $d_1\ge d_2\ge\cdots\ge d_n\ge 2$ admits a bisection of size at least $m/2+\xi\sum_{i=1}^n\sqrt{d_i}$ for an absolute constant $\xi>0$. The proof constructs a quasi-perfect matching, randomizes each matched pair independently, then re-randomizes active pairs, and shows that every non-matching edge which is the unique connection between its two matched pairs is cut with probability at least $1/2+\epsilon(1/\sqrt{d(u)+d(u')}+1/\sqrt{d(v)+d(v')})$. Summing these per-edge gains over a carefully chosen matching yields the degree-sum bound. Section 4 converts this into the $C_{2k}$-free corollary by a degeneracy argument, and the paper notes that both bounds are tight up to the values of the constants in the relevant regimes.

Load-bearing premise

The load-bearing premise is that an odd-order connected $\{C_4,C_6\}$-free graph with minimum degree at least 2 can always be made even by adding one new vertex joined to two old vertices without creating a 4-cycle or 6-cycle; this reduction is asserted in Section 3, and on $C_5$ it is not available, so the proof as written does not cover every odd-order instance of the theorem.

Editorial extensions

If this is right

  • The theorem gives a bisection of size at least $m/2+\xi\sum_v\sqrt{d(v)}$ in every connected $\{C_4,C_6\}$-free graph with minimum degree at least 2, without any assumption about a perfect matching.
  • For any fixed $k\ge 3$, a connected $\{C_4,C_6,C_{2k}\}$-free graph with minimum degree at least 2 has a bisection of size $m/2+\Omega(m^{(2k+1)/(2k+2)})$, resolving Problem 1.4 of the cited literature.
  • The minimum degree condition is shown to be necessary: a star has no large balanced cut, so one cannot simply drop the restriction.
  • The paper's tightness remarks indicate that the exponent $(2k+1)/(2k+2)$ cannot be improved in general for the relevant ranges of parameters.

Reading between the lines

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

  • Extension: the interaction-type catalogue in Lemma 2.1 is the main place where $\{C_4,C_6\}$-freeness enters, so the same quasi-perfect matching method should adapt to other even-cycle-free families whenever the corresponding dependency graph can be classified.
  • Extension: the proof's split between a sparse case using an existing $C_4$-free bound and a dense case using the matching argument suggests that a unified explicit value of $\xi$ could be extracted by optimizing the crossover, something the paper does not attempt.
  • Extension: the odd-to-even reduction asserted in Section 3 is not automatic, since on $C_5$ any added vertex joined to two old vertices creates a 4-cycle or 6-cycle; a complete proof of Theorem 1.5 as stated must therefore treat odd order separately.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper claims that every connected {C4, C6}-free graph with n vertices, m edges and minimum degree at least 2 admits a bisection of size at least m/2 + ξ Σ√d_i (Theorem 1.5), and derives from this a confirmation of a conjecture of Lin and Zeng for {C4, C6, C2k}-free graphs (Theorem 1.6). The proof combines a sparse case handled by an earlier theorem of Hou and Yan with a dense case based on a two-stage random bisection algorithm (Algorithm 1) and a quasi-perfect matching lemma (Lemma 2.1). The dense case requires a detailed stability analysis of matching pairs, carried out in Section 5 through several case distinctions and auxiliary inequalities.

Significance. If fully correct, the paper would replace the perfect matching condition in Lin and Zeng's theorem by a minimum degree condition, confirming a conjecture and extending Shearer-type bisection bounds to a broad family of graphs without perfect matchings. The even-order dense case is a substantial technical achievement: the quasi-perfect matching construction, the reduction of stability to binomial estimates, and the case analysis in Lemma 2.1 are all nontrivial and appear carefully developed. The main weakness is the odd-order reduction in Section 3, which is currently unproved and, as stated, false in a simple example. Because Theorem 1.5 is claimed for all n, this gap directly affects the main result and its corollary.

major comments (2)
  1. [Section 3, dense case after “Suppose ∑√di > 8(n−1)”] Theorem 1.5 is not established for odd n. The sentence “We may assume that n is even, since otherwise, we can add a new vertex x in G and connect x to two vertices in G avoiding C4 and C6” is the only bridge from odd to even order, and it is neither proved nor true as stated. In C5, if x is joined to adjacent vertices, the 4-path between them together with x forms a C6; if x is joined to non-adjacent vertices, the 2-path between them together with x forms a C4. Thus no choice of two vertices works for C5. The proof would need a separate argument showing that in the regime ∑√di > 8(n−1) such a pair exists, but none is given. Since Lemma 2.1 and Algorithm 1 are stated only for even n, the dense case of Theorem 1.5 is not covered for odd n, and Theorem 1.6 inherits this gap because its proof invokes Theorem 1.5 for all n.
  2. [Section 3, Eq. (6)] Even if a suitable two-vertex set existed, the proof does not convert the bisection found on the augmented even graph into a bisection of the original odd graph with the claimed bound. The expectation bound in Eq. (6) is computed for the augmented graph with m+2 edges and modified degrees. Deleting the degree-two vertex x from a part of that bisection leaves a valid bisection of G, but the cut size decreases by up to two edges, and the extra +1 in (m+2)/2 does not automatically compensate for this loss. The authors would need to bound the expected number of cut edges incident to x, or supply a direct odd-order version of Lemma 2.1; neither is present.
minor comments (3)
  1. [Abstract and Section 2.1] There are typographical errors: “t hat” in the abstract and “Algorimth 1” in the statement of Lemma 2.1 should be “that” and “Algorithm 1”.
  2. [Appendix, proof of Lemma 2.6] The line “hi(x) is an increasing function” appears to refer to f_i(x) or B(·, ·), and “For convince” should read “For convenience”; the proof would be easier to follow if these were corrected.
  3. [Section 3, inequality after Eq. (8)] The bound ∑√(k_i+2) < √2 n is stated without explanation; a short justification using Cauchy–Schwarz and the preceding bound |E2| ≤ n would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main derivation uses an independently proved Lemma 2.1 plus external published technical lemmas; cited prior work by the authors does not assume the target theorem.

full rationale

The paper's derivation chain is not circular. Theorem 1.5 is split into a sparse case handled by the external Hou-Yan C4-free bisection theorem and a dense case reduced to Lemma 2.1, whose proof in Section 5 is carried out through a quasi-perfect matching construction and the two-stage random algorithm. The cited Lemmas 2.3-2.5 and the Rao-Hou-Zeng adaptation of Lin-Zeng's probability formula (Proposition 1) are technical binomial or matching statements from prior published work; none of them states or assumes Theorem 1.5 or the Lin-Zeng conjecture being confirmed, so the self-citations are not circular even though some are load-bearing. Lemma 2.6 is proved in the appendix. The only substantial weakness detected is the Section 3 assertion that an odd-order graph can be made even by adding a vertex adjacent to two vertices while avoiding C4 and C6; this is false for C5 and leaves odd n unproved, but that is a correctness gap rather than a circular reduction. No fitted parameter is relabeled as a prediction, no uniqueness theorem is imported from the authors' own work to force a choice, and no known result is merely renamed.

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

The paper introduces no new postulated entities. The free parameters are universal constants in the proof, not empirical fits. The axioms are standard results from extremal graph theory and earlier published lemmas; several are self-cited (e.g., Wu-Xiong, Wu-Zhong, Hou-Yan) but they are independent results, not the target claim.

free parameters (3)
  • xi = xi = min{1/32, epsilon/2}
    Small universal constant chosen so that both the sparse-case bound (Theorem 2.2) and the dense-case bound (Lemma 2.1) exceed m/2 + xi * sum sqrt(d(v)). It is not fitted to data.
  • epsilon = exists via Lemma 2.1
    A small constant whose existence is guaranteed by the key probabilistic lemma; its value is never computed, and it is not fitted to data.
  • c(k) = c(k) = xi / sqrt(b), with b > 2c (Bondy-Simonovits constant)
    Constant in Theorem 1.6, depending on k; chosen sufficiently small to make the degenerate argument work.
assumptions (5)
  • standard math Bondy-Simonovits theorem on the maximum number of edges in a C_{2k}-free graph
    Used in Section 4 to bound e(G') and choose b so that G is (D-1)-degenerate.
  • domain assumption Hou-Yan Theorem 2.2: every connected C4-free graph with minimum degree at least 2 has a bisection of size at least m/2 + (n-1)/4
    Used in Section 3 for the sparse case.
  • domain assumption Lin-Zeng Proposition 1, relating the probability that an edge crosses the bisection to the stability probabilities p_uv and q_uv
    Used in Section 5; the paper asserts the proof remains valid without a perfect matching, but relies on this prior proposition.
  • standard math Lemma 2.3 (Lin-Zeng), Lemma 2.4 (Wu-Xiong), Lemma 2.5 (Wu-Zhong) on binomial probability bounds
    Used throughout Section 5 to lower bound the differences of Phi terms.
  • standard math Vandermonde's convolution formula
    Used in Section 5 to evaluate the sums over binomial coefficients in the stability probability.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Max-Bisections of graphs without perfect matching." pith.science (2026). https://pith.science/paper/XZPRIODO

@misc{pith2026241111013,
  author       = {Pith},
  title        = {Pith review of: Max-Bisections of graphs without perfect matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XZPRIODO}},
  note         = {Machine review of arXiv:2411.11013}
}
abstract

A bisection of a graph is a bipartition of its vertex set such that the two resulting parts differ in size by at most 1, and its size is the number of edges that connect vertices in the two parts. The perfect matching condition and forbidden even cycles subgraphs are essential in finding large bisections of graphs. In this paper, we show that the perfect matching condition can be replaced by the minimum degree condition. Let $C_{\ell}$ be a cycle of length $\ell$ for $\ell\ge 3$, and let $G$ be a $\{C_4, C_6\}$-free graph with $m$ edges and minimum degree at least 2. We prove that $G$ has a bisection of size at least $m/2+\Omega\left(\sum_{v\in V(G)}\sqrt{d(v)}\right)$. As a corollary, if $G$ is also $C_{2k}$-free for $k\ge3$, then $G$ has a bisection of size at least $m / 2+\Omega\left(m^{(2 k+1) /(2 k+2)}\right)$, thereby confirming a conjecture proposed by Lin and Zeng [J. Comb. Theory A, 180 (2021), 105404].

Figures

Figures reproduced from arXiv: 2411.11013 by the authors.

Figure 1
Figure 1. Four kinds quasi-triangles Combining (3), (4) and (5), E (e (V0, V1)) ≥ |E(M)| + |E1| 2 + |E2| 2 + ǫ X uv∈E1 ∇uv ≥ m 2 + ǫ X uv∈E1 ∇uv. (6) To complete the proof, we need bound P uv∈E1 ∇uv. By the C4-freeness of G, each pair in M is contained in at most one quasi-triangle, which implies that |E2| ≤ 2 ∗ n/2 = n. (7) For ei = uu′ ∈ M, let ki denote the number of edges in E2 which are incident with u or u ′ . Then by (… view at source ↗
Figure 2
Figure 2. Vertices in S(P) The labels of vertices from different types (S1)-(S7) are pairwise independent. For P = u ′uvv′ , let S(P) be the set of vertices of types (S1)-(S7). Clearly, vertices in S(P) will affect the stability of uu′ and vv′ . We illustrate this influence is small by considering the number of vertices in S(P). For i ∈ [6], let ki be the number of vertices (or pairs in (S1), (S2) and (S6)) of type (Si). More… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Max-Bisections of graphs without even cycles

    math.CO 2025-05 conditional novelty 8.0 of 10

    Every C_{2k}-free graph with minimum degree at least k has a balanced bipartition with at least m/2 + Omega(m^{(2k+1)/(2k+2)}) edges.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    Alon, Bipartite subgraphs, Combinatorica 16 (1996) 301–311

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

    work page 1996

  2. [2]

    N. Alon, B. Bollob´ as, M. Krivelevich, B. Sudakov, Maximum cuts an d judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B 88 (2003) 329–346. 2, 8

    work page 2003

  3. [3]

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

    work page 2005

  4. [4]

    Bollob´ as, A.D

    B. Bollob´ as, A.D. Scott, Better bounds for max cut, Contenpo rary Combina- torics 10 (2002) 185–246. 2

    work page 2002

  5. [5]

    Bollob´ as, A.D

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

    work page 2002

  6. [6]

    A Bondy, M

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

    work page 1974

  7. [7]

    Edwards, Some extremal properties of bipartite graphs, C anad

    C.S. Edwards, Some extremal properties of bipartite graphs, C anad. J. Math. 25 (1973) 475–485. 8, 21

    work page 1973

  8. [8]

    Edwards, An improved lower bound for the number of edges in a largest bi- partite subgraph, Proceedings of the Second Czechoslovak Symp osium on Graph Theory (1975) 167–181

    C.S. Edwards, An improved lower bound for the number of edges in a largest bi- partite subgraph, Proceedings of the Second Czechoslovak Symp osium on Graph Theory (1975) 167–181. 2

    work page 1975

Show all 35 references
  1. [9]

    Erd˝ os, On even subgraphs of graphs, Mat

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

    1967

  2. [10]

    Erd˝ os, Problem and results in graph theory and combinator ial analysis, in: Graph Theory and Related Topics (1979) 153–163

    P. Erd˝ os, Problem and results in graph theory and combinator ial analysis, in: Graph Theory and Related Topics (1979) 153–163. 2

    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. 2

    1997

  4. [12]

    G. Fan, J. Hou, X. Yu, Bisections of graphs without short cycle s, Combin. Probab. Comput. 27 (2018) 44–59. 2

    2018

  5. [13]

    Glock, O

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

    2023

  6. [14]

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

    2021

  7. [15]

    J. Hou, S. Wu, G. Yan, On bisections of directed graphs, Europ ean J. Combin. 63 (2017) 44–58. 21

    2017

  8. [16]

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

    2020

  9. [17]

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

    2019

  10. [18]

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

    2019

  11. [19]

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

    2013

  12. [20]

    J. Lin, Q. Zeng, Maximum bisections of graphs without short eve n cycles, J. Combin. Theory Ser. A 180 (2021) 105404. 2, 3, 4, 5, 9, 12, 21

    2021

  13. [21]

    G. Liu, J. Ma, C. Zu, Optimal bisections of directed graphs, Ran dom Structures Algorithms 64 (2024) 138–153. 2

    2024

  14. [22]

    J. Ma, T. Yang, Decomposing C4-free graphs under degree constraints, J. Graph Theory 90 (2019) 13–23. 2

    2019

  15. [23]

    Poljak, Zs

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

    1994

  16. [24]

    M. Rao, J. Hou, Q. Zeng, Maximum bisections of graphs without c ycles of length 4, Discrete Math. 245 (2022) 112914. 9

    2022

  17. [25]

    Scott, Judicious partitions and related problems, Surveys in Combinatorics 327 (2005) 95–117

    A.D. Scott, Judicious partitions and related problems, Surveys in Combinatorics 327 (2005) 95–117. 2

    2005

  18. [26]

    Shearer, A note on bipartite subgraphs of triangle-free gr aphs, Random Struc- tures Algorithms 3 (1992) 223–226

    J. Shearer, A note on bipartite subgraphs of triangle-free gr aphs, Random Struc- tures Algorithms 3 (1992) 223–226. 2, 3

    1992

  19. [27]

    S. Wu, J. Hou, Graph partitioning: an updated survey, AKCE In t. J. Graphs Comb. 20 (2023) 9–19. 2

    2023

  20. [28]

    S. Wu, X. Xiong, Maximum bisection of graphs with girth at least six , Graphs Combin. 40 (2024) 113. 5

    2024

  21. [29]

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

    2025

  22. [30]

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

    2010

  23. [31]

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

    2010

  24. [32]

    B. Xu, X. Yu, Triangle-free subcubic graphs with minimum bipartit e density, J. Combin. Theory Ser. B 98 (2008) 516–537

    2008

  25. [33]

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

    2014

  26. [34]

    Q. Zeng, J. Hou, Bipartite subgraphs of H-free graphs, Bull. Aust. Math. Soc. 96 (2017) 1–13. 2 23

    2017

  27. [35]

    Q. Zeng, J. Hou, Maximum cuts of graphs with forbidden cycles, Ars Math. Contemp. 15 (2018) 147–160. 2 2 Appendix Proof of Lemma 2.6. We prove Lemma 2.6 using a coarse way. For convenience, let Λ( t) :=Φ( t − 2, t + 2) + Φ( t + 2, t − 2) + Φ( −t − 4, −t) + Φ( −t, −t − 4) −Φ( t...

    2018

Pith tools

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