Matroid construction#
Theory#
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:
\(I\) contains the empty set
If \(X\) is a set in \(I\), then each subset of \(X\) is in \(I\)
If two subsets \(X\), \(Y\) are in \(I\), and \(|X| > |Y|\), then there exists \(x \in X - Y\) such that \(Y + \{x\}\) is in \(I\).
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.
Built-in matroids#
For built-in matroids, do the following:
Within a Sage session, type
matroids.(Do not press Enter, and do not forget the final period “.”)Hit Tab.
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
Constructing matroids#
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()) # needs sage.graphs
sage: M.rank() # needs sage.graphs
9
AUTHORS:
Rudi Pendavingh, Michael Welsh, Stefan van Zwam (2013-04-01): initial version
Functions#
- sage.matroids.constructor.Matroid(groundset=None, data=None, **kwds)#
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:
\(I\) contains the empty set
If \(X\) is a set in \(I\), then each subset of \(X\) is in \(I\)
If two subsets \(X\), \(Y\) are in \(I\), and \(|X| > |Y|\), then there exists \(x \in X - Y\) such that \(Y + \{x\}\) is in \(I\).
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:
Within a Sage session, type “matroids.” (Do not press Enter, and do not forget the final period “.”)
Hit Tab.
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:
groundset– (optional) If provided, the groundset of the matroid. Otherwise, the function attempts to determine a groundset from the data.
Exactly one of the following inputs must be given (where
datamust be a positional argument and anything else must be a keyword argument):data– a graph or a matrix or a RevLex-Index string or a list of independent sets containing all bases or a matroid.bases– The list of bases (maximal independent sets) of the matroid.independent_sets– The list of independent sets of the matroid.circuits– The list of circuits of the matroid.graph– A graph, whose edges form the elements of the matroid.matrix– A matrix representation of the matroid.reduced_matrix– A reduced representation of the matroid: ifreduced_matrix = Athen the matroid is represented by \([I\ \ A]\) where \(I\) is an appropriately sized identity matrix.rank_function– A function that computes the rank of each subset. Can only be provided together with a groundset.circuit_closures– Either a list of tuples(k, C)withCthe closure of a circuit, andkthe rank ofC, or a dictionaryDwithD[k]the set of closures of rank-kcircuits.revlex– the encoding as a string of0and*symbols. Used by [MatroidDatabase] and explained in [MMIB2012].matroid– An object that is already a matroid. Useful only with theregularoption.
Further options:
regular– (default:False) boolean. IfTrue, output aRegularMatroidinstance such that, if the input defines a valid regular matroid, then the output represents this matroid. Note that this option can be combined with any type of input.ring– any ring. If provided, and the input is amatrixorreduced_matrix, output will be a linear matroid over the ring or fieldring.field– any field. Same asring, but only fields are allowed.check– (default:True) boolean. IfTrueandregularis true, the output is checked to make sure it is a valid regular matroid.
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 typeBasisMatroid,CircuitClosuresMatroid,LinearMatroid,BinaryMatroid,TernaryMatroid,QuaternaryMatroid,RegularMatroid, orRankMatroid. 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 True
We 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() False
Bases 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 True
A matroid specified by a list of circuits gets converted to a
BasisMatroidinternally:sage: M = Matroid(groundset='abcd', circuits=['abc', 'abd', 'acd', ....: 'bcd']) sage: type(M) <... '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()] # random [['a']]
Graph:
Sage has great support for graphs, see
sage.graphs.graph.sage: G = graphs.PetersenGraph() # needs sage.graphs sage: Matroid(G) # needs sage.graphs Graphic matroid of rank 9 on 15 elements
If each edge has a unique label, then those are used as the ground set labels:
sage: G = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'c')]) # needs sage.graphs sage: M = Matroid(G) # needs sage.graphs sage: sorted(M.groundset()) # needs sage.graphs ['a', 'b', 'c']
If there are parallel edges, then integers are used for the ground set. If there are no edges in parallel, and is not a complete list of labels, or the labels are not unique, then vertex tuples are used:
sage: # needs sage.graphs sage: G = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'b')]) sage: M = Matroid(G) sage: sorted(M.groundset()) [(0, 1), (0, 2), (1, 2)] sage: H = Graph([(0, 1, 'a'), (0, 2, 'b'), (1, 2, 'b'), (1, 2, 'c')], ....: multiedges=True) sage: N = Matroid(H) sage: sorted(N.groundset()) [0, 1, 2, 3]
The GraphicMatroid object forces its graph to be connected. If a disconnected graph is used as input, it will connect the components:
sage: # needs sage.graphs sage: G1 = graphs.CycleGraph(3); G2 = graphs.DiamondGraph() sage: G = G1.disjoint_union(G2) sage: M = Matroid(G); M Graphic matroid of rank 5 on 8 elements sage: M.graph() Looped multi-graph on 6 vertices sage: M.graph().is_connected() True sage: M.is_connected() False
If the keyword
regularis set toTrue, the output will instead be an instance ofRegularMatroid.sage: G = Graph([(0, 1), (0, 2), (1, 2)]) # needs sage.graphs sage: M = Matroid(G, regular=True); M # needs sage.graphs Regular matroid of rank 2 on 3 elements with 3 bases
Note: 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)], multiedges=True) # needs sage.graphs sage: M = Matroid('abcd', G) # needs sage.graphs sage: M.rank(['b', 'c']) # needs sage.graphs 1
As before, 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)]) # needs sage.graphs sage: M = Matroid(G, regular=True) # needs sage.graphs sage: sorted(M.groundset()) # needs sage.graphs [(0, 1), (0, 2), (1, 2)] sage: G = Graph([(0, 1), (0, 2), (0, 2), (1, 2)], multiedges=True) # needs sage.graphs sage: M = Matroid(G, regular=True) # needs sage.graphs sage: sorted(M.groundset()) # needs sage.graphs [0, 1, 2, 3]
When the
graphkeyword is used, a variety of inputs can be converted to a graph automatically. The following uses a graph6 string (see theGraphmethod’s documentation):sage: Matroid(graph=':I`AKGsaOs`cI]Gb~') # needs sage.graphs Graphic matroid of rank 9 on 17 elements
However, this method is no more clever than
Graph():sage: Matroid(graph=41/2) # needs sage.graphs Traceback (most recent call last): ... ValueError: This input cannot be turned into 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)) # needs sage.graphs True
Various 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 True
However, with unnamed arguments the input has to be a
Matrixinstance, 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() 3
We 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], # needs sage.rings.finite_rings ....: 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], # needs sage.graphs ....: 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 bases
Otherwise 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 83
An 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()) True
You 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()) # needs sage.rings.finite_rings True
RevLex-Index:
This requires the
groundsetto be given and also needs a additional keyword argumentrankto specify the rank of the matroid:sage: M = Matroid("abcdef", "000000******0**", rank=4); M Matroid of rank 4 on 6 elements with 8 bases sage: list(M.bases()) [frozenset({'a', 'b', 'd', 'f'}), frozenset({'a', 'c', 'd', 'f'}), frozenset({'b', 'c', 'd', 'f'}), frozenset({'a', 'b', 'e', 'f'}), frozenset({'a', 'c', 'e', 'f'}), frozenset({'b', 'c', 'e', 'f'}), frozenset({'b', 'd', 'e', 'f'}), frozenset({'c', 'd', 'e', 'f'})]
Only the
0symbols really matter, any symbol can be used instead of*:sage: Matroid(“abcdefg”, revlex=”0++++++++0++++0+++++0+–++—-+–++”, rank=4) Matroid of rank 4 on 7 elements with 31 bases
It is checked that the input makes sense (but not that it defines a matroid):
sage: Matroid("abcdef", "000000******0**") Traceback (most recent call last): ... TypeError: for RevLex-Index, the rank needs to be specified sage: Matroid("abcdef", "000000******0**", rank=3) Traceback (most recent call last): ... ValueError: expected string of length 20 (6 choose 3), got 15 sage: M = Matroid("abcdef", "*0000000000000*", rank=4); M Matroid of rank 4 on 6 elements with 2 bases sage: M.is_valid() False
Matroid:
Most of the time, the matroid itself is returned:
sage: M = matroids.named_matroids.Fano() sage: N = Matroid(M) sage: N is M True
But it can be useful with the
regularoption:sage: M = Matroid(circuit_closures={2:['adb', 'bec', 'cfa', ....: 'def'], 3:['abcdef']}) sage: N = Matroid(M, regular=True); N # needs sage.graphs Regular matroid of rank 3 on 6 elements with 16 bases sage: M == N # needs sage.graphs False sage: M.is_isomorphic(N) # needs sage.graphs True sage: Matrix(N) # random # needs sage.graphs [1 0 0 1 1 0] [0 1 0 1 1 1] [0 0 1 0 1 1]
The
regularoption:sage: M = Matroid(reduced_matrix=[[1, 1, 0], # needs sage.graphs ....: [1, 0, 1], ....: [0, 1, 1]], regular=True); M Regular matroid of rank 3 on 6 elements with 16 bases sage: M.is_isomorphic(matroids.CompleteGraphic(4)) # needs sage.graphs True
By 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) # needs sage.graphs Traceback (most recent call last): ... ValueError: input is not a valid regular matroid sage: N = Matroid(M, regular=True, check=False); N # needs sage.graphs Regular matroid of rank 3 on 7 elements with 32 bases sage: N.is_valid() # needs sage.graphs False
Sometimes 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]]), # needs sage.graphs ....: regular=True) sage: N.is_valid() # needs sage.graphs True sage: N.is_isomorphic(M) # needs sage.graphs False