# Matroid minor

A **matroid minor** of a matroid M is any matroid obtained from M by a sequence of deletions and contractions of elements, written M\D/C for disjoint subsets C and D of the ground set E; minors form a natural partial order on matroids, and a class of matroids is minor closed when every minor of a member is again a member.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> The notion parallels the graph minor, obtained by deletions, contractions, and deletions of isolated vertices; the matroid version differs only because arbitrary matroids have no vertices.<sup>[2](https://www.math.lsu.edu/~oxley/jobcc.pdf)</sup> Matroids themselves were introduced by [Hassler Whitney](https://www.edgepedia.org/hassler-whitney) in 1935 to give a unifying abstract treatment of dependence in linear algebra and graph theory.<sup>[3](https://www.math.lsu.edu/~oxley/survey4.pdf)</sup>

| Key fact | Detail |
|---|---|
| Definition | A minor is M\D/C for disjoint C, D ⊆ E; deletion and contraction in a graph correspond exactly to deletion and contraction in its cycle matroid<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup><sup> • </sup><sup>[2](https://www.math.lsu.edu/~oxley/jobcc.pdf)</sup> |
| Binary matroids | A matroid is binary if and only if it has no U\_{2,4}-minor (Tutte)<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup> |
| Ternary matroids | Excluded minors: U\_{2,5}, U\_{3,5}, F\_7, F\_7* (Reid, Bixby)<sup>[5](https://archytas2.birs.ca/workshops/2009/09w5103/files/mayhew_09w5103_talk.pdf)</sup> |
| Regular matroids | Excluded minors: U\_{2,4}, F\_7, F\_7*; Seymour's decomposition theorem yields a polynomial-time total-unimodularity test<sup>[6](https://arxiv.org/pdf/2601.02582v2)</sup><sup> • </sup><sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> |
| GF(4)-representable matroids | Exactly seven excluded minors: U\_{2,6}, U\_{4,6}, P\_6, F\_7−, (F\_7−)*, P\_8, P\_8′<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup> |
| Well-quasi-ordering | Matroids representable over a fixed finite field with bounded branch-width are well-quasi-ordered by the minor relation<sup>[7](https://math.uwaterloo.ca/~jfgeelen/Publications/bw_wqo.pdf)</sup> |
| Rota's Conjecture | For each finite field there are only finitely many excluded minors for F-representability; announced in full by Geelen, Gerards, and Whittle<sup>[8](https://www.ams.org/notices/201407/rnoti-p736.pdf)</sup> |
| Complexity | Fixed-minor testing is O(n³) for bounded-branch-width matroids represented over a finite field, but NP-hard for matroids given by a rank oracle<sup>[9](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)</sup> |

## Formal definitions and constructions

**Deletion and contraction.** Deleting a set Y from M gives the restriction to the complement of Y with the restricted rank function. Contracting a set Z gives the rank function X ↦ rk\_M(X ∪ Z) − rk\_M(Z) on the complement of Z; a minor is the result of any sequence of such operations.<sup>[10](https://ar5iv.labs.arxiv.org/html/1512.01390)</sup> Geometrically, when a matroid is represented by vectors labeled by E, contraction corresponds to projecting the vectors labeled by E − C from the subspace spanned by C onto a subspace skew to C, which is why the rank-based definition and the quotient construction agree.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup>

Matroid duality interchanges the two operations: (M\X)* = M*/X, so every theorem about deletion has a dual statement about contraction.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> Minors can also be certified by rank data alone: for a fixed matroid N, one can prove that M has an N-minor using a fixed number of rank evaluations via the identity r\_N(X) = r\_M(X ∪ C) − r\_M(C).<sup>[11](https://www.sciencedirect.com/science/article/pii/S0012365X0500302X)</sup>

## Minor-closed classes and excluded minors

The classes of uniform, graphic, and cographic matroids are minor closed, and for every field F the class of F-representable matroids is minor closed; binary and ternary matroids are the cases F = GF(2) and GF(3).<sup>[3](https://www.math.lsu.edu/~oxley/survey4.pdf)</sup> An excluded minor for F-representability is a matroid that is not F-representable but every single-element deletion and contraction is F-representable.<sup>[5](https://archytas2.birs.ca/workshops/2009/09w5103/files/mayhew_09w5103_talk.pdf)</sup> A minor-minimal matroid outside a minor-closed class is an excluded minor for that class, and finiteness conjectures for such lists, Rota's Conjecture foremost among them, drive much of the theory.<sup>[12](https://academic.oup.com/book/25792/chapter/193382219)</sup>

The classical characterizations are short. Tutte showed that U\_{2,4} is the only excluded minor for the class of binary matroids<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup> and that a matroid is regular if and only if it has no minors of type U\_{2,4}, F\_7, or F\_7*,<sup>[6](https://arxiv.org/pdf/2601.02582v2)</sup> while Bixby and Reid, using Tutte's homotopy theory, proved that a matroid is ternary if and only if it has no U\_{2,5}-, U\_{3,5}-, F\_7-, or F\_7*-minor.<sup>[6](https://arxiv.org/pdf/2601.02582v2)</sup> For GF(4), Geelen, Gerards, and Kapoor proved there are exactly seven excluded minors: U\_{2,6}, U\_{4,6}, P\_6, F\_7−, (F\_7−)*, P\_8, and P\_8′; P\_8′ is obtained by relaxing the unique pair of disjoint circuit-hyperplanes of P\_8, while the other six were previously known.<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup>

Regular matroids have more than an excluded-minor list: Seymour's 1980 Regular Matroid Decomposition Theorem decomposes them into pieces that are graphic, cographic, or copies of the 10-element matroid R\_{10}, and a 3-connected [regular matroid](https://www.edgepedia.org/regular-matroid) with at least 11 elements in which every 3-separation has a side of size at most 5 is graphic or cographic.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> James Oxley has called this structure theorem probably the most important theorem ever proved in matroid theory.<sup>[3](https://www.math.lsu.edu/~oxley/survey4.pdf)</sup> The decomposition is also algorithmic: it leads to a polynomial-time algorithm for deciding whether a real matrix is totally unimodular.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup>

## Structure theory and well-quasi-ordering

The Matroid Minors Project of Geelen, Gerards, and Whittle built a theory parallel to Robertson and Seymour's Graph Minors Project. Its well-quasi-ordering conjecture states that for any finite field F, any infinite set of F-representable matroids contains two matroids one of which is isomorphic to a minor of the other.<sup>[13](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/towards_a_matroid_minor_structure_theory.pdf)</sup> What was proved is a bounded version: a class of matroids representable over a fixed finite field and with bounded branch-width is well-quasi-ordered under taking minors, and with extra work this implies Robertson and Seymour's theorem for graphs of bounded tree-width.<sup>[7](https://math.uwaterloo.ca/~jfgeelen/Publications/bw_wqo.pdf)</sup> The corresponding unbounded statement, without the branch-width restriction, remains a conjecture, because infinite antichains of unrestricted matroids, even among rank-3 matroids, do not disprove it.<sup>[8](https://www.ams.org/notices/201407/rnoti-p736.pdf)</sup><sup> • </sup><sup>[19](https://www.math.uwaterloo.ca/~jfgeelen/Research/research.html)</sup>

**The structure theorem.** The Matroid Minors Structure Theorem, which took more than a decade to prove, describes how to construct the members of any fixed minor-closed class of F-representable matroids from matroids represented over subfields, frame matroids, and duals of frame matroids.<sup>[8](https://www.ams.org/notices/201407/rnoti-p736.pdf)</sup> Up to duality there are only two types of fundamental minor-closed classes of F-representable matroids: the F\_0-representable matroids for each subfield F\_0 of F, and the class of frame matroids over F.<sup>[8](https://www.ams.org/notices/201407/rnoti-p736.pdf)</sup>

Partial finiteness results toward Rota's Conjecture came from this machinery. For any prime power q there are only finitely many excluded minors for GF(q)-representable matroids that contain a PG(q+6, q)-minor,<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> and for any prime power q and fixed integer k there are only finitely many excluded minors for GF(q)-representability among matroids of branch-width k.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> If Rota's Conjecture were false, then for any planar graph G there would be an excluded minor containing G, so counterexamples would contain arbitrarily large grid-like structures.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup> A recorded obstacle in the proof is that inequivalent representations of matroids cause major technical difficulties.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup>

## By the numbers

- **Excluded-minor list sizes:** 1 for binary (U\_{2,4}),<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup> 4 for ternary,<sup>[5](https://archytas2.birs.ca/workshops/2009/09w5103/files/mayhew_09w5103_talk.pdf)</sup> 3 for regular (U\_{2,4}, F\_7, F\_7*),<sup>[6](https://arxiv.org/pdf/2601.02582v2)</sup> and 7 for GF(4).<sup>[4](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)</sup>
- **Branch-width 2:** the excluded minors for the class of matroids of branch-width at most 2 are U\_{2,4} and M(K\_4).<sup>[14](https://www.sciencedirect.com/science/article/pii/S0095895602000461)</sup>
- **Certificates:** proving that an n-element matroid is not GF(p)-representable, for prime p, requires at most O(n²) rank evaluations; a U\_{2,4}-minor can be certified with eight rank evaluations, so non-binary matroids are certified with O(1) evaluations.<sup>[15](https://ar5iv.labs.arxiv.org/html/1101.4691)</sup> In the other direction, proving GF(q)-representability can require at least 2^(n/2) rank evaluations in the worst case, for example for a rank-n spike with n > q³.<sup>[15](https://ar5iv.labs.arxiv.org/html/1101.4691)</sup>
- **Enumeration:** a 2024 computer search enumerated the excluded minors on at most 15 elements for the classes of dyadic and 2-regular matroids, and a 16-element excluded minor exists for dyadic matroids.<sup>[16](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v31i3p20/pdf/)</sup>

## How it compares with graph minors

The two theories run in parallel but not identically. Deletions and contractions in a graph are in one-one correspondence with deletions and contractions in its cycle matroid, so the cycle matroid of a graph minor is a minor of the cycle matroid; the matroid notion simply drops the vertex bookkeeping.<sup>[2](https://www.math.lsu.edu/~oxley/jobcc.pdf)</sup> The Graph Minors Project proved Wagner's conjecture and gave cubic-time testing for a fixed graph minor; Geelen, Gerards, Robertson, and Whittle extended that program to matroids.<sup>[9](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)</sup>

Two differences stand out. First, well-quasi-ordering is proved for matroids of bounded branch-width representable over a fixed finite field and conjectured without the branch-width bound, since infinite antichains exist among unrestricted matroids,<sup>[8](https://www.ams.org/notices/201407/rnoti-p736.pdf)</sup> whereas the graph theorem covers all graphs. Second, minor testing is harder for matroids as inputs: describing an n-element matroid naively requires specifying properties of all 2^n subsets, so inputs are given via a small representation matrix or a rank oracle, and for abstract matroids given by a rank oracle the fixed-minor problem is NP-hard.<sup>[9](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)</sup>

## Algorithmic aspects

For matroids of bounded branch-width represented over a finite field, the fixed N-minor problem runs in O(n³) time.<sup>[9](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)</sup> The bounded-branch-width hypothesis is essential: given an n-element GF(q)-represented matroid of branch-width 3, it is NP-complete to decide whether M has a minor isomorphic to the planar cycle matroid M(G\_6).<sup>[9](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)</sup> The Minor-Recognition Conjecture of Geelen, Gerards, and Whittle asks, for any finite field F and F-representable matroid N, for a polynomial-time algorithm testing whether an F-representable matroid contains an N-minor.<sup>[13](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/towards_a_matroid_minor_structure_theory.pdf)</sup> Rank-evaluation certificates give a complementary tool: O(n²) evaluations suffice to certify non-representability over a prime field,<sup>[15](https://ar5iv.labs.arxiv.org/html/1101.4691)</sup> and Seymour's decomposition yields the polynomial-time total-unimodularity test mentioned above.<sup>[1](https://ir.cwi.nl/pub/22197/22197B.pdf)</sup>

## Recent developments

**New excluded minors for M\_3.** A recent preprint constructs five new graphic matroids M(G\_1), …, M(G\_5) that are excluded minors for the class M\_3, so any finite excluded-minor list for M\_3 contains at least six members together with M(K\_{3,5}), with excluded minors occurring at every rank from 7 to 10.<sup>[17](https://arxiv.org/html/2607.20954v1)</sup> The same work reports that Engel and Schreieder proved M(K\_{2p+1}) and M(K\_{3,2p−1}) are not in M\_p for every prime p, so the radical distance d(M(K\_n)) grows at least exponentially; for p = 5 the witnesses are M(K\_{11}) of corank 45 and M(K\_{3,9}) of corank 16.<sup>[17](https://arxiv.org/html/2607.20954v1)</sup>

**Partial fields and Rota's Conjecture.** The 2024 enumeration of excluded minors for dyadic and 2-regular matroids extends excluded-minor theory beyond the classical field cases.<sup>[16](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v31i3p20/pdf/)</sup> On the main finiteness question, Geelen, Gerards, and Whittle announced that for each finite field F there are finitely many excluded minors for the class of F-representable matroids,<sup>[18](https://matroidunion.org/?p=6113)</sup> resolving Rota's Conjecture; before their work it was known only for GF(2), GF(3), and GF(4).<sup>[15](https://ar5iv.labs.arxiv.org/html/1101.4691)</sup> The conjecture, if true, is best possible in a precise sense: finite fields are the only fields for which finitely many excluded minors can occur.<sup>[13](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/towards_a_matroid_minor_structure_theory.pdf)</sup> For infinite fields the situation is qualitatively different: Mayhew, Newman, and Whittle proved that for any infinite field K and any K-representable matroid M there is an excluded minor N for K-representability with M a minor of N.<sup>[5](https://archytas2.birs.ca/workshops/2009/09w5103/files/mayhew_09w5103_talk.pdf)</sup>

## References

1. [Geelen, Gerards, Whittle. Structure in Minor-Closed Classes of Matroids, Surveys in Combinatorics 2013.](https://ir.cwi.nl/pub/22197/22197B.pdf)
2. [Oxley. On the interplay between graphs and matroids.](https://www.math.lsu.edu/~oxley/jobcc.pdf)
3. [Oxley. What is a matroid?](https://www.math.lsu.edu/~oxley/survey4.pdf)
4. [Geelen, Gerards, Kapoor. The Excluded Minors for GF(4)-Representable Matroids, JCTB 2000.](https://math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf)
5. [Mayhew. Excluded minors for real-representable matroids, BIRS 2009.](https://archytas2.birs.ca/workshops/2009/09w5103/files/mayhew_09w5103_talk.pdf)
6. [A modern perspective on Tutte's homotopy theorem, arXiv.](https://arxiv.org/pdf/2601.02582v2)
7. [Geelen, Gerards, Robertson, Whittle. Branch-Width and Well-Quasi-Ordering in Matroids and Graphs.](https://math.uwaterloo.ca/~jfgeelen/Publications/bw_wqo.pdf)
8. [Geelen, Gerards, Whittle. Solving Rota's Conjecture, AMS Notices 2014.](https://www.ams.org/notices/201407/rnoti-p736.pdf)
9. [Hliněný. On the Computational Complexity of Matroid Minors (lecture slides).](https://www.fi.muni.cz/~hlineny/papers/mminor-sl.pdf)
10. [The category of matroids, arXiv:1512.01390.](https://ar5iv.labs.arxiv.org/html/1512.01390)
11. [Recent work in matroid representation theory, JCTB survey.](https://www.sciencedirect.com/science/article/pii/S0012365X0500302X)
12. [Towards a Matroid-Minor Structure Theory (tribute to Dominic Welsh), Oxford University Press.](https://academic.oup.com/book/25792/chapter/193382219)
13. [Geelen, Gerards, Whittle. Towards a Matroid-Minor Structure Theory.](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/towards_a_matroid_minor_structure_theory.pdf)
14. [Hall, Oxley, Semple, Whittle. On the excluded minors for the matroids of branch-width k, JCTB.](https://www.sciencedirect.com/science/article/pii/S0095895602000461)
15. [Certifying Non-representability of Matroids Over Prime Fields, arXiv:1101.4691.](https://ar5iv.labs.arxiv.org/html/1101.4691)
16. [Computing excluded minors for classes of matroids representable over partial fields, Electronic J. Combinatorics 31(3), 2024.](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v31i3p20/pdf/)
17. [New excluded minors for the class M_3, arXiv.](https://arxiv.org/html/2607.20954v1)
18. [Representability over infinite fields, The Matroid Union.](https://matroidunion.org/?p=6113)
19. [Jim Geelen](https://www.math.uwaterloo.ca/~jfgeelen/Research/research.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Matroid theory › Matroid minors, decomposition and excluded-minor theory*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license