Macaulay2 » Documentation
Packages » Matroids :: Matroids
next | previous | forward | backward | up | index | toc

# Matroids -- a package for computations with matroids

## Description

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 {4, 2}}}
                 cache => CacheTable{...1...}
                 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{...1...}
                 groundSet => set {0, 1, 2}
                 rank => 1

    i5 : circuits M

    o5 = {set {1}, set {3}, set {4, 0}}

    o5 : List

    i6 : netList flats M

         +-------------------+
    o6 = |set {1, 3}         |
         +-------------------+
         |set {0, 1, 3, 4}   |
         +-------------------+
         |set {1, 2, 3}      |
         +-------------------+
         |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.

## Contributors

The following people have generously contributed code, improved existing code, or enhanced the documentation: Aaron Dall, Chris Eur, Matthew Mastroeni, Jason McCullough, Tianyi Zhang.

## Author

- Justin Chen <jchen@math.berkeley.edu>

## Certification

Version 0.9.7 of this package was accepted for publication in volume 9 of The Journal of Software for Algebra and Geometry on 27 September 2018, in the article Matroids: a Macaulay2 package (DOI: 10.2140/jsag.2019.9.19). That version can be obtained from the journal.

## Version

This documentation describes version 1.7.0 of Matroids, released February 6, 2024.

## Citation

If you have used this package in your research, please cite it as follows:

    @misc{MatroidsSource,
      title = {{Matroids: computations with matroids. Version~1.7.0}},
      author = {Justin Chen},
      howpublished = {A \emph{Macaulay2} package available at
        "https://github.com/jchen419/Matroids-M2"}
    }

    @article{MatroidsArticle,
      title = {{Matroids: a \emph{Macaulay2} package}},
      author = {Justin Chen},
      journal = {The Journal of Software for Algebra and Geometry},
      volume = {9},
      year = {2018},
    }

## Exports

- 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 of rank r
  - allMinors -- returns all minors of one matroid in another
  - 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
  - coextension -- the free coextension 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
  - elementaryQuotient -- associated to a modular cut or linear subclass
  - extension -- of a matroid relative to a flat or modular cut
  - flats -- flats of a matroid
  - fundamentalCircuit -- fundamental circuit of independent set
  - getCycles -- find cycles of graph
  - getIsos -- all isomorphisms between two matroids
  - getRepresentation -- retrieves stored representation
  - getSeparation -- finds a k-separation of a matroid
  - groundSet -- (internal) ground set
  - hasMinor -- whether a matroid has a given minor
  - idealChowRing -- the defining ideal of the Chow ring
  - idealOrlikSolomonAlgebra (missing documentation)
  - indicesOf -- indices of a sublist
  - is3Connected -- whether a matroid is 3-connected
  - isBinary -- whether a matroid is representable over F_2
  - isDependent -- whether a subset is dependent
  - isElementaryQuotient -- whether a matroid is an elementary quotient of another matroid
  - isLinearSubclass -- whether a list of hyperplanes of a matroid is a linear subclass
  - isModularCut -- whether a list of flats of a matroid is a modular cut
  - isNonCrossing -- whether 2 subsets are non-crossing
  - isoTypes -- distinct isomorphism classes
  - isPositivelyOrientable -- whether a matroid is positively orientable
  - isPositivelyOriented -- whether a matroid is positively oriented
  - isQuotient -- whether a matroid is a quotient of another matroid
  - latticeOfFlats -- lattice of flats of a matroid
  - linearSubclass -- associated to an elementary quotient or modular cut
  - loops -- loops of matroid
  - matroid -- constructs a matroid
  - maxWeightBasis -- maximum weight basis using greedy algorithm
  - minor -- minor of matroid
  - modularCut -- associated to an elementary quotient or linear subclass
  - nonbases -- nonbases of matroid
  - parallelConnection -- parallel connection of two matroids
  - positiveOrientation -- a positive orientation of a matroid
  - projectiveGeometry -- projective geometry of dimension n over F_p
  - quickIsomorphismTest -- quick checks for isomorphism between matroids
  - relabel -- relabel a matroid
  - relaxation -- relaxation of matroid
  - restriction -- restriction to subset of matroid
  - `readFromFile` -- see saveMatroid -- save matroid to file
  - saveMatroid -- save matroid to file
  - searchRepresentation -- search for a representation of a matroid over a finite field
  - seriesConnection -- series connection of two matroids
  - setRepresentation -- stores user-defined representation
  - simpleMatroid -- simple matroid associated to a matroid
  - specificMatroid -- creates built-in matroid
  - `binarySpike` -- see spike -- spike matroid
  - spike -- spike matroid
  - sum2 -- 2-sum of matroids
  - swirl -- swirl matroid
  - thetaMatroid -- theta matroid
  - `fromSageMatroid` -- see toSageMatroid -- Sage format for matroid
  - toSageMatroid -- Sage format for matroid
  - tutteEvaluate -- evaluate Tutte polynomial
  - uniformMatroid -- uniform matroid
  - wheel -- wheels/whirls
  - `whirl` -- see wheel -- wheels/whirls
- Methods
  - `affineGeometry(ZZ,ZZ)` -- see affineGeometry -- affine geometry of rank n+1 over F_p
  - `allMatroids(ZZ)` -- see allMatroids -- returns all n-element matroids of rank r
  - `allMatroids(ZZ,ZZ)` -- see allMatroids -- returns all n-element matroids of rank r
  - `allMinors(Matroid,Matroid)` -- see allMinors -- returns all minors of one matroid in another
  - 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
  - `chromaticPolynomial(Graph)` -- see chromaticPolynomial -- computes chromatic polynomial of a graph
  - `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
  - `coextension(Matroid)` -- see coextension -- the free coextension 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
  - `elementaryQuotient(Matroid,List)` -- see elementaryQuotient -- associated to a modular cut or linear subclass
  - `extension(Matroid)` -- see extension -- of a matroid relative to a flat or modular cut
  - `extension(Matroid,List)` -- see extension -- of a matroid relative to a flat or modular cut
  - `extension(Matroid,Set)` -- see extension -- of a matroid relative to a flat or modular cut
  - `flats(Matroid)` -- see flats -- flats of a matroid
  - `flats(Matroid,ZZ)` -- see flats -- flats of a matroid
  - `flats(Matroid,ZZ,String)` -- 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
  - `getCycles(Graph)` -- see getCycles -- find cycles of graph
  - `getIsos(Matroid,Matroid)` -- see getIsos -- all isomorphisms between two matroids
  - `getRepresentation(Matroid)` -- see getRepresentation -- retrieves stored representation
  - `getSeparation(Matroid,ZZ)` -- see getSeparation -- finds a k-separation of a matroid
  - `groundSet(Matroid)` -- see groundSet -- (internal) ground set
  - `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
  - idealOrlikSolomonAlgebra(Matroid) (missing documentation)
  - independenceComplex(Matroid) -- independence complex of matroid
  - `independentSets(Matroid)` -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
  - `independentSets(Matroid,List)` -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
  - `independentSets(Matroid,Set)` -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
  - independentSets(Matroid,ZZ) -- independent subsets of a matroid
  - `indicesOf(List,List)` -- see indicesOf -- indices of a sublist
  - `indicesOf(Matroid,List)` -- see indicesOf -- indices of a sublist
  - `is3Connected(Matroid)` -- see is3Connected -- whether a matroid is 3-connected
  - `isBinary(Matroid)` -- see isBinary -- whether a matroid is representable over F_2
  - isConnected(Matroid) -- whether a matroid is connected
  - `isDependent(Matroid,List)` -- see isDependent -- whether a subset is dependent
  - `isDependent(Matroid,Set)` -- see isDependent -- whether a subset is dependent
  - `isElementaryQuotient(Matroid,Matroid)` -- see isElementaryQuotient -- whether a matroid is an elementary quotient of another matroid
  - `isLinearSubclass(Matroid,List)` -- see isLinearSubclass -- whether a list of hyperplanes of a matroid is a linear subclass
  - `isModularCut(Matroid,List)` -- see isModularCut -- whether a list of flats of a matroid is a modular cut
  - `isNonCrossing(List,List)` -- see isNonCrossing -- whether 2 subsets are non-crossing
  - `isNonCrossing(Set,Set)` -- see isNonCrossing -- whether 2 subsets are non-crossing
  - isomorphism(Matroid,Matroid) -- computes an isomorphism between isomorphic matroids
  - `isoTypes(List)` -- see isoTypes -- distinct isomorphism classes
  - `isPositivelyOrientable(Matroid)` -- see isPositivelyOrientable -- whether a matroid is positively orientable
  - `isPositivelyOriented(Matroid)` -- see isPositivelyOriented -- whether a matroid is positively oriented
  - `isQuotient(Matroid,Matroid)` -- see isQuotient -- whether a matroid is a quotient of another matroid
  - 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
  - `linearSubclass(Matroid,List)` -- see linearSubclass -- associated to an elementary quotient or modular cut
  - `linearSubclass(Matroid,Matroid)` -- see linearSubclass -- associated to an elementary quotient or modular cut
  - `loops(Matroid)` -- see loops -- loops of matroid
  - `matroid(Graph)` -- see matroid -- constructs a matroid
  - `matroid(Ideal)` -- see matroid -- constructs a matroid
  - `matroid(List)` -- see matroid -- constructs a matroid
  - `matroid(List,List)` -- see matroid -- constructs a matroid
  - `matroid(List,List,ZZ)` -- see matroid -- constructs a matroid
  - `matroid(List,MonomialIdeal)` -- see matroid -- constructs a matroid
  - `matroid(Matrix)` -- see matroid -- constructs a matroid
  - `matroid(ZZ,List)` -- see matroid -- constructs a 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
  - `modularCut(Matroid,List)` -- see modularCut -- associated to an elementary quotient or linear subclass
  - `modularCut(Matroid,Matroid)` -- see modularCut -- associated to an elementary quotient or linear subclass
  - `nonbases(Matroid)` -- see nonbases -- nonbases of matroid
  - `parallelConnection(Matroid,Matroid)` -- see parallelConnection -- parallel connection of two matroids
  - `positiveOrientation(Matroid)` -- see positiveOrientation -- a positive orientation of a matroid
  - `projectiveGeometry(ZZ,ZZ)` -- see projectiveGeometry -- projective geometry of dimension n over F_p
  - `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
  - `relabel(Matroid)` -- see relabel -- relabel a matroid
  - `relabel(Matroid,HashTable)` -- see relabel -- relabel a matroid
  - `relabel(Matroid,List)` -- see relabel -- relabel a matroid
  - `relaxation(Matroid)` -- see relaxation -- relaxation of matroid
  - `relaxation(Matroid,List)` -- see relaxation -- relaxation of matroid
  - `relaxation(Matroid,Set)` -- see relaxation -- relaxation of 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
  - `readFromFile(String)` -- see saveMatroid -- save matroid to file
  - `saveMatroid(Matroid)` -- see saveMatroid -- save matroid to file
  - `saveMatroid(Matroid,String)` -- see saveMatroid -- save matroid to file
  - `searchRepresentation(Matroid,GaloisField)` -- see searchRepresentation -- search for a representation of a matroid over a finite field
  - `seriesConnection(Matroid,Matroid)` -- see seriesConnection -- series connection of two matroids
  - `setRepresentation(Matroid,Matrix)` -- see setRepresentation -- stores user-defined representation
  - `simpleMatroid(Matroid)` -- see simpleMatroid -- simple matroid associated to a matroid
  - `specificMatroid(String)` -- see specificMatroid -- creates built-in matroid
  - `specificMatroid(Symbol)` -- see specificMatroid -- creates built-in matroid
  - `binarySpike(ZZ)` -- see spike -- spike matroid
  - `spike(ZZ)` -- see spike -- spike matroid
  - `spike(ZZ,List)` -- see spike -- spike matroid
  - `sum2(Matroid,Matroid)` -- see sum2 -- 2-sum of matroids
  - `swirl(ZZ)` -- see swirl -- swirl matroid
  - `thetaMatroid(ZZ)` -- see thetaMatroid -- theta matroid
  - `fromSageMatroid(String)` -- see toSageMatroid -- Sage format for matroid
  - `toSageMatroid(Matroid)` -- see toSageMatroid -- Sage format for matroid
  - `truncate(Matroid)` -- see truncate(Set,Matroid) -- the truncation of a matroid with respect to a flat
  - truncate(Set,Matroid) -- the truncation of a matroid with respect to a flat
  - truncate(ZZ,Matroid) -- the truncation of a matroid with respect to a flat
  - `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
  - `uniformMatroid(ZZ,ZZ)` -- see uniformMatroid -- uniform matroid
  - `wheel(ZZ)` -- see wheel -- wheels/whirls
  - `whirl(ZZ)` -- see wheel -- wheels/whirls
- Symbols
  - CheckWellDefined -- an optional argument
  - `ChowRingOptions` -- see idealChowRing -- the defining ideal of the Chow ring
  - `FlatOrder` -- see idealChowRing -- the defining ideal of the Chow ring
  - `Presentation` -- see idealChowRing -- the defining ideal of the Chow ring
  - `Loops` -- see matroid -- constructs a matroid
  - `ParallelEdges` -- see matroid -- constructs a matroid
  - `Attempts` -- see searchRepresentation -- search for a representation of a matroid over a finite field
  - `storedRepresentation` -- see setRepresentation -- stores user-defined representation

## For the programmer

The object Matroids is a package, defined in Matroids.m2, with auxiliary files in Matroids/.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Matroids/doc-Matroids.m2:62:0.