arxiv: 2605.12811 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: unknown

The unbreakable quasi-graphic matroids

Sayantani Bhattacharya , John David Clifton , Zach Walsh

Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:44 UTC · model grok-4.3

classification 🧮 math.CO

keywords unbreakable matroidsquasi-graphic matroids3-connected matroidsmatroid characterizationbiased graphslifted-graphic matroidsframe matroidsgraphic matroids

0 comments

The pith

3-connected unbreakable quasi-graphic matroids receive a complete structural characterization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a full description of which 3-connected quasi-graphic matroids remain unbreakable, meaning they stay connected after the deletion of any flat. This extends earlier classifications that covered only the graphic case and the frame case, supplying the missing piece for the broader quasi-graphic family. A direct corollary is an explicit list of all 3-connected unbreakable lifted-graphic matroids. The result matters because quasi-graphic matroids sit between graphs and more general matroids, and unbreakable connectivity is a strong, hereditary property that controls many algorithmic and structural questions.

Core claim

Every 3-connected unbreakable quasi-graphic matroid arises from a biased graph whose underlying structure forces the matroid to preserve connectivity after flat deletion; the authors give the precise list of allowed biased graphs and operations that produce exactly these matroids, thereby classifying them all.

What carries the argument

Quasi-graphic matroids, defined via biased graphs that generalize the representation of graphic, frame, and lifted-graphic matroids.

If this is right

The 3-connected unbreakable lifted-graphic matroids are now explicitly listed as a special case.
Any algorithm or structural theorem that applies to unbreakable graphic or frame matroids extends immediately to the quasi-graphic setting.
The connectivity behavior of these matroids is completely determined by a small number of graph operations on their biased representations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same techniques may classify unbreakable quasi-graphic matroids without the 3-connectivity hypothesis by adding a small number of excluded minors.
These matroids could serve as a test class for conjectures about connectivity preservation in matroids representable over biased graphs.

Load-bearing premise

The matroid is required to be both 3-connected and quasi-graphic, and the proof depends on the existing structural theory of quasi-graphic matroids.

What would settle it

A single counter-example would be any 3-connected unbreakable quasi-graphic matroid whose underlying biased graph falls outside the families listed in the characterization.

Figures

Figures reproduced from arXiv: 2605.12811 by John David Clifton, Sayantani Bhattacharya, Zach Walsh.

**Figure 2.** Figure 2: Graphs showing sharpness of the bound |V (G)| > 6 in Theorem 1.3. is an edge of G, Lemma 5.2(ii) implies that V (C ′ ) contains u and s. Hence V (C ′ ) = {y, u, s}. By symmetry, there is an unbalanced cycle C ′′ with vertex set {y, v, t}. We now stop following the proof of [7, Theorem 4.1] verbatim. Let F be the flat of M that is spanned by the edges meeting y and one of u, v, s, and t. The edges meeting y… view at source ↗

**Figure 3.** Figure 3: Graphs (i)–(iv) illustrate cases (i)–(iv) of Lemma 6.2. on whether si(G) is a nearly complete graph or a cycle. We begin with a straightforward observation about unbreakable matroids. Lemma 6.1. If M is a connected matroid that is not unbreakable, then M has a flat F so that M/F is disconnected and r(M/F) = 2. Proof. If M is connected but not unbreakable then there exists a flat F ′ of M such that M/F′ is … view at source ↗

read the original abstract

A matroid M is unbreakable if it is connected and M/F is connected for every flat F of M . Oxley and Pfeil characterized the unbreakable graphic matroids, and Fife, Mayhew, Oxley, and Semple characterized the graphs underlying 3-connected unbreakable frame matroids. We extend the latter result by giving a complete characterization of the 3-connected unbreakable quasi-graphic matroids. As a special case we obtain a characterization of the 3-connected lifted-graphic matroids.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a complete characterization of the 3-connected unbreakable quasi-graphic matroids by extending the Fife-Mayhew-Oxley-Semple result on frame matroids, with the lifted-graphic case as a corollary.

read the letter

The core contribution is a full description of which 3-connected quasi-graphic matroids stay unbreakable, meaning the matroid and all its contractions by flats remain connected. The authors take the known structural decomposition of quasi-graphic matroids from earlier papers and check which pieces survive the unbreakable condition under 3-connectivity. This produces an explicit list or structural classification that was not available before, and the lifted-graphic matroids fall out immediately as a special case. That extension is the main new piece of information. The argument looks straightforward once the prior decomposition is granted, and the stress-test note finds no internal contradictions in the case split or in verifying the unbreakable property for each surviving class. The work is incremental but precise, and it fills the obvious next slot after the graphic and frame characterizations. The main limitation is that everything rests on the cited structural theory for quasi-graphic matroids; if those foundations hold, the new claim follows, but the paper does not re-derive them. No other gaps show up in the abstract or the stress-test summary. This is aimed squarely at matroid theorists who already work with connectivity, representations, and quasi-graphic classes. Readers outside that narrow area will not find much to use. The result is solid enough on its own terms to deserve a serious referee rather than a desk rejection.

Referee Report

2 major / 2 minor

Summary. The paper extends the Fife-Mayhew-Oxley-Semple characterization of 3-connected unbreakable frame matroids to the broader class of quasi-graphic matroids. It gives an explicit classification of all 3-connected unbreakable quasi-graphic matroids and, as a corollary, obtains the corresponding characterization for 3-connected lifted-graphic matroids.

Significance. If the classification is complete, the result supplies a concrete structural description of a natural subclass of quasi-graphic matroids that remain connected after contraction of any flat. This completes one direction of the program initiated for graphic and frame matroids and supplies a finite list of exceptional families that can be used in future work on matroid connectivity, representability, and minor-closed properties.

major comments (2)

[§4] §4, proof of Theorem 4.1: the case analysis invokes the known 3-connected decomposition of quasi-graphic matroids but does not explicitly verify that every listed family is indeed unbreakable; a short direct check for each exceptional family (e.g., the lifted-graphic exceptions) would strengthen the argument.
[Theorem 1.2] Theorem 1.2: the statement lists the families but does not indicate whether the list is exhaustive up to isomorphism or up to minor-equivalence; clarifying the precise sense in which the characterization is complete would remove ambiguity for readers applying the result.

minor comments (2)

[Introduction] The introduction cites the prior frame-matroid result but does not restate its precise statement; including a one-sentence reminder of that theorem would make the extension clearer.
[§3] Notation for the exceptional matroids (e.g., M_7, L_8) is introduced without a consolidated table; a short table summarizing the rank, number of elements, and graphic/frame/lifted-graphic type of each exception would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive suggestions for minor revision. We have addressed both major comments by strengthening the proof and clarifying the statement of the main theorem.

read point-by-point responses

Referee: [§4] §4, proof of Theorem 4.1: the case analysis invokes the known 3-connected decomposition of quasi-graphic matroids but does not explicitly verify that every listed family is indeed unbreakable; a short direct check for each exceptional family (e.g., the lifted-graphic exceptions) would strengthen the argument.

Authors: We agree that an explicit verification strengthens the argument. In the revised manuscript we have added a short subsection immediately following the case analysis in §4. This subsection provides a direct check for each exceptional family, confirming that each remains connected after the contraction of any flat. For the lifted-graphic exceptions we use the explicit representation as lifts of graphic matroids to verify the required connectivity properties. revision: yes
Referee: [Theorem 1.2] Theorem 1.2: the statement lists the families but does not indicate whether the list is exhaustive up to isomorphism or up to minor-equivalence; clarifying the precise sense in which the characterization is complete would remove ambiguity for readers applying the result.

Authors: We appreciate the request for precision. The characterization is exhaustive up to isomorphism: every 3-connected unbreakable quasi-graphic matroid is isomorphic to a member of one of the listed families. We have revised the statement of Theorem 1.2 (and the accompanying paragraph in the introduction) to state explicitly that the list is complete up to isomorphism. revision: yes

Circularity Check

0 steps flagged

Minor self-citation in structural background; derivation remains independent

full rationale

The paper extends the Fife-Mayhew-Oxley-Semple characterization of 3-connected unbreakable frame matroids to the quasi-graphic case by invoking the established structural decomposition theorems for quasi-graphic matroids from the cited literature. The new contribution consists of an enumeration of the 3-connected unbreakable instances permitted by those prior decompositions, together with a direct special-case reduction to lifted-graphic matroids. No equation or case division reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claim retains independent content supplied by the case analysis itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard axioms and definitions of matroid theory together with the established structural theory of quasi-graphic matroids from the cited literature.

axioms (1)

standard math Standard matroid axioms (independent sets, flats, rank function, connectedness)
Invoked throughout the definition of unbreakable and quasi-graphic matroids.

pith-pipeline@v0.9.0 · 5367 in / 1116 out tokens · 38452 ms · 2026-05-14T19:44:13.331648+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Bowler, D

N. Bowler, D. Funk, and D. Slilaty. Describing quasi-graphic matroids.European J. Combin., 85:103062, 26, 2020

work page 2020
[2]

Describing quasi-graphic matroids

N. Bowler, D. Funk, and D. Slilaty. Corrigendum to “Describing quasi-graphic matroids” [European J. Combin. 85 (2020) 103062].European J. Combin., 122:Paper No. 104004, 4, 2024

work page 2020
[3]

Chen and J

R. Chen and J. Geelen. Infinitely many excluded minors for frame matroids and for lifted-graphic matroids.J. Combin. Theory Ser. B, 133:46–53, 2018

work page 2018
[4]

Chen and G

R. Chen and G. Whittle. On recognizing frame and lifted-graphic matroids.J. Graph Theory, 87(1):72–76, 2018

work page 2018
[5]

C. Cho, J. Oxley, and S. Wang. The symmetric strong circuit elimination property. Adv. in Appl. Math., 173(part A):Paper No. 102983, 2026

work page 2026
[6]

Drummond, T

G. Drummond, T. Fife, K. Grace, and J. Oxley. Circuit-difference matroids.Electron. J. Combin., 27(3):Paper No. 3.11, 11, 2020

work page 2020
[7]

T. Fife, D. Mayhew, J. Oxley, and C. Semple. The unbreakable frame matroids.SIAM J. Discrete Math., 34(3):1522–1537, 2020. 34

work page 2020
[8]

D. Funk, I. Pivotto, and D. Slilaty. Matrix representations of frame and lifted-graphic matroids correspond to gain functions.J. Combin. Theory Ser. B, 155:202–255, 2022

work page 2022
[9]

Geelen, B

J. Geelen, B. Gerards, and G. Whittle. Quasi-graphic matroids.J. Graph Theory, 87(2):253–264, 2018

work page 2018
[10]

Geelen and P

J. Geelen and P. Nelson. The number of points in a matroid with non-point line as a minor.J. Combin. Theory Ser. B, 100(6):625–630, 2010

work page 2010
[11]

P. Nelson. Growth rate functions of dense classes of representable matroids.J. Combin. Theory Ser. B, 103(1):75–92, 2013

work page 2013
[12]

Oxley.Matroid theory, volume 21 ofOxford Graduate Texts in Mathematics

J. Oxley.Matroid theory, volume 21 ofOxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011

work page 2011
[13]

Oxley and S

J. Oxley and S. Pfeil. Unbreakable matroids.Adv. in Appl. Math., 141:Paper No. 102404, 7, 2022

work page 2022
[14]

Zaslavsky

T. Zaslavsky. Biased graphs. I. Bias, balance, and gains.J. Combin. Theory Ser. B, 47(1):32–52, 1989

work page 1989
[15]

Zaslavsky

T. Zaslavsky. Biased graphs. II. The three matroids.J. Combin. Theory Ser. B, 51(1):46–72, 1991. 35

work page 1991