Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/...) dependence. Formally, a matroid is a pair \(M = (E, I)\) of a finite set \(E\), the groundset, and a collection of subsets \(I\), the independent sets, subject to the following axioms:
See the Wikipedia article on matroids for more theory and examples. Matroids can be obtained from many types of mathematical structures, and Sage supports a number of them.
There are two main entry points to Sage’s matroid functionality. The object matroids. contains a number of constructors for well-known matroids. The function Matroid() allows you to define your own matroids from a variety of sources. We briefly introduce both below; follow the links for more comprehensive documentation.
Each matroid object in Sage comes with a number of built-in operations. An overview can be found in the documentation of the abstract matroid class.
For built-in matroids, do the following:
You will see a list of methods which will construct matroids. For example:
sage: M = matroids.Wheel(4)
sage: M.is_connected()
True
or:
sage: U36 = matroids.Uniform(3, 6)
sage: U36.equals(U36.dual())
True
A number of special matroids are collected under a named_matroids submenu. To see which, type matroids.named_matroids.<tab> as above:
sage: F7 = matroids.named_matroids.Fano()
sage: len(F7.nonspanning_circuits())
7
To define your own matroid, use the function Matroid(). This function attempts to interpret its arguments to create an appropriate matroid. The input arguments are documented in detail below.
EXAMPLES:
sage: A = Matrix(GF(2), [[1, 0, 0, 0, 1, 1, 1],
....: [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 1, 1, 0, 1]])
sage: M = Matroid(A)
sage: M.is_isomorphic(matroids.named_matroids.Fano())
True
sage: M = Matroid(graphs.PetersenGraph())
sage: M.rank()
9
AUTHORS:
Construct a matroid.
Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/...) dependence. Formally, a matroid is a pair \(M = (E, I)\) of a finite set \(E\), the groundset, and a collection of subsets \(I\), the independent sets, subject to the following axioms:
See the Wikipedia article on matroids for more theory and examples. Matroids can be obtained from many types of mathematical structures, and Sage supports a number of them.
There are two main entry points to Sage’s matroid functionality. For built-in matroids, do the following:
You will see a list of methods which will construct matroids. For example:
sage: F7 = matroids.named_matroids.Fano()
sage: len(F7.nonspanning_circuits())
7
or:
sage: U36 = matroids.Uniform(3, 6)
sage: U36.equals(U36.dual())
True
To define your own matroid, use the function Matroid(). This function attempts to interpret its arguments to create an appropriate matroid. The following named arguments are supported:
INPUT:
Up to two unnamed arguments are allowed.
The examples section details how each of the input types deals with explicit or implicit groundset arguments.
OPTIONS:
Warning
Except for regular matroids, the input is not checked for validity. If your data does not correspond to an actual matroid, the behavior of the methods is undefined and may cause strange errors. To ensure you have a matroid, run M.is_valid().
Note
The Matroid() method will return instances of type BasisMatroid, CircuitClosuresMatroid, LinearMatroid, BinaryMatroid, TernaryMatroid, QuaternaryMatroid, RegularMatroid, or RankMatroid. To import these classes (and other useful functions) directly into Sage’s main namespace, type:
sage: from sage.matroids.advanced import *
EXAMPLES:
Note that in these examples we will often use the fact that strings are iterable in these examples. So we type 'abcd' to denote the list ['a', 'b', 'c', 'd'].
List of bases:
All of the following inputs are allowed, and equivalent:
sage: M1 = Matroid(groundset='abcd', bases=['ab', 'ac', 'ad', ....: 'bc', 'bd', 'cd']) sage: M2 = Matroid(bases=['ab', 'ac', 'ad', 'bc', 'bd', 'cd']) sage: M3 = Matroid(['ab', 'ac', 'ad', 'bc', 'bd', 'cd']) sage: M4 = Matroid('abcd', ['ab', 'ac', 'ad', 'bc', 'bd', 'cd']) sage: M5 = Matroid('abcd', bases=[['a', 'b'], ['a', 'c'], ....: ['a', 'd'], ['b', 'c'], ....: ['b', 'd'], ['c', 'd']]) sage: M1 == M2 True sage: M1 == M3 True sage: M1 == M4 True sage: M1 == M5 TrueWe do not check if the provided input forms an actual matroid:
sage: M1 = Matroid(groundset='abcd', bases=['ab', 'cd']) sage: M1.full_rank() 2 sage: M1.is_valid() FalseBases may be repeated:
sage: M1 = Matroid(['ab', 'ac']) sage: M2 = Matroid(['ab', 'ac', 'ab']) sage: M1 == M2 True
List of independent sets:
sage: M1 = Matroid(groundset='abcd', ....: independent_sets=['', 'a', 'b', 'c', 'd', 'ab', ....: 'ac', 'ad', 'bc', 'bd', 'cd'])We only require that the list of independent sets contains each basis of the matroid; omissions of smaller independent sets and repetitions are allowed:
sage: M1 = Matroid(bases=['ab', 'ac']) sage: M2 = Matroid(independent_sets=['a', 'ab', 'b', 'ab', 'a', ....: 'b', 'ac']) sage: M1 == M2 True
List of circuits:
sage: M1 = Matroid(groundset='abc', circuits=['bc']) sage: M2 = Matroid(bases=['ab', 'ac']) sage: M1 == M2 TrueA matroid specified by a list of circuits gets converted to a BasisMatroid internally:
sage: M = Matroid(groundset='abcd', circuits=['abc', 'abd', 'acd', ....: 'bcd']) sage: type(M) <type 'sage.matroids.basis_matroid.BasisMatroid'>Strange things can happen if the input does not satisfy the circuit axioms, and these are not always caught by the is_valid() method. So always check whether your input makes sense!
sage: M = Matroid('abcd', circuits=['ab', 'acd']) sage: M.is_valid() True sage: [sorted(C) for C in M.circuits()] [['a']]
Graph:
Sage has great support for graphs, see sage.graphs.graph.
sage: G = graphs.PetersenGraph() sage: Matroid(G) Regular matroid of rank 9 on 15 elements with 2000 basesNote: if a groundset is specified, we assume it is in the same order as G.edge_iterator() provides:
sage: G = Graph([(0, 1), (0, 2), (0, 2), (1, 2)]) sage: M = Matroid('abcd', G) sage: M.rank(['b', 'c']) 1If no groundset is provided, we attempt to use the edge labels:
sage: G = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'c')]) sage: M = Matroid(G) sage: sorted(M.groundset()) ['a', 'b', 'c']If no edge labels are present and the graph is simple, we use the tuples (i, j) of endpoints. If that fails, we simply use a list [0..m-1]
sage: G = Graph([(0, 1), (0, 2), (1, 2)]) sage: M = Matroid(G) sage: sorted(M.groundset()) [(0, 1), (0, 2), (1, 2)] sage: G = Graph([(0, 1), (0, 2), (0, 2), (1, 2)]) sage: M = Matroid(G) sage: sorted(M.groundset()) [0, 1, 2, 3]When the graph keyword is used, a variety of inputs can be converted to a graph automatically. The following uses a graph6 string (see the Graph method’s documentation):
sage: Matroid(graph=':I`AKGsaOs`cI]Gb~') Regular matroid of rank 9 on 17 elements with 4004 basesHowever, this method is no more clever than Graph():
sage: Matroid(graph=41/2) Traceback (most recent call last): ... ValueError: input does not seem to represent a graph.
Matrix:
The basic input is a Sage matrix:
sage: A = Matrix(GF(2), [[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 0, 1], ....: [0, 0, 1, 0, 1, 1]]) sage: M = Matroid(matrix=A) sage: M.is_isomorphic(matroids.CompleteGraphic(4)) TrueVarious shortcuts are possible:
sage: M1 = Matroid(matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 0, 1], ....: [0, 0, 1, 0, 1, 1]], ring=GF(2)) sage: M2 = Matroid(reduced_matrix=[[1, 1, 0], ....: [1, 0, 1], ....: [0, 1, 1]], ring=GF(2)) sage: M3 = Matroid(groundset=[0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: ring=GF(2)) sage: A = Matrix(GF(2), [[1, 1, 0], [1, 0, 1], [0, 1, 1]]) sage: M4 = Matroid([0, 1, 2, 3, 4, 5], A) sage: M1 == M2 True sage: M1 == M3 True sage: M1 == M4 TrueHowever, with unnamed arguments the input has to be a Matrix instance, or the function will try to interpret it as a set of bases:
sage: Matroid([0, 1, 2], [[1, 0, 1], [0, 1, 1]]) Traceback (most recent call last): ... ValueError: basis has wrong cardinality.If the groundset size equals number of rows plus number of columns, an identity matrix is prepended. Otherwise the groundset size must equal the number of columns:
sage: A = Matrix(GF(2), [[1, 1, 0], [1, 0, 1], [0, 1, 1]]) sage: M = Matroid([0, 1, 2], A) sage: N = Matroid([0, 1, 2, 3, 4, 5], A) sage: M.rank() 2 sage: N.rank() 3We automatically create an optimized subclass, if available:
sage: Matroid([0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: field=GF(2)) Binary matroid of rank 3 on 6 elements, type (2, 7) sage: Matroid([0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: field=GF(3)) Ternary matroid of rank 3 on 6 elements, type 0- sage: Matroid([0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: field=GF(4, 'x')) Quaternary matroid of rank 3 on 6 elements sage: Matroid([0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: field=GF(2), regular=True) Regular matroid of rank 3 on 6 elements with 16 basesOtherwise the generic LinearMatroid class is used:
sage: Matroid([0, 1, 2, 3, 4, 5], ....: matrix=[[1, 1, 0], [1, 0, 1], [0, 1, 1]], ....: field=GF(83)) Linear matroid of rank 3 on 6 elements represented over the Finite Field of size 83An integer matrix is automatically converted to a matrix over \(\QQ\). If you really want integers, you can specify the ring explicitly:
sage: A = Matrix([[1, 1, 0], [1, 0, 1], [0, 1, -1]]) sage: A.base_ring() Integer Ring sage: M = Matroid([0, 1, 2, 3, 4, 5], A) sage: M.base_ring() Rational Field sage: M = Matroid([0, 1, 2, 3, 4, 5], A, ring=ZZ) sage: M.base_ring() Integer Ring
Rank function:
Any function mapping subsets to integers can be used as input:
sage: def f(X): ....: return min(len(X), 2) ....: sage: M = Matroid('abcd', rank_function=f) sage: M Matroid of rank 2 on 4 elements sage: M.is_isomorphic(matroids.Uniform(2, 4)) True
Circuit closures:
This is often a really concise way to specify a matroid. The usual way is a dictionary of lists:
sage: M = Matroid(circuit_closures={3: ['edfg', 'acdg', 'bcfg', ....: 'cefh', 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'], ....: 4: ['abcdefgh']}) sage: M.equals(matroids.named_matroids.P8()) TrueYou can also input tuples \((k, X)\) where \(X\) is the closure of a circuit, and \(k\) the rank of \(X\):
sage: M = Matroid(circuit_closures=[(2, 'abd'), (3, 'abcdef'), ....: (2, 'bce')]) sage: M.equals(matroids.named_matroids.Q6()) True
Matroid:
Most of the time, the matroid itself is returned:
sage: M = matroids.named_matroids.Fano() sage: N = Matroid(M) sage: N is M TrueBut it can be useful with the regular option:
sage: M = Matroid(circuit_closures={2:['adb', 'bec', 'cfa', ....: 'def'], 3:['abcdef']}) sage: N = Matroid(M, regular=True) sage: N Regular matroid of rank 3 on 6 elements with 16 bases sage: Matrix(N) [1 0 0 1 1 0] [0 1 0 1 1 1] [0 0 1 0 1 1]
The regular option:
sage: M = Matroid(reduced_matrix=[[1, 1, 0], ....: [1, 0, 1], ....: [0, 1, 1]], regular=True) sage: M Regular matroid of rank 3 on 6 elements with 16 bases sage: M.is_isomorphic(matroids.CompleteGraphic(4)) TrueBy default we check if the resulting matroid is actually regular. To increase speed, this check can be skipped:
sage: M = matroids.named_matroids.Fano() sage: N = Matroid(M, regular=True) Traceback (most recent call last): ... ValueError: input does not correspond to a valid regular matroid. sage: N = Matroid(M, regular=True, check=False) sage: N Regular matroid of rank 3 on 7 elements with 32 bases sage: N.is_valid() FalseSometimes the output is regular, but represents a different matroid from the one you intended:
sage: M = Matroid(Matrix(GF(3), [[1, 0, 1, 1], [0, 1, 1, 2]])) sage: N = Matroid(Matrix(GF(3), [[1, 0, 1, 1], [0, 1, 1, 2]]), ....: regular=True) sage: N.is_valid() True sage: N.is_isomorphic(M) False