A matroid is a combinatorial structure abstracting the notion of (linear algebraic, graph-theoretic) independence. This package provides methods to perform computations with matroids in Macaulay2.

This package provides capabilities for converting between various representations of matroids, creating linear and graphic matroids from a matrix or graph, forming and detecting existence of minors, computing Tutte polynomials, and additional functions for applications of matroids to areas like optimization and convex geometry.

Matroids are stored as pairs (E, B) of a ground set E and a list B of bases, which are maximal independent subsets of the ground set. Internally, a ground set of size n is always identified with the set *{0, ..., n-1}*, and thus all subsets of the ground set (e.g. bases, circuits, flats) are also treated as subsets of *{0, ..., n-1}* (for more, cf. groundSet). However, the actual elements of the ground set are allowed to be arbitrary (e.g. integers, symbols, vectors, edges in a graph), and can be accessed by taking subscripts.

i1 : M = matroid({a, matrix{{-1.2},{3.78}}, x, set{4,6}, -9}, {{a, x}, {x, -9}}) o1 = a matroid of rank 2 on 5 elements o1 : Matroid |

i2 : peek M o2 = Matroid{bases => {set {0, 2}, set {2, 4}}} cache => CacheTable{...2...} groundSet => set {0, 1, 2, 3, 4} rank => 2 |

i3 : M_{0,1,4} o3 = {a, | -1.2 |, -9} | 3.78 | o3 : List |

i4 : peek restriction(M, set{1,2,3}) o4 = Matroid{bases => {set {1}} } cache => CacheTable{...2...} groundSet => set {0, 1, 2} rank => 1 |

i5 : circuits M o5 = {set {1}, set {3}, set {0, 4}} o5 : List |

i6 : netList flats M +-------------------+ o6 = |set {1, 3} | +-------------------+ |set {1, 2, 3} | +-------------------+ |set {0, 1, 3, 4} | +-------------------+ |set {0, 1, 2, 3, 4}| +-------------------+ |

i7 : tuttePolynomial M 2 2 3 o7 = x y + x*y o7 : ZZ[x, y] |

A matroid can be specified by its bases, nonbases, circuits, from a matrix, graph, or ideal, or via a collection of predefined matroids. For more on how to construct a matroid, see matroid.

**Reference** Oxley, Matroid Theory, second edition. Oxford University Press, 2011.

Version **0.9.7** of this package was accepted for publication in volume 9 of the journal The Journal of Software for Algebra and Geometry on 27 September 2018, in the article Matroids: a Macaulay2 package. That version can be obtained from the journal or from the *Macaulay2* source code repository, http://github.com/Macaulay2/M2/blob/master/M2/Macaulay2/packages/....m2, commit number cf37f5a1eefc2fe7e6eef2868718256106805027.

- Types
- Matroid -- the class of all matroids

- Functions and commands
- affineGeometry -- affine geometry of rank n+1 over F_p
- allMatroids -- returns all n-element matroids
- bases -- bases of matroid
- basisIndicatorMatrix -- matrix of basis polytope
- chromaticPolynomial -- computes chromatic polynomial of a graph
- circuits -- circuits of matroid
- closure -- closure of a subset of a matroid
- cogeneratorChowRing -- cogenerator of the Chow ring of a matroid
- coloops -- coloops of matroid
- contraction -- contraction of subset of matroid
- deletion -- deletion of subset of matroid
- flats -- flats of a matroid
- fundamentalCircuit -- fundamental circuit of independent set
- getCycles -- find cycles of graph
- getIsos -- all isomorphisms between two matroids
- hasMinor -- whether a matroid has a given minor
- hyperplanes -- hyperplanes of a matroid
- idealChowRing -- the defining ideal of the Chow ring
- indicesOf -- indices of a sublist
- isDependent -- whether a subset is dependent
- latticeOfFlats -- lattice of flats of a matroid
- loops -- loops of matroid
- matroid -- constructs a matroid
- maxWeightBasis -- maximum weight basis using greedy algorithm
- minor -- minor of matroid
- nonbases -- nonbases of matroid
- projectiveGeometry -- projective geometry of dimension n over F_p
- quickIsomorphismTest -- quick checks for isomorphism between matroids
- relaxation -- relaxation of matroid
- representationOf -- represents a realizable/graphic matroid
- restriction -- restriction to subset of matroid
- simpleMatroid -- simple matroid associated to a matroid
- specificMatroid -- creates built-in matroid
- tutteEvaluate -- evaluate Tutte polynomial
- uniformMatroid -- uniform matroid

- Methods
- areIsomorphic(Matroid,Matroid) -- whether two matroids are isomorphic
- bases(Matroid), see bases -- bases of matroid
- basisIndicatorMatrix(Matroid), see basisIndicatorMatrix -- matrix of basis polytope
- characteristicPolynomial(Matroid) -- computes characteristic polynomial of a matroid
- circuits(Matroid), see circuits -- circuits of matroid
- closure(Matroid,List), see closure -- closure of a subset of a matroid
- closure(Matroid,Set), see closure -- closure of a subset of a matroid
- cogeneratorChowRing(Matroid), see cogeneratorChowRing -- cogenerator of the Chow ring of a matroid
- coloops(Matroid), see coloops -- coloops of matroid
- components(Matroid) -- connected components of matroid
- contraction(Matroid,List), see contraction -- contraction of subset of matroid
- contraction(Matroid,Set), see contraction -- contraction of subset of matroid
- Matroid / List, see contraction -- contraction of subset of matroid
- Matroid / Set, see contraction -- contraction of subset of matroid
- deletion(Matroid,List), see deletion -- deletion of subset of matroid
- deletion(Matroid,Set), see deletion -- deletion of subset of matroid
- Matroid \ List, see deletion -- deletion of subset of matroid
- Matroid \ Set, see deletion -- deletion of subset of matroid
- dual(Matroid) -- dual matroid
- flats(Matroid), see flats -- flats of a matroid
- flats(Matroid,ZZ), see flats -- flats of a matroid
- fundamentalCircuit(Matroid,List,Thing), see fundamentalCircuit -- fundamental circuit of independent set
- fundamentalCircuit(Matroid,Set,ZZ), see fundamentalCircuit -- fundamental circuit of independent set
- fVector(Matroid) -- f-vector of a matroid
- getIsos(Matroid,Matroid), see getIsos -- all isomorphisms between two matroids
- hasMinor(Matroid,Matroid), see hasMinor -- whether a matroid has a given minor
- hyperplanes(Matroid), see hyperplanes -- hyperplanes of a matroid
- ideal(Matroid) -- Stanley-Reisner (circuit) ideal of matroid
- idealChowRing(Matroid), see idealChowRing -- the defining ideal of the Chow ring
- independenceComplex(Matroid) -- independence complex of matroid
- independentSets(Matroid) -- independent subsets of a matroid
- independentSets(Matroid,ZZ), see independentSets(Matroid) -- independent subsets of a matroid
- indicesOf(Matroid,List), see indicesOf -- indices of a sublist
- isDependent(Matroid,List), see isDependent -- whether a subset is dependent
- isDependent(Matroid,Set), see isDependent -- whether a subset is dependent
- isomorphism(Matroid,Matroid) -- computes an isomorphism between isomorphic matroids
- isSimple(Matroid) -- whether a matroid is simple
- isWellDefined(Matroid) -- whether the input is a well-defined matroid
- latticeOfFlats(Matroid), see latticeOfFlats -- lattice of flats of a matroid
- loops(Matroid), see loops -- loops of matroid
- Matroid + Matroid -- union of matroids
- Matroid ++ Matroid -- direct sum of matroids
- Matroid == Matroid -- whether two matroids are equal
- Matroid _ List -- elements of matroid
- Matroid _ Set, see Matroid _ List -- elements of matroid
- Matroid _ ZZ, see Matroid _ List -- elements of matroid
- Matroid _*, see Matroid _ List -- elements of matroid
- maxWeightBasis(Matroid,List), see maxWeightBasis -- maximum weight basis using greedy algorithm
- minor(Matroid,List,List), see minor -- minor of matroid
- minor(Matroid,Set,Set), see minor -- minor of matroid
- nonbases(Matroid), see nonbases -- nonbases of matroid
- quickIsomorphismTest(Matroid,Matroid), see quickIsomorphismTest -- quick checks for isomorphism between matroids
- rank(Matroid) -- rank of a matroid
- rank(Matroid,List), see rank(Matroid,Set) -- rank of a subset of a matroid
- rank(Matroid,Set) -- rank of a subset of a matroid
- relaxation(Matroid,List), see relaxation -- relaxation of matroid
- relaxation(Matroid,Set), see relaxation -- relaxation of matroid
- representationOf(Matroid), see representationOf -- represents a realizable/graphic matroid
- Matroid | List, see restriction -- restriction to subset of matroid
- Matroid | Set, see restriction -- restriction to subset of matroid
- restriction(Matroid,List), see restriction -- restriction to subset of matroid
- restriction(Matroid,Set), see restriction -- restriction to subset of matroid
- simpleMatroid(Matroid), see simpleMatroid -- simple matroid associated to a matroid
- tutteEvaluate(Matroid,Thing,Thing), see tutteEvaluate -- evaluate Tutte polynomial
- tuttePolynomial(Matroid) -- Tutte polynomial of a matroid
- tuttePolynomial(Matroid,Ring), see tuttePolynomial(Matroid) -- Tutte polynomial of a matroid

- Symbols
- groundSet -- (internal) ground set