{"id":"76dfbbd4-c439-49d4-8de1-c68229609fc5","arxiv_id":"2411.11013","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A {C4,C6}-free graph with minimum degree at least 2 has a bisection of size at least m/2 + Omega(sum sqrt(d(v))), confirming a conjecture of Lin and Zeng.","lead":"This paper proves that every connected graph with no 4- or 6-cycles and with every vertex having at least two edges has a bisection (a split into two nearly equal parts) with noticeably more than half its edges crossing the cut. This confirms an open conjecture by Lin and Zeng and removes the need for a perfect matching, replacing it with a simple minimum degree condition.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Odd-order reduction in §3 is false for C5 and unproved in general; Theorem 1.5 is not established for odd n.","rationale":"The paper's central claim is Theorem 1.5, and its proof depends on a randomized even-order lemma. The odd/even reduction is the only mechanism to cover odd n. Since the asserted reduction fails on C5, the proof as written cannot be accepted. The theorem may be true, and the gap may be repairable, but the manuscript does not supply the needed argument. The reader's REJECT verdict is therefore appropriate: a load-bearing step in the proof of the main theorem is asserted without proof and is false as stated. I agree with the reader's identification of the weakest assumption. No formal verification or independent computational evidence offsets this gap.","tokens_in":19591,"tokens_out":13706,"duration_ms":147785,"concrete_test":"Test the reduction directly: for every connected {C4,C6}-free graph with odd n, minimum degree at least 2, and n ≤ 11 (or up to computational limits), check whether there is a pair u,v with no common neighbor and no path of length 4 between u and v. C5 should fail this test; if any other graph also fails, the Section 3 reduction cannot be repaired by the proposed vertex addition. For a sharper analytic check, attempt to prove the existence of such a pair for all odd n ≥ 7; a single counterexample would definitively show the proof of Theorem 1.5 is incomplete.","verdict_should_be":"REJECT","load_bearing_attack":"In Section 3, after assuming Σ√d_i > 8(n−1), the proof says '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.' This is the only bridge from odd to even order, and Lemma 2.1 plus Algorithm 1 are stated only for even n. The assertion is false for C5: if x is joined to adjacent vertices of C5, the length-4 path between them together with x forms a C6; if x is joined to non-adjacent vertices, the length-2 path through their common neighbor forms a C4. Hence no choice of two vertices avoids both C4 and C6. Moreover, no argument is given for larger odd graphs, so the proof does not cover odd-order inputs. A repair would require either a separate odd-order argument or a proof that every odd connected {C4,C6}-free min-degree-2 graph, beyond finitely many exceptions, has a pair of vertices with no 2-path and no 4-path, plus an accounting of the up-to-two cut edges lost when x is removed from the bisection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19779,"tokens_out":21681,"duration_ms":228480,"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":[{"comment":"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.","section":"Section 3, dense case after “Suppose ∑√di > 8(n−1)”"},{"comment":"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.","section":"Section 3, Eq. (6)"}],"minor_comments":[{"comment":"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”.","section":"Abstract and Section 2.1"},{"comment":"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.","section":"Appendix, proof of Lemma 2.6"},{"comment":"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.","section":"Section 3, inequality after Eq. (8)"}],"recommendation":"major_revision","confidential_remarks":"The even-order part of the paper is a substantial and careful piece of work, and the paper fits the scope of the journal. My main concern is the odd-order bridge in Section 3: it is a genuine load-bearing gap, not a presentation issue. If the authors can supply a correct odd-order argument—or explicitly restrict the theorems to even-order graphs and state the resulting limitation—the remaining claims appear credible. I do not see a circularity or attribution problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The even-order case looks like a genuine advance and probably works, but the odd-order bridge is asserted, not proved, so the main theorem falls short as written. The new content is real: Theorem 1.5 replaces the perfect-matching hypothesis with minimum degree 2 in {C4,C6}-free graphs, confirms Lin-Zeng's conjecture in the C2k-free corollary, and the proof adapts the perfect-matching method to quasi-perfect matchings. The case analysis in Lemma 2.1 is intricate and appears careful; the four-case division with the Phi functions is serious work. I agree with the reader that the result is new and not a routine application of earlier theorems.\n\nThe soft spot is exactly where the reader puts it. In Section 3, after the sparse case is dispatched, the proof says 'We may assume n is even, since otherwise we can add a new vertex x and connect x to two vertices avoiding C4 and C6.' That is the only bridge from odd to even order, and no proof is given. The C5 example in the stress-test note is not a counterexample to the theorem as a whole, because C5 satisfies n >= (1/8) sum sqrt(d_i) + 1 and falls into the sparse case handled by Theorem 2.2. But that does not repair the gap: the reduction is used in the dense case sum sqrt(d_i) > 8(n-1), and nothing in the paper shows that every odd connected {C4,C6}-free min-degree-2 graph in that regime has a pair of vertices with no 2-path and no 4-path. Since Lemma 2.1 and Algorithm 1 are stated only for even n, the proof for odd n is simply missing. A fix needs either a separate odd-order argument or a lemma producing such a pair plus an accounting of the cut edges lost when x is removed from the bisection. That is load-bearing.\n\nA secondary gripe: the construction of M3 says 'randomly pair' but then relies on deterministic structural facts such as k23 <= 1. These may hold for every maximal choice, but the text does not say so explicitly. This is minor compared with the odd-order problem.\n\nThe citation pattern is honest: the paper leans on Lin-Zeng and on Wu-Xiong and Wu-Zhong lemmas, which are published results, not circular. The appendix computation for Lemma 2.6 is plausible.\n\nThis paper is for extremal graph theory people working on max-bisection in H-free graphs. It deserves a serious referee, but the referee should insist on a real odd-order argument before the main theorem is accepted. My own verdict would be major revision, not flat rejection, because the even-order machinery is strong and the gap may be fixable.","headline":"Strong even-order proof, but the odd-order reduction is a real gap: Theorem 1.5 is not yet established for odd n.","tokens_in":20343,"tokens_out":4466,"would_cite":false,"duration_ms":49201,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C07","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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)})$.","keywords":["max-bisection","forbidden even cycles","minimum degree at least 2","quasi-perfect matching","random bisection algorithm","degree-sum lower bound","C2k-free graphs","degeneracy argument"],"falsifier":"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.","tokens_in":19360,"feed_emoji":"⚖️","tokens_out":12446,"duration_ms":123258,"temperature":0.7,"pith_summary":"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.","feed_headline":"Graphs without 4- or 6-cycles get a guaranteed surplus bisection","feed_subtitle":"Minimum degree at least 2 replaces the perfect-matching condition, settling the open problem.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the perfect-matching predecessor, the two-stage randomization scheme, and the open problem that the paper settles.","marker":"[20]"},{"why":"gives the original degree-sum lower bound for triangle-free maximum cuts, whose form the paper extends to bisections.","marker":"[26]"},{"why":"provides the $C_4$-free bisection bound used for the sparse case of Theorem 1.5.","marker":"[16]"},{"why":"supplies the extremal bound on edges in $C_{2k}$-free graphs used to force degeneracy in the proof of Theorem 1.6.","marker":"[6]"},{"why":"cited to justify that the key probability proposition survives when the graph has no perfect matching.","marker":"[24]"},{"why":"supplies the binomial-tail inequality of Lemma 2.4 used in the case analysis of Lemma 2.1.","marker":"[28]"},{"why":"supplies the binomial-tail inequality of Lemma 2.5 used to lower-bound the stability probability.","marker":"[29]"},{"why":"introduces the degeneracy argument that converts a degree-sum bound into an exponent-of-$m$ bound in Theorem 1.6.","marker":"[1]"}],"fun_headline_variants":["Minimum degree 2 replaces perfect matching for surplus bisections","No 4- or 6-cycles: large bisections from degree 2+","Surplus bisection without perfect matching? Degree 2 suffices","Conjecture confirmed: cycle-free graphs have large bisections"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Minimum degree 2 replaces perfect matching for surplus bisections","No 4- or 6-cycles: large bisections from degree 2+","Surplus bisection without perfect matching? Degree 2 suffices","Conjecture confirmed: cycle-free graphs have large bisections"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000716,"raw_usage":{"total_tokens":3246,"prompt_tokens":1000,"completion_tokens":2246,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2169}},"tokens_in":616,"tokens_out":2246,"duration_ms":17738,"temperature":1.0,"reasoning_tokens":2169,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:02:06.720143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"cited to justify that the key probability proposition survives when the graph has no perfect matching."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the perfect-matching predecessor, the two-stage randomization scheme, and the open problem that the paper settles."},{"cited_title":"Shearer, A note on bipartite subgraphs of triangle-free gr aphs, Random Struc- tures Algorithms 3 (1992) 223–226","cited_arxiv_id":null,"evidence_quote":"gives the original degree-sum lower bound for triangle-free maximum cuts, whose form the paper extends to bisections."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the $C_4$-free bisection bound used for the sparse case of Theorem 1.5."},{"cited_title":"A Bondy, M","cited_arxiv_id":null,"evidence_quote":"supplies the extremal bound on edges in $C_{2k}$-free graphs used to force degeneracy in the proof of Theorem 1.6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the binomial-tail inequality of Lemma 2.4 used in the case analysis of Lemma 2.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the binomial-tail inequality of Lemma 2.5 used to lower-bound the stability probability."},{"cited_title":"Alon, Bipartite subgraphs, Combinatorica 16 (1996) 301–311","cited_arxiv_id":null,"evidence_quote":"introduces the degeneracy argument that converts a degree-sum bound into an exponent-of-$m$ bound in Theorem 1.6."}],"review_version":1}