{"id":"a9f1325c-68dd-48ef-93bb-359178374524","arxiv_id":"2608.01059","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The join-ear equality does not extend beyond graphic matroids, but the two parameters stay within a factor of 6 for all regular matroids.","lead":"This paper shows that Frank's theorem equating joins with ear-decomposition parameters in graphic matroids fails for general matroids, including cographic ones, and that computing the join parameter is NP-hard there. It still proves a constant-factor analogue for regular matroids: η(M) ≤ 6μ(M) − 2.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Regular-matroid bound rests on an unproved external lower bound in Seymour's decomposition (Thm 2.7(iv)(c)); the 3-sum induction step fails if that bound does not hold.","rationale":"I read the central proof of Theorem 5.9 in detail. The induction is otherwise sound: the 2-sum and 3-sum lemmas correctly construct a join of M from joins of the pieces, the graphic case uses Frank's equality, the cographic case uses the sphere-covering bound (with min-degree ≥3 giving t>1/3), and R10 is handled with explicit values. The only step that is not self-contained is the use of the strong form of Seymour's decomposition theorem, specifically the lower bound |E(M_i)\\cl(T)|≥6. Since this is a standard, deep theorem, the concern is not an internal inconsistency but a verification risk: if the quotation is accurate, the main claim follows; if not, the proof has a gap. The asserted finite computations (R10, gadget case analysis) do not threaten the central constant-factor bound, because small errors there would not change the inequality—for R10 only μ≥2 is needed, which is evident since any pair of elements is a join. Thus I agree with the reader's assessment and recommend leaving the verdict UNCHANGED (CONDITIONAL), pending verification of the external theorem.","tokens_in":34882,"tokens_out":15726,"duration_ms":167932,"concrete_test":"Verify the precise statement of Theorem 2.7(iv)(c) against Oxley's 'Matroid Theory' Cor. 13.4.6 and Seymour's original paper [18]. Then, for each component M_i in a 3-sum decomposition, compute the contracted matroid Q_i=M_i/T and confirm that |E(M_i)\\cl_{M_i}(T)|≥6 indeed implies r(Q_i)>0 by exhibiting an element outside cl(T) with rank 1 in Q_i. If the bound is confirmed, the concern is resolved; if a counterexample to the bound exists, Theorem 5.9 and Corollary 5.10 need repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main result (Cor 5.10) is derived from r(M)≤6μ(M)−2κ(M) (Thm 5.9) by induction over Seymour's decomposition. In the 3-connected non-exceptional case, the proof invokes Thm 2.7 to decompose M=M1⊕3M2 over a triangle T and applies the induction hypothesis to Q_i=M_i/T. The only argument that κ(Q_i)≥1 is the quoted lower bound |E(M_i)\\cl_{M_i}(T)|≥6: it gives an element e_i∉cl_{M_i}(T), which is a non-loop of Q_i. If this bound were absent, misquoted, or not always true, the induction step for the 3-sum case would not go through and the regular-matroid theorem would lack a proof. The paper neither proves nor derives this bound; it cites a deep external theorem. I checked the surrounding lemmas (2-sum, graphic, cographic, R10) and found no internal inconsistency; the dependence on Thm 2.7(iv)(c) is the single most load-bearing assumption for the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies how far Frank's min-max theorem for graphic matroids—that the maximum join size μ(M) equals the ear-decomposition parameter η(M)—extends to arbitrary matroids. The authors prove that exact equality fails already for cographic matroids, that μ and η are incomparable in general, and that the class of matroids with μ=η is not minor-closed. On the algorithmic side, they prove that computing μ is NP-hard for cographic matroids, inapproximable within 519/520 unless P=NP, and NP-hard for connected sparse paving matroids given by their basis lists. The positive results include a one-sided bound μ≤η for binary matroids, tight constant-factor comparisons for paving matroids, rank-dependent tight bounds for general matroids, and the main theorem: for every connected regular matroid not isomorphic to U_{1,1}, η(M)≤6μ(M)-2. The regular-matroid proof combines Frank's graphic theorem, a cographic entropy bound, R_{10}, and Seymour's decomposition theorem.","tokens_in":35143,"tokens_out":39397,"duration_ms":432430,"significance":"If the results are correct, the regular-matroid bound is a genuine constant-factor analogue of Frank's theorem in a class where exact equality fails, and the binary one-sided bound gives a structural explanation of why the failure is one-directional within GF(2)-representable matroids. The hardness results are concrete and the comparison bounds are sharp with explicit extremal examples. The paper is careful: the constants (2/3, 2, c0<5.5, 6) are not fitted parameters, the finite claims for K_{4,4}, R_{10}, and the sparse-paving reduction are presented with explicit certificates, and the induction in Theorem 5.9 is internally coherent. The main potentially fragile point is the use of the external lower bound |E(M_i)\\cl(T)|≥6 from Seymour's decomposition theorem to guarantee positive rank after contraction; this is a quoted theorem, not an ad-hoc assumption, and it is used correctly. I do not regard this as circularity or as a gap.","major_comments":[],"minor_comments":[{"comment":"The lower bound is stated in places as ⌊μ(M)/2⌋, but the proof establishes ⌈μ(M)/2⌉ (and Remark 4.8 likewise says η=⌈μ/2⌉). Please reconcile the notation in the theorem statement and abstract so that the displayed bound matches the proof and the claimed tightness.","section":"Theorem 4.7 and abstract"},{"comment":"The claim that the one-edge-extension graph G gives μ(N)=η(N)=5 is asserted as a direct computation but no computation or certificate is provided. Since this is the only evidence for the non-minor-closedness statement, please include the verification or at least a concise derivation of μ(N) and η(N).","section":"Remark 3.2"},{"comment":"The phrase 'Since sabs is a 3-cycle' appears to be a typo; it should read 's-a-b-s' or 'sab s'. Please correct.","section":"Lemma 3.10"},{"comment":"In the 3-sum case, the positive-rank claim κ(Q_i)≥1 is exactly where Theorem 2.7(iv)(c) is used. A short parenthetical noting that the bound is quoted verbatim from Oxley's Corollary 13.4.6 would make the dependence explicit and reassure readers who might otherwise think the lower bound is an unproved assumption.","section":"Section 5.4, Theorem 5.9"},{"comment":"The case analysis in Lemmas 3.8–3.10 is dense and relies on Figure 1. If space permits, adding the explicit signed-edge configuration for the extremal signing in Lemma 3.10 in a small table would improve verifiability.","section":"Section 3.3.3"}],"recommendation":"minor_revision","confidential_remarks":"I found no load-bearing technical error. The referee's main worry about Theorem 5.9 depending on the external lower bound in Theorem 2.7(iv)(c) does not, on close reading, land: the bound is part of the quoted Seymour decomposition theorem, and the proof uses it precisely to ensure that the contracted matroids Q_i have positive rank. The manuscript would be strengthened by fixing the floor/ceiling notation in Theorem 4.7 and by supplying the omitted computation in Remark 3.2. These are local issues, so minor revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Overall: this is a genuine contribution. It settles how far Frank's min-max theorem extends: equality already fails for cographic matroids, the class satisfying equality is not minor-closed, and the two parameters are incomparable. On the positive side, it delivers the first constant-factor analogue for regular matroids via Seymour's decomposition, with a clean induction. The counterexamples are well chosen, and the hardness reductions look correct to me.\n\nWhat's new: the separation of μ and η in cographic and paving matroids, the NP-hardness including the 519/520 inapproximability, and the comparison bounds: μ ≤ η for binary, 2/3μ ≤ η ≤ 2μ for paving, the rank-dependent general bounds, and the cographic bound with c0 ≈ 5.42. The regular-matroid theorem (r ≤ 6μ − 2κ, hence η ≤ 6μ − 2) is the centerpiece and uses Seymour's decomposition in a natural way.\n\nSoft spots: several finite computations are asserted without full details — R10 parameters, the one-edge extension in Remark 3.2, and the gadget lemmas in Section 3.3.3 are verified by a summarized case analysis. These are minor in a combinatorics paper; the cases are small and the claims are plausible. The strongest external dependency is Theorem 2.7(iv)(c), which guarantees |E(M_i)\\cl_{M_i}(T)| ≥ 6 in the 3-sum case, used to ensure the contracted matroids have positive rank. That's a deep theorem, but it's quoted correctly from Oxley, and leaning on it is exactly what Seymour's decomposition is for. I don't see a circularity or a fitted parameter.\n\nWho is this for: matroid theorists and combinatorial optimizers interested in ear decompositions and conservative weightings; also people working on covering radius of linear codes. It deserves a serious referee. I'd send it to review, with a request to add more details to the finite checks (perhaps an appendix or supplementary code) but nothing more.","headline":"A solid paper: the exact equality fails beyond graphic matroids, and the resulting constant-factor bounds, especially 6μ−2 for regular matroids, are a real step forward; the reviewer's concerns are minor.","tokens_in":35634,"tokens_out":2892,"would_cite":true,"duration_ms":31804,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B35","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows the exact min–max equality between joins and ear decompositions is special to graphic matroids, yet connected regular matroids still satisfy η(M) ≤ 6μ(M) − 2.","keywords":["matroids","joins","ear decompositions","regular matroids","cographic matroids","paving matroids","covering radius","maximum frustration"],"falsifier":"Find a connected regular matroid $M$ (or already a cographic matroid $M=M^*(G)$) with $\\eta(M)>6\\mu(M)-2$. Concretely, for a cographic matroid $\\mu(M)$ equals the covering radius of the cutset code of $G$ and $\\eta(M)$ is computable from ear decompositions, so one can test graphs: if any graph $G$ has $r(M)>6\\rho(B(G))-2$, the main theorem is false.","tokens_in":34779,"feed_emoji":"🧮","tokens_out":10506,"duration_ms":103545,"temperature":0.7,"pith_summary":"The paper asks whether the exact equality between the maximum join size $\\mu(M)$ and the ear-decomposition parameter $\\eta(M)$, proved for graphic matroids, survives in matroids. It finds the equality is genuinely graphic: it already fails for cographic matroids ($\\mu=4$ vs $\\eta=5$ for $M^*(K_{4,4})$), the reverse inequality occurs in paving matroids, and the equality class is not minor-closed. Computing $\\mu(M)$ is NP-hard for cographic and for sparse paving matroids, and hard to approximate within $519/520$. The positive core is a constant-factor analogue: every connected regular matroid $M$ not isomorphic to $U_{1,1}$ satisfies $\\eta(M)\\leq 6\\mu(M)-2$, proved by combining the graphic equality, a cographic estimate via the sphere-covering bound, a direct check of $R_{10}$, and the decomposition of regular matroids into 1-, 2-, and 3-sums.","feed_headline":"For regular matroids, ear-decompositions stay within a factor of six of joins","feed_subtitle":"Exact equality fails outside graphic matroids, but the two parameters stay comparable through decomposition.","key_machinery":"The object under study is the pair $(\\mu(M),\\eta(M))$: $\\mu$ is the maximum size of a join, a set meeting every circuit in at most half its elements; $\\eta=(r(M)+\\varphi(M))/2$, where $\\varphi(M)$ is the minimum number of even lobes in an ear decomposition. The argument's load-bearing machinery is the decomposition of regular matroids into graphic and cographic pieces and copies of $R_{10}$ by 1-, 2-, and 3-sums, together with lemmas that control $\\mu$ under contraction along the sum: a join of each contracted piece lifts to a join of the whole, while rank adds with a $+1$ or $+2$ correction.","core_discovery":"Frank's formula relates the largest join of a connected graphic matroid to the minimum number of even lobes in an ear decomposition: $\\mu(M)=\\eta(M)$, where $\\eta(M)=(r(M)+\\varphi(M))/2$. The paper establishes that this exact identity is a graphic phenomenon. It fails for cographic matroids—the dual of $K_{4,4}$ has $\\mu=4$ but $\\eta=5$—and the two parameters can go in either direction in general. Algorithmically the join side is hard: maximum join is NP-hard for cographic matroids, inapproximable within $519/520$ unless P = NP, and NP-hard for sparse paving matroids given by their bases. The main positive theorem is that the parameters remain quantitatively locked on regular matroids: for e","pith_inferences":["The constant 6 is almost certainly not optimal; the tight cographic constant c0 ≈ 5.42 and the R10 equality suggest searching small regular matroids for the true ratio.","The cographic hardness route through maximum frustration indicates that any efficient join algorithm for broader binary classes would have to exploit more than the cutset-code representation, since covering radius is hard.","One testable next step is to check connected transversal matroids for μ = η; a positive answer would give a new exact class beyond graphics, while a counterexample would locate the boundary.","The lift lemmas for 2- and 3-sums resemble a composition principle that could convert any future bound on basic pieces into bounds for all matroids in a decomposition-closed class."],"forward_implications":["The exact min–max equality cannot be a matroidal theorem: cographic and paving counterexamples already separate μ and η in both directions.","Because the equality class is not minor-closed, no forbidden-minor description of matroids with μ = η can exist.","For binary matroids the failure is one-sided: μ(M) ≤ η(M) throughout, so any gap must come from η being larger.","For paving matroids the parameters are within absolute constants, (2/3)μ ≤ η ≤ 2μ, with both constants tight.","For connected regular matroids, η ≤ 6μ − 2, so join and ear-decomposition size are interchangeable up to a fixed factor, the best available surrogate for exact equality in this class."],"supporting_citations":[{"why":"Supplies the exact min–max equality for connected graphic matroids that the paper extends and tests beyond graphics.","marker":"[7]"},{"why":"Decomposes regular matroids via 1-, 2-, and 3-sums into graphic, cographic, and R10 pieces; the backbone of the regular-matroid induction.","marker":"[18]"},{"why":"Provides the sphere-covering bound used to lower-bound the join parameter of cographic matroids.","marker":"[5]"},{"why":"Equates cographic joins with maximum frustration and the covering radius of the cutset code, key for the cographic estimate and the hardness reduction.","marker":"[19]"},{"why":"Develops the matroidal ear-decomposition and odd-ear theory from which φ(M) and η(M) are taken.","marker":"[20]"},{"why":"Characterizes connected matroids by the existence of ear decompositions, making η(M) well-defined throughout the paper.","marker":"[6]"},{"why":"Source of the structural statements on 2-connected and 3-connected regular matroids used in the induction.","marker":"[15]"},{"why":"Gives the gap hardness for stable sets in cubic graphs that yields the 519/520 inapproximability for cographic joins.","marker":"[2]"}],"fun_headline_variants":["Regular matroids: joins and ear decompositions differ by at most factor 6","Beyond graphic matroids: exact equality fails, but factor-6 bound holds","Max join is NP-hard for cographic and sparse paving matroids","Ear decompositions vs joins: six-fold guarantee on regular matroids","When joins and ear decompositions stay within factor 6"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The proof leans on the decomposition theorem for regular matroids, and in the 3-connected case on the strong structural guarantee that each summand has at least six elements outside the closure of the shared triangle; if that guarantee failed, the contracted pieces could have zero rank and the induction step would not go through.","fun_headline_variants_meta":{"raw":{"variants":["Regular matroids: joins and ear decompositions differ by at most factor 6","Beyond graphic matroids: exact equality fails, but factor-6 bound holds","Max join is NP-hard for cographic and sparse paving matroids","Ear decompositions vs joins: six-fold guarantee on regular matroids","When joins and ear decompositions stay within factor 6"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000754,"raw_usage":{"total_tokens":3247,"prompt_tokens":859,"completion_tokens":2388,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":2293}},"tokens_in":603,"tokens_out":2388,"duration_ms":18739,"temperature":1.0,"reasoning_tokens":2293,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:36:03.732350+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a connected regular matroid $M$ (or already a cographic matroid $M=M^*(G)$) with $\\eta(M)>6\\mu(M)-2$. Concretely, for a cographic matroid $\\mu(M)$ equals the covering radius of the cutset code of $G$ and $\\eta(M)$ is computable from ear decompositions, so one can test graphs: if any graph $G$ has $r(M)>6\\rho(B(G))-2$, the main theorem is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the exact min–max equality for connected graphic matroids that the paper extends and tests beyond graphics."},{"cited_title":"Cohen, I","cited_arxiv_id":null,"evidence_quote":"Provides the sphere-covering bound used to lower-bound the join parameter of cographic matroids."},{"cited_title":"Sol´ e and T","cited_arxiv_id":null,"evidence_quote":"Equates cographic joins with maximum frustration and the covering radius of the cutset code, key for the cographic estimate and the hardness reduction."},{"cited_title":"Szegedy and C","cited_arxiv_id":null,"evidence_quote":"Develops the matroidal ear-decomposition and odd-ear theory from which φ(M) and η(M) are taken."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes connected matroids by the existence of ear decompositions, making η(M) well-defined throughout the paper."},{"cited_title":"Oxley.Matroid Theory","cited_arxiv_id":null,"evidence_quote":"Source of the structural statements on 2-connected and 3-connected regular matroids used in the induction."},{"cited_title":"Berman and M","cited_arxiv_id":null,"evidence_quote":"Gives the gap hardness for stable sets in cubic graphs that yields the 519/520 inapproximability for cographic joins."}],"review_version":1}