# 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 {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.

## 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. That version can be obtained from the journal or from the Macaulay2 source code repository.

## Version

This documentation describes version 1.3.0 of Matroids.

## Source code

The source code from which this documentation is derived is in the file Matroids.m2. The auxiliary files accompanying it are in the directory Matroids/.

## For the programmer

The object Matroids is .