Joins and ear decompositions beyond graphic matroids

Chaitanya Nalam; Krist\'of B\'erczi; Yuhang Bai

Joins and ear decompositions beyond graphic matroids

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

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2608.01059 v1 pith:SHF4TLET submitted 2026-08-02 math.CO cs.DM

Yuhang Bai , Kristóf Bérczi , Chaitanya Nalam This is my paper · ORCID

classification math.COcs.DM MSC 05B3568Q17

keywords matroidsjoinseardecompositionsregularcographicpavingcoveringradiusmaximumfrustration

topics P versus NP

open problems P versus NP

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

What'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.

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

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

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)

[Theorem 4.7 and abstract] 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.
[Remark 3.2] 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).
[Lemma 3.10] 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 5.4, Theorem 5.9] 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 3.3.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regular-matroid comparison is assembled from independent external theorems and finite checks, not from its own conclusion.

full rationale

The central derivation chain is not circular. Theorem 5.9 proves r(M) ≤ 6μ(M) − 2κ(M) for regular matroids by induction over Seymour's decomposition, using as independent anchors: Frank's graphic theorem (Theorem 2.11), the cographic bound derived from the sphere-covering bound and η ≤ r (Theorem 5.2 and Claim 5.3), the direct finite analysis of R10 (Proposition 5.4), and Seymour's decomposition theorems (Theorems 2.5 and 2.7). None of these inputs is defined in terms of the target inequality; μ and η are separate combinatorial parameters, and no fitted parameter is later renamed as a prediction. The proof does rely on the external structural bound |E(M_i)\cl_{M_i}(T)| ≥ 6 from Theorem 2.7(iv)(c) to ensure positive rank after contraction, but this is an external result cited from Oxley [15], not a self-citation and not a restatement of the theorem being proved. The paper itself flags in its concluding section that the constant 6 is likely not optimal and asks whether 2 is achievable; that is an ordinary limitation statement, not evidence of circularity. There are no author self-citations, no imported uniqueness theorem, and no ansatz smuggled in via the authors' prior work. The hardness reductions rely on external results (Berman–Karpinski, Guruswami–Micciancio–Regev, Gallai) and on independently verified gadget estimates. Thus the derivation is self-contained against external anchors and the circularity score is 0.

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

The paper introduces no fitted parameters and no new postulated entities. Its results rest on a set of standard, external structural and complexity theorems; the most nontrivial of these is Seymour's decomposition theorem.

assumptions (7)

standard math Frank's min-max theorem: μ(G) = η(G) for connected graphic matroids
Used as the graphic base case in Theorem 5.9 and Corollary 5.10; quoted from [7].
standard math Seymour's decomposition theorem for regular matroids (Theorems 2.5, 2.6, 2.7)
The backbone of the regular-matroid bound; provides the 1-, 2-, 3-sum decomposition and the structural properties of 3-sum components used in the induction.
standard math Sphere-covering bound for binary codes
Used in the cographic bound (Theorem 5.2) and in the μ(M) = 1 cographic case to lower-bound the covering radius in terms of code dimension.
standard math Gallai's identity α(G) + τ(G) = |V(G)|
Used in Lemma 3.6 for the cubic-graph estimate and in Claim 3.18.
standard math Hartmanis characterization of paving and sparse paving matroids (Theorem 2.4)
Basis for the sparse-paving hardness construction.
standard math Equivalence of maximum frustration, cutset-code covering radius, and cographic joins (Sole-Zaslavsky, Bowlin)
Connects μ(M*(G)) to Fmax(G) = ρ(B(G)); foundational for the cographic hardness and the entropy bound.
domain assumption Berman-Karpinski gap hardness for cubic maximum stable set
External complexity assumption used to derive the 519/520 inapproximability factor; cited from an ECCC report.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Joins and ear decompositions beyond graphic matroids." pith.science (2026). https://pith.science/paper/SHF4TLET

@misc{pith2026260801059,
  author       = {Pith},
  title        = {Pith review of: Joins and ear decompositions beyond graphic matroids},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SHF4TLET}},
  note         = {Machine review of arXiv:2608.01059}
}

abstract

For a matroid $M$, a join is a set $J\subseteq E(M)$ that meets every circuit $C$ in at most $|C|/2$ elements. Let $\mu(M)$ denote the maximum size of a join. Motivated by Frank's min--max theorem for graphic matroids, we compare $\mu(M)$ with an ear-decomposition parameter $\eta(M)=(r(M)+\varphi(M))/2$, where $\varphi(M)$ is the minimum number of even lobes in an ear decomposition of $M$. Frank's theorem implies $\mu(M)=\eta(M)$ for connected graphic matroids. Here we study how far this equality extends beyond graphic matroids. We show that the exact equality does not hold in general: it already fails for cographic matroids, hence within the binary class. Furthermore, the class of matroids satisfying $\mu(M)=\eta(M)$ is not minor-closed, thus there is little hope for a forbidden minor characterization. We also prove that computing a maximum join is NP-hard for cographic matroids, hard to approximate within a factor of $519/520$, and NP-hard for sparse paving matroids given by their list of bases. Despite these negative results, we show that the two parameters remain quantitatively comparable in several natural classes. We prove comparison bounds for binary, paving, cographic, and arbitrary connected matroids. In particular, using Seymour's decomposition theorem, we combine the equality for graphic matroids, the bound for cographic matroids, and a direct analysis of $R_{10}$ to obtain $\eta(M)\leq 6\mu(M)-2$ for every regular matroid $M$.

Figures

Figures reproduced from arXiv: 2608.01059 by the authors.

**Figure 2.** Illustration for the reduction and proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages

[1]

C. A. Athanasiadis and L. Ferroni. A convex ear decomposition of the augmented Bergman complex of a matroid.Arkiv f¨ or Matematik, 64(1):1–17, 2026

work page 2026
[2]

Berman and M

P. Berman and M. Karpinski. Improved approximation lower bounds on small occurrence optimization. ECCC Report, 2003

work page 2003
[3]

G. S. Bowlin. Maximum frustration in bipartite signed graphs.The Electronic Journal of Combinatorics, 19(4):P10, 2012

work page 2012
[4]

Bryant, J

V. Bryant, J. Dawson, and H. Perfect. Hereditary circuit spaces.Compositio Mathematica, 37(3):339– 351, 1978

work page 1978
[5]

Cohen, I

G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein.Covering codes, volume 54. Elsevier, 1997

work page 1997
[6]

C. R. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory.Combinatorica, 16(2):189–208, 1996

work page 1996
[7]

A. Frank. Conservative weightings and ear-decompositions of graphs.Combinatorica, 13(1):65–81, 1993

work page 1993
[8]

Frank.Connections in combinatorial optimization, volume 38 ofOxford Lecture Series in Mathematics and its Applications

A. Frank.Connections in combinatorial optimization, volume 38 ofOxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2011

work page 2011

Show all 25 references

[9]

T. Gallai. ¨Uber extreme punkt- und kantenmengen.Annales Universitatis Scientiarum Budapestinensis de Rolando E¨ otv¨ os, Sectio Mathematica, 2:133–138, 1959

1959
[10]

Guruswami, D

V. Guruswami, D. Micciancio, and O. Regev. The complexity of the covering radius problem.Compu- tational Complexity, 14:90–121, 2005

2005
[11]

Hartmanis

J. Hartmanis. Lattice theory of generalized partitions.Canadian Journal of Mathematics, 11:97–106, 1959

1959
[12]

Jord´ an

T. Jord´ an. Ear-decompositions, minimally connected matroids and rigid graphs.Journal of Graph Theory, 105(3):451–467, 2024

2024
[13]

Lov´ asz

L. Lov´ asz. A note on factor-critical graphs.Studia Scientiarum Mathematicarum Hungarica, 7:279–280, 1972

1972
[14]

U. S. R. Murty. Extremal critically connected matroids.Discrete Mathematics, 8(1):49–58, 1974

1974
[15]

Oxley.Matroid Theory

J. Oxley.Matroid Theory. Oxford University Press, Second edition, 2011

2011
[16]

H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control.The American Mathematical Monthly, 46(5):281–283, 1939

1939
[17]

Seb˝ o and J

A. Seb˝ o and J. Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs.Combinatorica, 34(5):597–629, 2014

2014
[18]

P. D. Seymour. Decomposition of regular matroids.Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980

1980
[19]

Sol´ e and T

P. Sol´ e and T. Zaslavsky. A coding approach to signed graphs.SIAM Journal on Discrete Mathematics, 7(4):544–553, 1994

1994
[20]

Szegedy and C

B. Szegedy and C. Szegedy. Symplectic spaces and ear-decomposition of matroids.Combinatorica, 26(3):353–377, 2006

2006
[21]

Szegedy.Some applications of the weighted combinatorial Laplacian

C. Szegedy.Some applications of the weighted combinatorial Laplacian. Ph.D. thesis, Rheinische Friedrich-Wilhelms-Universit¨ at Bonn, 2005

2005
[22]

Z. Szigeti. On a matroid defined by ear-decompositions of graphs.Combinatorica, 16(2):233–241, 1996

1996
[23]

D. J. Welsh.Matroid Theory. Courier Corporation, 2010

2010
[24]

D. B. West.Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996

1996
[25]

H. Whitney. Non-separable and planar graphs.Transactions of the American Mathematical Society, 34(2):339–362, 1932. 31

1932

Pith tools

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

[1] [1]

C. A. Athanasiadis and L. Ferroni. A convex ear decomposition of the augmented Bergman complex of a matroid.Arkiv f¨ or Matematik, 64(1):1–17, 2026

work page 2026

[2] [2]

Berman and M

P. Berman and M. Karpinski. Improved approximation lower bounds on small occurrence optimization. ECCC Report, 2003

work page 2003

[3] [3]

G. S. Bowlin. Maximum frustration in bipartite signed graphs.The Electronic Journal of Combinatorics, 19(4):P10, 2012

work page 2012

[4] [4]

Bryant, J

V. Bryant, J. Dawson, and H. Perfect. Hereditary circuit spaces.Compositio Mathematica, 37(3):339– 351, 1978

work page 1978

[5] [5]

Cohen, I

G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein.Covering codes, volume 54. Elsevier, 1997

work page 1997

[6] [6]

C. R. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory.Combinatorica, 16(2):189–208, 1996

work page 1996

[7] [7]

A. Frank. Conservative weightings and ear-decompositions of graphs.Combinatorica, 13(1):65–81, 1993

work page 1993

[8] [8]

Frank.Connections in combinatorial optimization, volume 38 ofOxford Lecture Series in Mathematics and its Applications

A. Frank.Connections in combinatorial optimization, volume 38 ofOxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2011

work page 2011