The abstract Matroid class¶
Matroids are combinatorial structures that capture the abstract properties
of (linear/algebraic/...) dependence. See the Wikipedia article on
matroids for theory and examples. In Sage, various types of
matroids are supported:
BasisMatroid
,
CircuitClosuresMatroid
,
LinearMatroid
(and some specialized subclasses),
RankMatroid
.
To construct them, use the function
Matroid()
.
All these classes share a common interface, which includes the following
methods (organized by category). Note that most subclasses (notably
LinearMatroids
) will implement
additional functionality (e.g. linear extensions).
 Ground set:
 Rank, bases, circuits, closure
rank()
full_rank()
basis()
max_independent()
circuit()
fundamental_circuit()
closure()
augment()
corank()
full_corank()
cobasis()
max_coindependent()
cocircuit()
fundamental_cocircuit()
coclosure()
is_independent()
is_dependent()
is_basis()
is_circuit()
is_closed()
is_coindependent()
is_codependent()
is_cobasis()
is_cocircuit()
is_coclosed()
 Verification
 Comparison
 Minors, duality, truncation
 Representation
 Invariants
In addition to these, all methods provided by
SageObject
are available,
notably save()
and
rename()
.
Advanced usage¶
Many methods (such as M.rank()
) have a companion method whose name starts
with an underscore (such as M._rank()
). The method with the underscore
does not do any checks on its input. For instance, it may assume of its input
that
 It is a subset of the groundset. The interface is compatible with Python’s
frozenset
type.  It is a list of things, supports iteration, and recursively these rules apply to its members.
Using the underscored version could improve the speed of code a little, but will generate more cryptic error messages when presented with wrong input. In some instances, no error might occur and a nonsensical answer returned.
A subclass should always override the underscored method, if available, and as a rule leave the regular method alone.
These underscored methods are not documented in the reference manual. To see
them, within Sage you can create a matroid M
and type M._<tab>
. Then
M._rank?
followed by <tab>
will bring up the documentation string of
the _rank()
method.
Creating new Matroid subclasses¶
Many mathematical objects give rise to matroids, and not all are available
through the provided code. For incidental use, the
RankMatroid
subclass may suffice. If you
regularly use matroids based on a new data type, you can write a subclass of
Matroid
. You only need to override the __init__
, _rank()
and
groundset()
methods to get a fully working class.
EXAMPLES:
In a partition matroid, a subset is independent if it has at most one element from each partition. The following is a very basic implementation, in which the partition is specified as a list of lists:
sage: import sage.matroids.matroid
sage: class PartitionMatroid(sage.matroids.matroid.Matroid):
....: def __init__(self, partition):
....: self.partition = partition
....: E = set()
....: for P in partition:
....: E.update(P)
....: self.E = frozenset(E)
....: def groundset(self):
....: return self.E
....: def _rank(self, X):
....: X2 = set(X)
....: used_indices = set()
....: rk = 0
....: while len(X2) > 0:
....: e = X2.pop()
....: for i in range(len(self.partition)):
....: if e in self.partition[i]:
....: if i not in used_indices:
....: used_indices.add(i)
....: rk = rk + 1
....: break
....: return rk
....:
sage: M = PartitionMatroid([[1, 2], [3, 4, 5], [6, 7]])
sage: M.full_rank()
3
sage: M.tutte_polynomial(var('x'), var('y'))
x^2*y^2 + 2*x*y^3 + y^4 + x^3 + 3*x^2*y + 3*x*y^2 + y^3
Note
The abstract base class has no idea about the data used to represent the matroid. Hence some methods need to be customized to function properly.
Necessary:
def __init__(self, ...)
def groundset(self)
def _rank(self, X)
Representation:
def _repr_(self)
Comparison:
def __hash__(self)
def __eq__(self, other)
def __ne__(self, other)
In Cythonized classes, use __richcmp__()
instead of __eq__()
,
__ne__()
.
Copying, loading, saving:
def __copy__(self)
def __deepcopy__(self, memo={})
def __reduce__(self)
See, for instance, rank_matroid
or
circuit_closures_matroid
for sample implementations of these.
Note
The example provided does not check its input at all. You may want to make sure the input data are not corrupt.
Some examples¶
EXAMPLES:
Construction:
sage: M = Matroid(Matrix(QQ, [[1, 0, 0, 0, 1, 1, 1],
....: [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 1, 1, 0, 1]]))
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
sage: M.rank([0, 1, 2])
3
sage: M.rank([0, 1, 5])
2
Minors:
sage: M = Matroid(Matrix(QQ, [[1, 0, 0, 0, 1, 1, 1],
....: [0, 1, 0, 1, 0, 1, 1],
....: [0, 0, 1, 1, 1, 0, 1]]))
sage: N = M / [2] \ [3, 4]
sage: sorted(N.groundset())
[0, 1, 5, 6]
sage: N.full_rank()
2
Testing. Note that the abstract base class does not support pickling:
sage: M = sage.matroids.matroid.Matroid()
sage: TestSuite(M).run(skip="_test_pickling")
REFERENCES¶
 [BC1977]
 [Cun1986]
 [CMO2011]
 [CMO2012]
 [GG2012]
 [GR2001]
 [Hli2006]
 [Hoc]
 [Lyo2003]
 [Oxl1992]
 [Oxl2011]
 [Pen2012]
 [PvZ2010]
 [Raj1987]
AUTHORS:
 Michael Welsh (20130403): Changed flats() to use SetSystem
 Michael Welsh (20130401): Added is_3connected(), using naive algorithm
 Rudi Pendavingh, Stefan van Zwam (20130401): initial version
Methods¶

class
sage.matroids.matroid.
Matroid
¶ Bases:
sage.structure.sage_object.SageObject
The abstract matroid class, from which all matroids are derived. Do not use this class directly!
To implement a subclass, the least you should do is implement the
__init__()
,_rank()
andgroundset()
methods. See the source ofrank_matroid.py
for a barebones example of this.EXAMPLES:
In a partition matroid, a subset is independent if it has at most one element from each partition. The following is a very basic implementation, in which the partition is specified as a list of lists:
sage: class PartitionMatroid(sage.matroids.matroid.Matroid): ....: def __init__(self, partition): ....: self.partition = partition ....: E = set() ....: for P in partition: ....: E.update(P) ....: self.E = frozenset(E) ....: def groundset(self): ....: return self.E ....: def _rank(self, X): ....: X2 = set(X) ....: used_indices = set() ....: rk = 0 ....: while len(X2) > 0: ....: e = X2.pop() ....: for i in range(len(self.partition)): ....: if e in self.partition[i]: ....: if i not in used_indices: ....: used_indices.add(i) ....: rk = rk + 1 ....: break ....: return rk ....: sage: M = PartitionMatroid([[1, 2], [3, 4, 5], [6, 7]]) sage: M.full_rank() 3 sage: M.tutte_polynomial(var('x'), var('y')) x^2*y^2 + 2*x*y^3 + y^4 + x^3 + 3*x^2*y + 3*x*y^2 + y^3
Note
The abstract base class has no idea about the data used to represent the matroid. Hence some methods need to be customized to function properly.
Necessary:
def __init__(self, ...)
def groundset(self)
def _rank(self, X)
Representation:
def _repr_(self)
Comparison:
def __hash__(self)
def __eq__(self, other)
def __ne__(self, other)
In Cythonized classes, use
__richcmp__()
instead of__eq__()
,__ne__()
.Copying, loading, saving:
def __copy__(self)
def __deepcopy__(self, memo={})
def __reduce__(self)
See, for instance,
rank_matroid.py
orcircuit_closures_matroid.pyx
for sample implementations of these.Note
Many methods (such as
M.rank()
) have a companion method whose name starts with an underscore (such asM._rank()
). The method with the underscore does not do any checks on its input. For instance, it may assume of its input that Any input that should be a subset of the groundset, is one. The
interface is compatible with Python’s
frozenset
type.  Any input that should be a list of things, supports iteration, and recursively these rules apply to its members.
Using the underscored version could improve the speed of code a little, but will generate more cryptic error messages when presented with wrong input. In some instances, no error might occur and a nonsensical answer returned.
A subclass should always override the underscored method, if available, and as a rule leave the regular method alone.

augment
(X, Y=None)¶ Return a maximal subset \(I\) of \(Y  X\) such that \(r(X + I) = r(X) + r(I)\).
INPUT:
X
– A subset ofself.groundset()
.Y
– a subset ofself.groundset()
. IfY
isNone
, the full groundset is used.
OUTPUT:
A subset of \(Y  X\).
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.augment(['a'], ['e', 'f', 'g', 'h'])) ['e', 'g', 'h'] sage: sorted(M.augment(['a'])) ['b', 'c', 'e'] sage: sorted(M.augment(['x'])) Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset. sage: sorted(M.augment(['a'], ['x'])) Traceback (most recent call last): ... ValueError: input Y is not a subset of the groundset.

bases
()¶ Return the list of bases of the matroid.
A basis is a maximal independent set.
OUTPUT:
An iterable containing all bases of the matroid.
EXAMPLES:
sage: M = matroids.Uniform(2, 4) sage: sorted([sorted(X) for X in M.bases()]) [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
ALGORITHM:
Test all subsets of the groundset of cardinality
self.full_rank()
See also

basis
()¶ Return an arbitrary basis of the matroid.
A basis is an inclusionwise maximal independent set.
Note
The output of this method can change in between calls.
OUTPUT:
Set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: B = M.basis() sage: M.is_basis(B) True sage: len(B) 3 sage: M.rank(B) 3 sage: M.full_rank() 3

binary_matroid
(randomized_tests=1, verify=True)¶ Return a binary matroid representing
self
, if such a representation exists.INPUT:
randomized_tests
– (default: 1) an integer; the number of times a certain necessary condition for being binary is tested, using randomizationverify
– (default:True
), a Boolean; ifTrue
, any output will be a binary matroid representingself
; ifFalse
, any output will representself
if and only if the matroid is binary
OUTPUT:
Either a BinaryMatroid, or
None
ALGORITHM:
First, compare the binary matroids local to two random bases. If these matroids are not isomorphic, return
None
. This test is performedrandomized_tests
times. Next, ifverify
isTrue
, test if a binary matroid local to some basis is isomorphic toself
.See also
M.local_binary_matroid()
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.binary_matroid() Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) sage: N = matroids.named_matroids.NonFano() sage: N.binary_matroid() is None True

broken_circuit_complex
(ordering=None)¶ Return the broken circuit complex of
self
.The broken circuit complex of a matroid with a total ordering \(<\) on the ground set is obtained from the
NBC sets
under subset inclusion.INPUT:
ordering
– a total ordering of the groundset given as a list
OUTPUT:
A simplicial complex of the NBC sets under inclusion.
EXAMPLES:
sage: M = Matroid(circuits=[[1,2,3], [3,4,5], [1,2,4,5]]) sage: M.broken_circuit_complex() Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 4), (1, 3, 5), (1, 2, 5), (1, 2, 4)} sage: M.broken_circuit_complex([5,4,3,2,1]) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 4, 5), (2, 3, 5), (1, 3, 5), (2, 4, 5)}

broken_circuits
(ordering=None)¶ Return the list of broken circuits of
self
.Let \(M\) be a matroid with ground set \(E\), and let \(<\) be a total ordering on \(E\). A broken circuit for \(M\) means a subset \(B\) of \(E\) such that there exists a \(u \in E\) for which \(B \cup \{ u \}\) is a circuit of \(M\) and \(u < b\) for all \(b \in B\).
INPUT:
ordering
– a total ordering of the groundset given as a list
EXAMPLES:
sage: M = Matroid(circuits=[[1,2,3], [3,4,5], [1,2,4,5]]) sage: M.broken_circuits() frozenset({frozenset({2, 3}), frozenset({4, 5}), frozenset({2, 4, 5})}) sage: M.broken_circuits([5,4,3,2,1]) frozenset({frozenset({1, 2}), frozenset({3, 4}), frozenset({1, 2, 4})})
sage: M = Matroid(circuits=[[1,2,3], [1,4,5], [2,3,4,5]]) sage: M.broken_circuits([5,4,3,2,1]) frozenset({frozenset({1, 2}), frozenset({1, 4}), frozenset({2, 3, 4})})

chordality
()¶ Return the minimal \(k\) such that the matroid
M
is \(k\)chordal.See also
EXAMPLES:
sage: M = matroids.Uniform(2,4) sage: M.chordality() 4 sage: M = matroids.named_matroids.NonFano() sage: M.chordality() 5 sage: M = matroids.named_matroids.Fano() sage: M.chordality() 4

chow_ring
(R=None)¶ Return the Chow ring of
self
overR
.Let \(M\) be a matroid and \(R\) be a commutative ring. The Chow ring of \(M\) is the quotient ring
\[A^*(M)_R := R[x_{F_1}, \ldots, x_{F_k}] / (Q_M + L_M),\]where
\(F_1, \ldots, F_k\) are the nonempty proper flats of \(M\),
\(Q_M\) is the ideal generated by all \(x_{F_i} x_{F_j}\) where \(F_i\) and \(F_j\) are incomparable elements in the lattice of flats, and
\(L_M\) is the ideal generated by all linear forms
\[\sum_{i_1 \in F} x_F  \sum_{i_2 \in F} x_F\]for all \(i_1 \neq i_2 \in E\).
INPUT:
R
– (default: \(\ZZ\)) the base ring
EXAMPLES:
sage: M = matroids.Wheel(2) sage: A = M.chow_ring() sage: A Chow ring of Wheel(2): Regular matroid of rank 2 on 4 elements with 5 bases over Integer Ring sage: A.gens() (A23, A23, A23) sage: A23 = A.gen(0) sage: A23*A23 0
We construct a more interesting example using the Fano matroid:
sage: M = matroids.named_matroids.Fano() sage: A = M.chow_ring(QQ) sage: A Chow ring of Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) over Rational Field
Next we get the nontrivial generators and do some computations:
sage: G = A.gens()[6:] sage: Ag, Aabf, Aace, Aadg, Abcd, Abeg, Acfg, Adef = G sage: Ag * Ag 2*Adef^2 sage: Ag * Abeg Adef^2 sage: matrix([[x * y for x in G] for y in G]) [2*Adef^2 0 0 Adef^2 0 Adef^2 Adef^2 0] [ 0 Adef^2 0 0 0 0 0 0] [ 0 0 Adef^2 0 0 0 0 0] [ Adef^2 0 0 Adef^2 0 0 0 0] [ 0 0 0 0 Adef^2 0 0 0] [ Adef^2 0 0 0 0 Adef^2 0 0] [ Adef^2 0 0 0 0 0 Adef^2 0] [ 0 0 0 0 0 0 0 Adef^2]
REFERENCES:

circuit
(X=None)¶ Return a circuit.
A circuit of a matroid is an inclusionwise minimal dependent subset.
INPUT:
X
– A subset ofself.groundset()
, orNone
. In the latter case, a circuit contained in the full groundset is returned.
OUTPUT:
Set of elements.
 If
X
is notNone
, the output is a circuit contained inX
if such a circuit exists. Otherwise an error is raised.  If
X
isNone
, the output is a circuit contained inself.groundset()
if such a circuit exists. Otherwise an error is raised.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.circuit(['a', 'c', 'd', 'e', 'f'])) ['c', 'd', 'e', 'f'] sage: sorted(M.circuit(['a', 'c', 'd'])) Traceback (most recent call last): ... ValueError: no circuit in independent set. sage: M.circuit(['x']) Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset. sage: sorted(M.circuit()) ['a', 'b', 'c', 'd']

circuit_closures
()¶ Return the list of closures of circuits of the matroid.
A circuit closure is a closed set containing a circuit.
OUTPUT:
A dictionary containing the circuit closures of the matroid, indexed by their ranks.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: CC = M.circuit_closures() sage: len(CC[2]) 7 sage: len(CC[3]) 1 sage: len(CC[1]) Traceback (most recent call last): ... KeyError: 1 sage: [sorted(X) for X in CC[3]] [['a', 'b', 'c', 'd', 'e', 'f', 'g']]

circuits
()¶ Return the list of circuits of the matroid.
OUTPUT:
An iterable containing all circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted([sorted(C) for C in M.circuits()]) [['a', 'b', 'c', 'g'], ['a', 'b', 'd', 'e'], ['a', 'b', 'f'], ['a', 'c', 'd', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'], ['a', 'e', 'f', 'g'], ['b', 'c', 'd'], ['b', 'c', 'e', 'f'], ['b', 'd', 'f', 'g'], ['b', 'e', 'g'], ['c', 'd', 'e', 'g'], ['c', 'f', 'g'], ['d', 'e', 'f']]

closure
(X)¶ Return the closure of a set
X
.A set is closed if adding any extra element to it will increase the rank of the set. The closure of a set is the smallest closed set containing it.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Set of elements containing
X
.EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.closure(set(['a', 'b', 'c']))) ['a', 'b', 'c', 'd'] sage: M.closure(['x']) Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

cobasis
()¶ Return an arbitrary cobasis of the matroid.
A cobasis is the complement of a basis. A cobasis is a basis of the dual matroid.
Note
Output can change between calls.
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: B = M.cobasis() sage: M.is_cobasis(B) True sage: len(B) 6 sage: M.corank(B) 6 sage: M.full_corank() 6

cocircuit
(X=None)¶ Return a cocircuit.
A cocircuit is an inclusionwise minimal subset that is dependent in the dual matroid.
INPUT:
X
– (default:None
) a subset ofself.groundset()
.
OUTPUT:
A set of elements.
 If
X
is notNone
, the output is a cocircuit contained inX
if such a cocircuit exists. Otherwise an error is raised.  If
X
isNone
, the output is a cocircuit contained inself.groundset()
if such a cocircuit exists. Otherwise an error is raised.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.cocircuit(['a', 'c', 'd', 'e', 'f'])) ['c', 'd', 'e', 'f'] sage: sorted(M.cocircuit(['a', 'c', 'd'])) Traceback (most recent call last): ... ValueError: no cocircuit in coindependent set. sage: M.cocircuit(['x']) Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset. sage: sorted(M.cocircuit()) ['e', 'f', 'g', 'h']

cocircuits
()¶ Return the list of cocircuits of the matroid.
OUTPUT:
An iterable containing all cocircuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted([sorted(C) for C in M.cocircuits()]) [['a', 'b', 'c', 'g'], ['a', 'b', 'd', 'e'], ['a', 'c', 'd', 'f'], ['a', 'e', 'f', 'g'], ['b', 'c', 'e', 'f'], ['b', 'd', 'f', 'g'], ['c', 'd', 'e', 'g']]

coclosure
(X)¶ Return the coclosure of a set
X
.A set is coclosed if it is closed in the dual matroid. The coclosure of \(X\) is the smallest coclosed set containing \(X\).
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
A set of elements containing
X
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.coclosure(set(['a', 'b', 'c']))) ['a', 'b', 'c', 'd'] sage: M.coclosure(['x']) Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

coextension
(element=None, subsets=None)¶ Return a coextension of the matroid.
A coextension of \(M\) by an element \(e\) is a matroid \(M'\) such that \(M' / e = M\). The element
element
is placed such that it lies in thecoclosure
of each set insubsets
, and otherwise as freely as possible.This is the dual method of
M.extension()
. See the documentation there for more details.INPUT:
element
– (default:None
) the label of the new element. If not specified, a new label will be generated automatically.subsets
– (default:None
) a set of subsets of the matroid. The coextension should be such that the new element is in the cospan of each of these. If not specified, the element is assumed to be in the cospan of the full groundset.
OUTPUT:
A matroid.
See also
M.dual()
,M.coextensions()
,M.modular_cut()
,M.extension()
,M.linear_subclasses()
,sage.matroids.extension
EXAMPLES:
Add an element in general position:
sage: M = matroids.Uniform(3, 6) sage: N = M.coextension(6) sage: N.is_isomorphic(matroids.Uniform(4, 7)) True
Add one inside the span of a specified hyperplane:
sage: M = matroids.Uniform(3, 6) sage: H = [frozenset([0, 1])] sage: N = M.coextension(6, H) sage: N Matroid of rank 4 on 7 elements with 34 bases sage: [sorted(C) for C in N.cocircuits() if len(C) == 3] [[0, 1, 6]]
Put an element in series with another:
sage: M = matroids.named_matroids.Fano() sage: N = M.coextension('z', ['c']) sage: N.corank('cz') 1

coextensions
(element=None, coline_length=None, subsets=None)¶ Return an iterable set of singleelement coextensions of the matroid.
A coextension of a matroid \(M\) by element \(e\) is a matroid \(M'\) such that \(M' / e = M\). By default, this method returns an iterable containing all coextensions, but it can be restricted in two ways. If
coline_length
is specified, the output is restricted to those matroids not containing a coline minor of length \(k\) greater thancoline_length
. Ifsubsets
is specified, then the output is restricted to those matroids for which the new element lies in thecoclosure
of each member ofsubsets
.This method is dual to
M.extensions()
.INPUT:
element
– (optional) the name of the newly added element in each coextension.coline_length
– (optional) a natural number. If given, restricts the output to coextensions that do not contain a \(U_{k  2, k}\) minor wherek > coline_length
.subsets
– (optional) a collection of subsets of the ground set. If given, restricts the output to extensions where the new element is contained in all cohyperplanes that contain an element ofsubsets
.
OUTPUT:
An iterable containing matroids.
Note
The coextension by a coloop will always occur. The extension by a loop will never occur.
See also
M.coextension()
,M.modular_cut()
,M.linear_subclasses()
,sage.matroids.extension
,M.extensions()
,M.dual()
EXAMPLES:
sage: M = matroids.named_matroids.P8() sage: len(list(M.coextensions())) 1705 sage: len(list(M.coextensions(coline_length=4))) 41 sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'] sage: len(list(M.coextensions(subsets=[{'a', 'b'}], coline_length=4))) 5

coflats
(r)¶ Return the collection of coflats of the matroid of specified corank.
A coflat is a coclosed set.
INPUT:
r
– a nonnegative integer.
OUTPUT:
An iterable containing all coflats of corank
r
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Q6() sage: sorted([sorted(F) for F in M.coflats(2)]) [['a', 'b'], ['a', 'c'], ['a', 'd', 'f'], ['a', 'e'], ['b', 'c'], ['b', 'd'], ['b', 'e'], ['b', 'f'], ['c', 'd'], ['c', 'e', 'f'], ['d', 'e']]

coloops
()¶ Return the set of coloops of the matroid.
A coloop is an element \(u\) of the groundset such that the oneelement set \(\{ u \}\) is a cocircuit. In other words, a coloop is a loop of the dual of the matroid.
OUTPUT:
A set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual() sage: M.coloops() frozenset() sage: (M \ ['a', 'b']).coloops() frozenset({'f'})

components
()¶ Return a list of the components of the matroid.
A component is an inclusionwise maximal connected subset of the matroid. A subset is connected if the matroid resulting from deleting the complement of that subset is
connected
.OUTPUT:
A list of subsets.
See also
EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 2, 0], ....: [0, 0, 1, 0, 0, 1]]) sage: setprint(M.components()) [{0, 1, 3, 4}, {2, 5}]

connectivity
(S, T=None)¶ Evaluate the connectivity function of the matroid.
If the input is a single subset \(S\) of the groundset \(E\), then the output is \(r(S) + r(E\S)  r(E)\).
If the input are disjoint subsets \(S, T\) of the groundset, then the output is
\[\min \{ r(X) + r(Y)  r(E) \mid X \subseteq S, Y \subseteq T, {X,Y} \text{a partition of} E \}.\]INPUT:
S
– a subset of the ground setT
– (optional) a subset of the ground set disjoint fromS
OUTPUT:
An integer.
EXAMPLES:
sage: M = matroids.named_matroids.BetsyRoss() sage: M.connectivity('ab') 2 sage: M.connectivity('ab', 'cd') 2

contract
(X)¶ Contract elements.
If \(e\) is a nonloop element, then the matroid \(M / e\) is a matroid on groundset \(E(M)  e\). A set \(X\) is independent in \(M / e\) if and only if \(X \cup e\) is independent in \(M\). If \(e\) is a loop then contracting \(e\) is the same as deleting \(e\). We say that \(M / e\) is the matroid obtained from \(M\) by contracting \(e\). Contracting an element in \(M\) is the same as deleting an element in the dual of \(M\).
When contracting a set, the elements of that set are contracted one by one. It can be shown that the resulting matroid does not depend on the order of the contractions.
Sage supports the shortcut notation
M / X
forM.contract(X)
.INPUT:
X
– Either a single element of the groundset, or a collection of elements.
OUTPUT:
The matroid obtained by contracting the element(s) in
X
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g'] sage: M.contract(['a', 'c']) Binary matroid of rank 1 on 5 elements, type (1, 0) sage: M.contract(['a']) == M / ['a'] True
One can use a single element, rather than a set:
sage: M = matroids.CompleteGraphic(4) sage: M.contract(1) == M.contract([1]) True sage: M / 1 Regular matroid of rank 2 on 5 elements with 8 bases
Note that one can iterate over strings:
sage: M = matroids.named_matroids.Fano() sage: M / 'abc' Binary matroid of rank 0 on 4 elements, type (0, 0)
The following is therefore ambiguous. Sage will contract the single element:
sage: M = Matroid(groundset=['a', 'b', 'c', 'abc'], ....: bases=[['a', 'b', 'c'], ['a', 'b', 'abc']]) sage: sorted((M / 'abc').groundset()) ['a', 'b', 'c']

corank
(X=None)¶ Return the corank of
X
, or the corank of the groundset ifX
isNone
.The corank of a set \(X\) is the rank of \(X\) in the dual matroid.
If
X
isNone
, the corank of the groundset is returned.INPUT:
X
– (default:None
) a subset of the groundset.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.corank() 4 sage: M.corank('cdeg') 3 sage: M.rank(['a', 'b', 'x']) Traceback (most recent call last): ... ValueError: input is not a subset of the groundset.

cosimplify
()¶ Return the cosimplification of the matroid.
A matroid is cosimple if it contains no cocircuits of length 1 or 2. The cosimplification of a matroid is obtained by contracting all coloops (cocircuits of length 1) and contracting all but one element from each series class (a coclosed set of rank 1, that is, each pair in it forms a cocircuit of length 2).
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual().delete('a') sage: M.cosimplify().size() 3

delete
(X)¶ Delete elements.
If \(e\) is an element, then the matroid \(M \setminus e\) is a matroid on groundset \(E(M)  e\). A set \(X\) is independent in \(M \setminus e\) if and only if \(X\) is independent in \(M\). We say that \(M \setminus e\) is the matroid obtained from \(M\) by deleting \(e\).
When deleting a set, the elements of that set are deleted one by one. It can be shown that the resulting matroid does not depend on the order of the deletions.
Sage supports the shortcut notation
M \ X
forM.delete(X)
.INPUT:
X
– Either a single element of the groundset, or a collection of elements.
OUTPUT:
The matroid obtained by deleting the element(s) in
X
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g'] sage: M.delete(['a', 'c']) Binary matroid of rank 3 on 5 elements, type (1, 6) sage: M.delete(['a']) == M \ ['a'] True
One can use a single element, rather than a set:
sage: M = matroids.CompleteGraphic(4) sage: M.delete(1) == M.delete([1]) True sage: M \ 1 Regular matroid of rank 3 on 5 elements with 8 bases
Note that one can iterate over strings:
sage: M = matroids.named_matroids.Fano() sage: M \ 'abc' Binary matroid of rank 3 on 4 elements, type (0, 5)
The following is therefore ambiguous. Sage will delete the single element:
sage: M = Matroid(groundset=['a', 'b', 'c', 'abc'], ....: bases=[['a', 'b', 'c'], ['a', 'b', 'abc']]) sage: sorted((M \ 'abc').groundset()) ['a', 'b', 'c']

dependent_r_sets
(r)¶ Return the list of dependent subsets of fixed size.
INPUT:
r
– a nonnegative integer.
OUTPUT:
An iterable containing all dependent subsets of size
r
.EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.dependent_r_sets(3) [] sage: sorted([sorted(X) for X in ....: matroids.named_matroids.Vamos().dependent_r_sets(4)]) [['a', 'b', 'c', 'd'], ['a', 'b', 'e', 'f'], ['a', 'b', 'g', 'h'], ['c', 'd', 'e', 'f'], ['e', 'f', 'g', 'h']]
ALGORITHM:
Test all subsets of the groundset of cardinality
r

dual
()¶ Return the dual of the matroid.
Let \(M\) be a matroid with ground set \(E\). If \(B\) is the set of bases of \(M\), then the set \(\{E  b : b \in B\}\) is the set of bases of another matroid, the dual of \(M\).
Note
This function wraps
self
in aDualMatroid
object. For more efficiency, subclasses that can, should override this method.OUTPUT:
The dual matroid.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: N = M.dual() sage: N.rank() 6 sage: N Dual of 'Pappus: Matroid of rank 3 on 9 elements with circuitclosures {2: {{'a', 'b', 'c'}, {'a', 'f', 'h'}, {'c', 'e', 'g'}, {'b', 'f', 'g'}, {'c', 'd', 'h'}, {'d', 'e', 'f'}, {'a', 'e', 'i'}, {'b', 'd', 'i'}, {'g', 'h', 'i'}}, 3: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'}}}'

equals
(other)¶ Test for matroid equality.
Two matroids \(M\) and \(N\) are equal if they have the same groundset and a subset \(X\) is independent in \(M\) if and only if it is independent in \(N\).
INPUT:
other
– A matroid.
OUTPUT:
Boolean.
Note
This method tests abstract matroid equality. The
==
operator takes a more restricted view:M == N
returnsTrue
only if the internal representations are of the same type,
 those representations are equivalent (for an appropriate meaning of “equivalent” in that class), and
M.equals(N)
.
EXAMPLES:
A
BinaryMatroid
andBasisMatroid
use different representations of the matroid internally, so==
yieldsFalse
, even if the matroids are equal:sage: from sage.matroids.advanced import * sage: M = matroids.named_matroids.Fano() sage: M Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) sage: M1 = BasisMatroid(M) sage: M2 = Matroid(groundset='abcdefg', reduced_matrix=[ ....: [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1]], field=GF(2)) sage: M.equals(M1) True sage: M.equals(M2) True sage: M == M1 False sage: M == M2 True
LinearMatroid
instancesM
andN
satisfyM == N
if the representations are equivalent up to row operations and column scaling:sage: M1 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 1, 2]])) sage: M2 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7), ....: [[1, 0, 1, 1], [0, 1, 1, 3]])) sage: M3 = LinearMatroid(groundset='abcd', matrix=Matrix(GF(7), ....: [[2, 6, 1, 0], [6, 1, 0, 1]])) sage: M1.equals(M2) True sage: M1.equals(M3) True sage: M1 == M2 False sage: M1 == M3 True

extension
(element=None, subsets=None)¶ Return an extension of the matroid.
An extension of \(M\) by an element \(e\) is a matroid \(M'\) such that \(M' \setminus e = M\). The element
element
is placed such that it lies in theclosure
of each set insubsets
, and otherwise as freely as possible. More precisely, the extension is defined by themodular cut
generated by the sets insubsets
.INPUT:
element
– (default:None
) the label of the new element. If not specified, a new label will be generated automatically.subsets
– (default:None
) a set of subsets of the matroid. The extension should be such that the new element is in the span of each of these. If not specified, the element is assumed to be in the span of the full groundset.
OUTPUT:
A matroid.
Note
Internally, sage uses the notion of a linear subclass for matroid extension. If
subsets
already consists of a linear subclass (i.e. the set of hyperplanes of a modular cut) then the faster methodM._extension()
can be used.See also
M.extensions()
,M.modular_cut()
,M.coextension()
,M.linear_subclasses()
,sage.matroids.extension
EXAMPLES:
First we add an element in general position:
sage: M = matroids.Uniform(3, 6) sage: N = M.extension(6) sage: N.is_isomorphic(matroids.Uniform(3, 7)) True
Next we add one inside the span of a specified hyperplane:
sage: M = matroids.Uniform(3, 6) sage: H = [frozenset([0, 1])] sage: N = M.extension(6, H) sage: N Matroid of rank 3 on 7 elements with 34 bases sage: [sorted(C) for C in N.circuits() if len(C) == 3] [[0, 1, 6]]
Putting an element in parallel with another:
sage: M = matroids.named_matroids.Fano() sage: N = M.extension('z', ['c']) sage: N.rank('cz') 1

extensions
(element=None, line_length=None, subsets=None)¶ Return an iterable set of singleelement extensions of the matroid.
An extension of a matroid \(M\) by element \(e\) is a matroid \(M'\) such that \(M' \setminus e = M\). By default, this method returns an iterable containing all extensions, but it can be restricted in two ways. If
line_length
is specified, the output is restricted to those matroids not containing a line minor of length \(k\) greater thanline_length
. Ifsubsets
is specified, then the output is restricted to those matroids for which the new element lies in theclosure
of each member ofsubsets
.INPUT:
element
– (optional) the name of the newly added element in each extension.line_length
– (optional) a natural number. If given, restricts the output to extensions that do not contain a \(U_{2, k}\) minor wherek > line_length
.subsets
– (optional) a collection of subsets of the ground set. If given, restricts the output to extensions where the new element is contained in all hyperplanes that contain an element ofsubsets
.
OUTPUT:
An iterable containing matroids.
Note
The extension by a loop will always occur. The extension by a coloop will never occur.
See also
M.extension()
,M.modular_cut()
,M.linear_subclasses()
,sage.matroids.extension
,M.coextensions()
EXAMPLES:
sage: M = matroids.named_matroids.P8() sage: len(list(M.extensions())) 1705 sage: len(list(M.extensions(line_length=4))) 41 sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'] sage: len(list(M.extensions(subsets=[{'a', 'b'}], line_length=4))) 5

f_vector
()¶ Return the \(f\)vector of the matroid.
The \(f\)vector is a vector \((f_0, ..., f_r)\), where \(f_i\) is the number of flats of rank \(i\), and \(r\) is the rank of the matroid.
OUTPUT:
List of integers.
EXAMPLES:
sage: M = matroids.named_matroids.BetsyRoss() sage: M.f_vector() [1, 11, 20, 1]

flat_cover
()¶ Return a minimumsize cover of the nonbases by nonspanning flats.
A nonbasis is a subset that has the size of a basis, yet is dependent. A flat is a closed set.
See also
EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = matroids.named_matroids.Fano() sage: setprint(M.flat_cover()) [{'a', 'b', 'f'}, {'a', 'c', 'e'}, {'a', 'd', 'g'}, {'b', 'c', 'd'}, {'b', 'e', 'g'}, {'c', 'f', 'g'}, {'d', 'e', 'f'}]

flats
(r)¶ Return the collection of flats of the matroid of specified rank.
A flat is a closed set.
INPUT:
r
– A natural number.
OUTPUT:
An iterable containing all flats of rank
r
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted([sorted(F) for F in M.flats(2)]) [['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'], ['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'], ['d', 'e', 'f']]

full_corank
()¶ Return the corank of the matroid.
The corank of the matroid equals the rank of the dual matroid. It is given by
M.size()  M.full_rank()
.OUTPUT:
Integer.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.full_corank() 4

full_rank
()¶ Return the rank of the matroid.
The rank of the matroid is the size of the largest independent subset of the groundset.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.full_rank() 4 sage: M.dual().full_rank() 4

fundamental_circuit
(B, e)¶ Return the \(B\)fundamental circuit using \(e\).
If \(B\) is a basis, and \(e\) an element not in \(B\), then the \(B\)fundamental circuit using \(e\) is the unique matroid circuit contained in \(B\cup e\).
INPUT:
B
– a basis of the matroid.e
– an element not inB
.
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.fundamental_circuit('defg', 'c')) ['c', 'd', 'e', 'f']

fundamental_cocircuit
(B, e)¶ Return the \(B\)fundamental cocircuit using \(e\).
If \(B\) is a basis, and \(e\) an element of \(B\), then the \(B\)fundamental cocircuit using \(e\) is the unique matroid cocircuit that intersects \(B\) only in \(e\).
This is equal to
M.dual().fundamental_circuit(M.groundset().difference(B), e)
.INPUT:
B
– a basis of the matroid.e
– an element ofB
.
OUTPUT:
A set of elements.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.fundamental_cocircuit('abch', 'c')) ['c', 'd', 'e', 'f']

groundset
()¶ Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
Note
Subclasses should implement this method. The return type should be frozenset or any type with compatible interface.
EXAMPLES:
sage: M = sage.matroids.matroid.Matroid() sage: M.groundset() Traceback (most recent call last): ... NotImplementedError: subclasses need to implement this.

has_line_minor
(k, hyperlines=None)¶ Test if the matroid has a \(U_{2, k}\)minor.
The matroid \(U_{2, k}\) is a matroid on \(k\) elements in which every subset of at most 2 elements is independent, and every subset of more than two elements is dependent.
The optional argument
hyperlines
restricts the search space: this method returnsFalse
if \(si(M/F)\) is isomorphic to \(U_{2, l}\) with \(l \geq k\) for some \(F\) inhyperlines
, andTrue
otherwise.INPUT:
k
– the length of the line minorhyperlines
– (default:None
) a set of flats of codimension 2. Defaults to the set of all flats of codimension 2.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.N1() sage: M.has_line_minor(4) True sage: M.has_line_minor(5) False sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c']]) False sage: M.has_line_minor(k=4, hyperlines=[['a', 'b', 'c'], ....: ['a', 'b', 'd' ]]) True

has_minor
(N, certificate=False)¶ Check if
self
has a minor isomorphic toN
, and optionally return frozensetsX
andY
so thatN
is isomorphic toself.minor(X, Y)
.INPUT:
N
– An instance of aMatroid
object,certificate
– Boolean (Defalt:False
) IfTrue
, returnsTrue, (X, Y, dic) where ``N
is isomorphic toself.minor(X, Y)
, anddic
is an isomorphism betweenN
andself.minor(X, Y)
.
OUTPUT:
boolean or tuple.
See also
Todo
This important method can (and should) be optimized considerably. See [Hli2006] p.1219 for hints to that end.
EXAMPLES:
sage: M = matroids.Whirl(3) sage: matroids.named_matroids.Fano().has_minor(M) False sage: matroids.named_matroids.NonFano().has_minor(M) True sage: matroids.named_matroids.NonFano().has_minor(M, certificate=True) (True, (frozenset(), frozenset({'g'}), {0: 'b', 1: 'c', 2: 'a', 3: 'd', 4: 'e', 5: 'f'})) sage: M = matroids.named_matroids.Fano() sage: M.has_minor(M, True) (True, (frozenset(), frozenset(), {'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd', 'e': 'e', 'f': 'f', 'g': 'g'}))

hyperplanes
()¶ Return the set of hyperplanes of the matroid.
A hyperplane is a flat of rank
self.full_rank()  1
. A flat is a closed set.OUTPUT:
An iterable containing all hyperplanes of the matroid.
See also
EXAMPLES:
sage: M = matroids.Uniform(2, 3) sage: sorted([sorted(F) for F in M.hyperplanes()]) [[0], [1], [2]]

independence_matroid_polytope
()¶ Return the independence matroid polytope of
self
.This is defined as the convex hull of the vertices
\[\sum_{i \in I} e_i\]over all independent sets \(I\) of the matroid. Here \(e_i\) are the standard basis vectors of \(\RR^n\). An arbitrary labelling of the groundset by \({0,\dots,n1}\) is chosen.
See also
EXAMPLES:
sage: M = matroids.Whirl(4) sage: M.independence_matroid_polytope() A 8dimensional polyhedron in ZZ^8 defined as the convex hull of 135 vertices sage: M = matroids.named_matroids.NonFano() sage: M.independence_matroid_polytope() A 7dimensional polyhedron in ZZ^7 defined as the convex hull of 58 vertices
REFERENCE:

independent_r_sets
(r)¶ Return the list of size
r
independent subsets of the matroid.INPUT:
r
– a nonnegative integer.
OUTPUT:
An iterable containing all independent subsets of the matroid of cardinality
r
.EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: M.independent_r_sets(4) [] sage: sorted(sorted(M.independent_r_sets(3))[0]) ['a', 'c', 'e']
ALGORITHM:
Test all subsets of the groundset of cardinality
r
See also

independent_sets
()¶ Return the list of independent subsets of the matroid.
OUTPUT:
An iterable containing all independent subsets of the matroid.
EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: I = M.independent_sets() sage: len(I) 121
See also

intersection
(other, weights=None)¶ Return a maximumweight common independent set.
A common independent set of matroids \(M\) and \(N\) with the same groundset \(E\) is a subset of \(E\) that is independent both in \(M\) and \(N\). The weight of a subset
S
issum(weights(e) for e in S)
.INPUT:
other
– a second matroid with the same groundset as this matroid.weights
– (default:None
) a dictionary which specifies a weight for each element of the common groundset. Defaults to the all1 weight function.
OUTPUT:
A subset of the groundset.
EXAMPLES:
sage: M = matroids.named_matroids.T12() sage: N = matroids.named_matroids.ExtendedTernaryGolayCode() sage: w = {'a':30, 'b':10, 'c':11, 'd':20, 'e':70, 'f':21, 'g':90, ....: 'h':12, 'i':80, 'j':13, 'k':40, 'l':21} sage: Y = M.intersection(N, w) sage: sorted(Y) ['a', 'd', 'e', 'g', 'i', 'k'] sage: sum([w[y] for y in Y]) 330 sage: M = matroids.named_matroids.Fano() sage: N = matroids.Uniform(4, 7) sage: M.intersection(N) Traceback (most recent call last): ... ValueError: matroid intersection requires equal groundsets.

intersection_unweighted
(other)¶ Return a maximumcardinality common independent set.
A common independent set of matroids \(M\) and \(N\) with the same groundset \(E\) is a subset of \(E\) that is independent both in \(M\) and \(N\).
INPUT:
other
– a second matroid with the same groundset as this matroid.
OUTPUT:
A subset of the groundset.
EXAMPLES:
sage: M = matroids.named_matroids.T12() sage: N = matroids.named_matroids.ExtendedTernaryGolayCode() sage: len(M.intersection_unweighted(N)) 6 sage: M = matroids.named_matroids.Fano() sage: N = matroids.Uniform(4, 7) sage: M.intersection_unweighted(N) Traceback (most recent call last): ... ValueError: matroid intersection requires equal groundsets.

is_3connected
(certificate=False, algorithm=None, separation=False)¶ Return
True
if the matroid is 3connected,False
otherwise. It can optionally return a separator as a witness.A \(k\)separation in a matroid is a partition \((X, Y)\) of the groundset with \(X \geq k, Y \geq k\) and \(r(X) + r(Y)  r(M) < k\). A matroid is \(k\)connected if it has no \(l\)separations for \(l < k\).
INPUT:
certificate
– (default:False
) a boolean; ifTrue
, then returnTrue, None
if the matroid is 3connected, andFalse,
\(X\) otherwise, where \(X\) is a \(<3\)separationalgorithm
– (default:None
); specify which algorithm to compute 3connectivity:None
– The most appropriate algorithm is chosen automatically."bridges"
– Bixby and Cunningham’s algorithm, based on bridges [BC1977]. Note that this cannot return a separator."intersection"
– An algorithm based on matroid intersection."shifting"
– An algorithm based on the shifting algorithm [Raj1987].
OUTPUT:
boolean, or a tuple
(boolean, frozenset)
ALGORITHM:
 Bridges based: The 3connectivity algorithm from [BC1977] which runs in \(O((r(E))^2E)\) time.
 Matroid intersection based: Evaluates the connectivity between \(O(E^2)\) pairs of disjoint sets \(S\), \(T\) with \(S = T = 2\).
 Shifting algorithm: The shifting algorithm from [Raj1987] which runs in \(O((r(E))^2E)\) time.
EXAMPLES:
sage: matroids.Uniform(2, 3).is_3connected() True sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 2, 0], ....: [0, 0, 1, 0, 0, 1]]) sage: M.is_3connected() False sage: M.is_3connected() == M.is_3connected(algorithm="bridges") True sage: M.is_3connected() == M.is_3connected(algorithm="intersection") True sage: N = Matroid(circuit_closures={2: ['abc', 'cdef'], ....: 3: ['abcdef']}, ....: groundset='abcdef') sage: N.is_3connected() False sage: matroids.named_matroids.BetsyRoss().is_3connected() True sage: M = matroids.named_matroids.R6() sage: M.is_3connected() False sage: B, X = M.is_3connected(True) sage: M.connectivity(X) 1

is_4connected
(certificate=False, algorithm=None)¶ Return
True
if the matroid is 4connected,False
otherwise. It can optionally return a separator as a witness.INPUT:
certificate
– (default:False
) a boolean; ifTrue
, then returnTrue, None
if the matroid is 4connected, andFalse,
\(X\) otherwise, where \(X\) is a \(<4\)separationalgorithm
– (default:None
); specify which algorithm to compute 4connectivity:None
– The most appropriate algorithm is chosen automatically."intersection"
– an algorithm based on matroid intersection, equivalent to callingis_kconnected(4,certificate)
."shifting"
– an algorithm based on the shifting algorithm [Raj1987].
OUTPUT:
boolean, or a tuple
(boolean, frozenset)
EXAMPLES:
sage: M = matroids.Uniform(2, 6) sage: B, X = M.is_4connected(True) sage: (B, M.connectivity(X)<=3) (False, True) sage: matroids.Uniform(4, 8).is_4connected() True sage: M = Matroid(field=GF(2), matrix=[[1,0,0,1,0,1,1,0,0,1,1,1], ....: [0,1,0,1,0,1,0,1,0,0,0,1], ....: [0,0,1,1,0,0,1,1,0,1,0,1], ....: [0,0,0,0,1,1,1,1,0,0,1,1], ....: [0,0,0,0,0,0,0,0,1,1,1,1]]) sage: M.is_4connected() == M.is_4connected(algorithm="shifting") True sage: M.is_4connected() == M.is_4connected(algorithm="intersection") True

is_basis
(X)¶ Check if a subset is a basis of the matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_basis('abc') False sage: M.is_basis('abce') True sage: M.is_basis('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_binary
(randomized_tests=1)¶ Decide if
self
is a binary matroid.INPUT:
randomized_tests
– (default: 1) an integer; the number of times a certain necessary condition for being binary is tested, using randomization
OUTPUT:
A Boolean.
ALGORITHM:
First, compare the binary matroids local to two random bases. If these matroids are not isomorphic, return
False
. This test is performedrandomized_tests
times. Next, test if a binary matroid local to some basis is isomorphic toself
.See also
EXAMPLES:
sage: N = matroids.named_matroids.Fano() sage: N.is_binary() True sage: N = matroids.named_matroids.NonFano() sage: N.is_binary() False

is_chordal
(k1=4, k2=None, certificate=False)¶ Return if a matroid is
[k1, k2]
chordal.A matroid \(M\) is \([k_1, k_2]\)chordal if every circuit of length \(\ell\) with \(k_1 \leq \ell \leq k_2\) has a
chord
. We say \(M\) is \(k\)chordal if \(k_1 = k\) and \(k_2 = \infty\). We call \(M\) chordal if it is \(4\)chordal.INPUT:
k1
– (optional) the integer \(k_1\)k2
– (optional) the integer \(k_2\); if not specified, then this method returns ifself
is \(k_1\)chordalcertificate
– (default:False
) boolean; ifTrue
returnTrue, C
, whereC
is a nonk1
k2
circuit
Output:
 boolean or tuple
See also
EXAMPLES:
sage: M = matroids.Uniform(2,4) sage: [M.is_chordal(i) for i in range(4, 8)] [True, True, True, True] sage: M = matroids.named_matroids.NonFano() sage: [M.is_chordal(i) for i in range(4, 8)] [False, True, True, True] sage: M = matroids.named_matroids.N2() sage: [M.is_chordal(i) for i in range(4, 10)] [False, False, False, False, True, True] sage: M.is_chordal(4, 5) False sage: M.is_chordal(4, 5, certificate=True) (False, frozenset({'a', 'b', 'e', 'f', 'g'}))

is_circuit
(X)¶ Test if a subset is a circuit of the matroid.
A circuit is an inclusionwise minimal dependent subset.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_circuit('abc') False sage: M.is_circuit('abcd') True sage: M.is_circuit('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_circuit_chordal
(C, certificate=False)¶ Check if the circuit
C
has a chord.A circuit \(C\) in a matroid \(M\) has a chord \(x \in E\) if there exists sets \(A, B\) such that \(C = A \sqcup B\) and \(A + x\) and \(B + x\) are circuits.
INPUT:
C
– a circuitcertificate
– (default:False
) a boolean, ifTrue
returnTrue, (x, Ax, Bx)
, wherex
is a chord andAx
andBx
are circuits whose union is the elements ofC
together withx
, ifFalse
returnFalse, None
OUTPUT:
 boolean or tuple
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.is_circuit_chordal(['b','c','d']) False sage: M.is_circuit_chordal(['b','c','d'], certificate=True) (False, None) sage: M.is_circuit_chordal(['a','b','d','e']) True sage: M.is_circuit_chordal(['a','b','d','e'], certificate=True) (True, ('c', frozenset({'b', 'c', 'd'}), frozenset({'a', 'c', 'e'})))

is_closed
(X)¶ Test if a subset is a closed set of the matroid.
A set is closed if adding any element to it will increase the rank of the set.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_closed('abc') False sage: M.is_closed('abcd') True sage: M.is_closed('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_cobasis
(X)¶ Check if a subset is a cobasis of the matroid.
A cobasis is the complement of a basis. It is a basis of the dual matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_cobasis('abc') False sage: M.is_cobasis('abce') True sage: M.is_cobasis('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_cocircuit
(X)¶ Test if a subset is a cocircuit of the matroid.
A cocircuit is an inclusionwise minimal subset that is dependent in the dual matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_cocircuit('abc') False sage: M.is_cocircuit('abcd') True sage: M.is_cocircuit('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_coclosed
(X)¶ Test if a subset is a coclosed set of the matroid.
A set is coclosed if it is a closed set of the dual matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_coclosed('abc') False sage: M.is_coclosed('abcd') True sage: M.is_coclosed('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_codependent
(X)¶ Check if a subset is codependent in the matroid.
A set is codependent if it is dependent in the dual of the matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_codependent('abc') False sage: M.is_codependent('abcd') True sage: M.is_codependent('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_coindependent
(X)¶ Check if a subset is coindependent in the matroid.
A set is coindependent if it is independent in the dual matroid.
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_coindependent('abc') True sage: M.is_coindependent('abcd') False sage: M.is_coindependent('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_connected
(certificate=False)¶ Test if the matroid is connected.
A separation in a matroid is a partition \((X, Y)\) of the groundset with \(X, Y\) nonempty and \(r(X) + r(Y) = r(X\cup Y)\). A matroid is connected if it has no separations.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 2, 0], ....: [0, 0, 1, 0, 0, 1]]) sage: M.is_connected() False sage: matroids.named_matroids.Pappus().is_connected() True

is_cosimple
()¶ Test if the matroid is cosimple.
A matroid is cosimple if it contains no cocircuits of length 1 or 2.
Dual method of
M.is_simple()
.OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual() sage: M.is_cosimple() True sage: N = M \ 'a' sage: N.is_cosimple() False

is_dependent
(X)¶ Check if a subset
X
is dependent in the matroid.INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_dependent('abc') False sage: M.is_dependent('abcd') True sage: M.is_dependent('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_independent
(X)¶ Check if a subset
X
is independent in the matroid.INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_independent('abc') True sage: M.is_independent('abcd') False sage: M.is_independent('abcx') Traceback (most recent call last): ... ValueError: input X is not a subset of the groundset.

is_isomorphic
(other, certificate=False)¶ Test matroid isomorphism.
Two matroids \(M\) and \(N\) are isomorphic if there is a bijection \(f\) from the groundset of \(M\) to the groundset of \(N\) such that a subset \(X\) is independent in \(M\) if and only if \(f(X)\) is independent in \(N\).
INPUT:
other
– A matroid, optional parameter
certificate
– Boolean.
OUTPUT:
Boolean, and, if certificate = True, a dictionary or None
EXAMPLES:
sage: M1 = matroids.Wheel(3) sage: M2 = matroids.CompleteGraphic(4) sage: M1.is_isomorphic(M2) True sage: M1.is_isomorphic(M2, certificate=True) (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4}) sage: G3 = graphs.CompleteGraph(4) sage: M1.is_isomorphic(G3) Traceback (most recent call last): ... TypeError: can only test for isomorphism between matroids. sage: M1 = matroids.named_matroids.Fano() sage: M2 = matroids.named_matroids.NonFano() sage: M1.is_isomorphic(M2) False sage: M1.is_isomorphic(M2, certificate=True) (False, None)

is_isomorphism
(other, morphism)¶ Test if a provided morphism induces a matroid isomorphism.
A morphism is a map from the groundset of
self
to the groundset ofother
.INPUT:
other
– A matroid.morphism
– A map. Can be, for instance, a dictionary, function, or permutation.
OUTPUT:
Boolean.
..SEEALSO:
:meth:`M.is_isomorphism() <sage.matroids.matroid.Matroid.is_isomorphism>`
Note
If you know the input is valid, consider using the faster method
self._is_isomorphism
.EXAMPLES:
sage: M = matroids.named_matroids.Pappus() sage: N = matroids.named_matroids.NonPappus() sage: N.is_isomorphism(M, {e:e for e in M.groundset()}) False sage: M = matroids.named_matroids.Fano() \ ['g'] sage: N = matroids.Wheel(3) sage: morphism = {'a':0, 'b':1, 'c': 2, 'd':4, 'e':5, 'f':3} sage: M.is_isomorphism(N, morphism) True
A morphism can be specified as a dictionary (above), a permutation, a function, and many other types of maps:
sage: M = matroids.named_matroids.Fano() sage: P = PermutationGroup([[('a', 'b', 'c'), ....: ('d', 'e', 'f'), ('g')]]).gen() sage: M.is_isomorphism(M, P) True sage: M = matroids.named_matroids.Pappus() sage: N = matroids.named_matroids.NonPappus() sage: def f(x): ....: return x ....: sage: N.is_isomorphism(M, f) False sage: N.is_isomorphism(N, f) True
There is extensive checking for inappropriate input:
sage: M = matroids.CompleteGraphic(4) sage: M.is_isomorphism(graphs.CompleteGraph(4), lambda x:x) Traceback (most recent call last): ... TypeError: can only test for isomorphism between matroids. sage: M = matroids.CompleteGraphic(4) sage: sorted(M.groundset()) [0, 1, 2, 3, 4, 5] sage: M.is_isomorphism(M, {0: 1, 1: 2, 2: 3}) Traceback (most recent call last): ... ValueError: domain of morphism does not contain groundset of this matroid. sage: M = matroids.CompleteGraphic(4) sage: sorted(M.groundset()) [0, 1, 2, 3, 4, 5] sage: M.is_isomorphism(M, {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}) Traceback (most recent call last): ... ValueError: range of morphism does not contain groundset of other matroid. sage: M = matroids.CompleteGraphic(3) sage: N = Matroid(bases=['ab', 'ac', 'bc']) sage: f = [0, 1, 2] sage: g = {'a': 0, 'b': 1, 'c': 2} sage: N.is_isomorphism(M, f) Traceback (most recent call last): ... ValueError: the morphism argument does not seem to be an isomorphism. sage: N.is_isomorphism(M, g) True

is_k_closed
(k)¶ Return if
self
is ak
closed matroid.We say a matroid is \(k\)closed if all \(k\)closed subsets are closed in
M
.EXAMPLES:
sage: PR = RootSystem(['A',4]).root_lattice().positive_roots() sage: m = matrix([x.to_vector() for x in PR]).transpose() sage: M = Matroid(m) sage: M.is_k_closed(3) True sage: M.is_k_closed(4) True sage: PR = RootSystem(['D',4]).root_lattice().positive_roots() sage: m = matrix([x.to_vector() for x in PR]).transpose() sage: M = Matroid(m) sage: M.is_k_closed(3) False sage: M.is_k_closed(4) True

is_kconnected
(k, certificate=False)¶ Return
True
if the matroid is \(k\)connected,False
otherwise. It can optionally return a separator as a witness.INPUT:
k
– a integer greater or equal to 1.certificate
– (default:False
) a boolean; ifTrue
, then returnTrue, None
if the matroid is kconnected, andFalse, X
otherwise, whereX
is a \(<k\)separation
OUTPUT:
boolean, or a tuple
(boolean, frozenset)
ALGORITHM:
Apply linking algorithm to find small separator.
EXAMPLES:
sage: matroids.Uniform(2, 3).is_kconnected(3) True sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0], ....: [0, 1, 0, 1, 2, 0], ....: [0, 0, 1, 0, 0, 1]]) sage: M.is_kconnected(3) False sage: N = Matroid(circuit_closures={2: ['abc', 'cdef'], ....: 3: ['abcdef']}, ....: groundset='abcdef') sage: N.is_kconnected(3) False sage: matroids.named_matroids.BetsyRoss().is_kconnected(3) True sage: matroids.AG(5,2).is_kconnected(4) True sage: M = matroids.named_matroids.R6() sage: M.is_kconnected(3) False sage: B, X = M.is_kconnected(3,True) sage: M.connectivity(X)<3 True

is_max_weight_coindependent_generic
(X=None, weights=None)¶ Test if only one cobasis of the subset
X
has maximal weight.The weight of a subset
S
issum(weights(e) for e in S)
.INPUT:
X
– (default: the ground set ofself
) a subset ofself.groundset()
(given as a list, tuple or set).weights
– a dictionary or function mapping the elements ofX
to nonnegative weights.
OUTPUT:
Boolean.
ALGORITHM:
The greedy algorithm. If a weight function is given, then sort the elements of
X
by increasing weight, and otherwise use the ordering in whichX
lists its elements. Then greedily select elements if they are coindependent of all that was selected before. If an element is not coindependent of the previously selected elements, then we check if it is coindependent with the previously selected elements with higher weight.EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = matroids.named_matroids.Fano() sage: M.is_max_weight_coindependent_generic() False sage: def wt(x): ....: return x ....: sage: M = matroids.Uniform(2, 8) sage: M.is_max_weight_coindependent_generic(weights=wt) True sage: M.is_max_weight_coindependent_generic(weights={x: x for x in M.groundset()}) True sage: M.is_max_weight_coindependent_generic() False sage: M=matroids.Uniform(2,5) sage: wt={0: 1, 1: 1, 2: 1, 3: 2, 4: 2} sage: M.is_max_weight_independent_generic(weights=wt) True sage: M.dual().is_max_weight_coindependent_generic(weights=wt) True
Here is an example from [GriRei2014] (Example 7.56 in v3):
sage: A = Matrix(QQ, [[ 1, 1, 0, 0], ....: [1, 0, 1, 1], ....: [ 0, 1, 1, 1]]) sage: M = Matroid(A) sage: M.is_max_weight_coindependent_generic() False sage: M.is_max_weight_coindependent_generic(weights={0: 1, 1: 3, 2: 3, 3: 2}) True sage: M.is_max_weight_coindependent_generic(weights={0: 1, 1: 3, 2: 2, 3: 2}) False sage: M.is_max_weight_coindependent_generic(weights={0: 2, 1: 3, 2: 1, 3: 1}) False

is_max_weight_independent_generic
(X=None, weights=None)¶ Test if only one basis of the subset
X
has maximal weight.The weight of a subset
S
issum(weights(e) for e in S)
.INPUT:
X
– (default: the ground set ofself
) a subset ofself.groundset()
(given as a list, tuple or set).weights
– a dictionary or function mapping the elements ofX
to nonnegative weights.
OUTPUT:
Boolean.
ALGORITHM:
The greedy algorithm. If a weight function is given, then sort the elements of
X
by decreasing weight, and otherwise use the ordering in whichX
lists its elements. Then greedily select elements if they are independent of all that was selected before. If an element is not independent of the previously selected elements, then we check if it is independent with the previously selected elements with higher weight.EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = matroids.named_matroids.Fano() sage: M.is_max_weight_independent_generic() False sage: def wt(x): ....: return x ....: sage: M = matroids.Uniform(2, 8) sage: M.is_max_weight_independent_generic(weights=wt) True sage: M.is_max_weight_independent_generic(weights={x: x for x in M.groundset()}) True sage: M.is_max_weight_independent_generic() False
Here is an example from [GriRei2014] (Example 7.56 in v3):
sage: A = Matrix(QQ, [[ 1, 1, 0, 0], ....: [1, 0, 1, 1], ....: [ 0, 1, 1, 1]]) sage: M = Matroid(A) sage: M.is_max_weight_independent_generic() False sage: M.is_max_weight_independent_generic(weights={0: 1, 1: 3, 2: 3, 3: 2}) True sage: M.is_max_weight_independent_generic(weights={0: 1, 1: 3, 2: 2, 3: 2}) False sage: M.is_max_weight_independent_generic(weights={0: 2, 1: 3, 2: 1, 3: 1}) True

is_simple
()¶ Test if the matroid is simple.
A matroid is simple if it contains no circuits of length 1 or 2.
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.is_simple() True sage: N = M / 'a' sage: N.is_simple() False

is_subset_k_closed
(X, k)¶ Test if
X
is ak
closed set of the matroid.A set \(S\) is \(k\)closed if the closure of any \(k\) element subsets is contained in \(S\).
INPUT:
X
– a subset ofself.groundset()
k
– a positive integer
OUTPUT:
Boolean.
See also
EXAMPLES:
sage: m = matrix([[1,2,5,2], [0,2,1,0]]) sage: M = Matroid(m) sage: M.is_subset_k_closed({1,3}, 2) False sage: M.is_subset_k_closed({0,1}, 1) False sage: M.is_subset_k_closed({1,2}, 1) True sage: Q = RootSystem(['D',4]).root_lattice() sage: m = matrix([x.to_vector() for x in Q.positive_roots()]) sage: m = m.transpose(); m [1 0 0 0 1 0 0 0 1 1 1 1] [0 1 0 0 1 1 1 1 1 1 1 2] [0 0 1 0 0 0 1 1 1 0 1 1] [0 0 0 1 0 1 0 1 0 1 1 1] sage: M = Matroid(m) sage: M.is_subset_k_closed({0,2,3,11}, 3) True sage: M.is_subset_k_closed({0,2,3,11}, 4) False sage: M.is_subset_k_closed({0,1}, 4) False sage: M.is_subset_k_closed({0,1,4}, 4) True

is_ternary
(randomized_tests=1)¶ Decide if
self
is a ternary matroid.INPUT:
randomized_tests
– (default: 1) an integer; the number of times a certain necessary condition for being ternary is tested, using randomization
OUTPUT:
A Boolean.
ALGORITHM:
First, compare the ternary matroids local to two random bases. If these matroids are not isomorphic, return
False
. This test is performedrandomized_tests
times. Next, test if a ternary matroid local to some basis is isomorphic toself
.See also
EXAMPLES:
sage: N = matroids.named_matroids.Fano() sage: N.is_ternary() False sage: N = matroids.named_matroids.NonFano() sage: N.is_ternary() True

is_valid
()¶ Test if the data obey the matroid axioms.
The default implementation checks the (disproportionately slow) rank axioms. If \(r\) is the rank function of a matroid, we check, for all pairs \(X, Y\) of subsets,
 \(0 \leq r(X) \leq X\)
 If \(X \subseteq Y\) then \(r(X) \leq r(Y)\)
 \(r(X\cup Y) + r(X\cap Y) \leq r(X) + r(Y)\)
Certain subclasses may check other axioms instead.
OUTPUT:
Boolean.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.is_valid() True
The following is the ‘Escher matroid’ by Brylawski and Kelly. See Example 1.5.5 in [Oxl2011]
sage: M = Matroid(circuit_closures={2: [[1, 2, 3], [1, 4, 5]], ....: 3: [[1, 2, 3, 4, 5], [1, 2, 3, 6, 7], [1, 4, 5, 6, 7]]}) sage: M.is_valid() False

isomorphism
(other)¶ Return a matroid isomorphism.
Two matroids \(M\) and \(N\) are isomorphic if there is a bijection \(f\) from the groundset of \(M\) to the groundset of \(N\) such that a subset \(X\) is independent in \(M\) if and only if \(f(X)\) is independent in \(N\). This method returns one isomorphism \(f\) from self to other, if such an isomorphism exists.
INPUT:
other
– A matroid.
OUTPUT:
A dictionary, or
None
.EXAMPLES:
sage: M1 = matroids.Wheel(3) sage: M2 = matroids.CompleteGraphic(4) sage: morphism=M1.isomorphism(M2) sage: M1.is_isomorphism(M2, morphism) True sage: G3 = graphs.CompleteGraph(4) sage: M1.isomorphism(G3) Traceback (most recent call last): ... TypeError: can only give isomorphism between matroids. sage: M1 = matroids.named_matroids.Fano() sage: M2 = matroids.named_matroids.NonFano() sage: M1.isomorphism(M2) is not None False

k_closure
(X, k)¶ Return the
k
closure ofX
.A subset \(S\) of the groundset is \(k\)closed if the closure of any subset \(T\) of \(S\) satisfying \(T \leq k\) is contained in \(S\). The \(k\)closure of a set \(X\) is the smallest \(k\)closed set containing \(X\).
INPUT:
X
– a subset ofself.groundset()
k
– a positive integer
EXAMPLES:
sage: m = matrix([[1,2,5,2], [0,2,1,0]]) sage: M = Matroid(m) sage: sorted(M.k_closure({1,3}, 2)) [0, 1, 2, 3] sage: sorted(M.k_closure({0,1}, 1)) [0, 1, 3] sage: sorted(M.k_closure({1,2}, 1)) [1, 2] sage: Q = RootSystem(['D',4]).root_lattice() sage: m = matrix([x.to_vector() for x in Q.positive_roots()]) sage: m = m.transpose(); m [1 0 0 0 1 0 0 0 1 1 1 1] [0 1 0 0 1 1 1 1 1 1 1 2] [0 0 1 0 0 0 1 1 1 0 1 1] [0 0 0 1 0 1 0 1 0 1 1 1] sage: M = Matroid(m) sage: sorted(M.k_closure({0,2,3,11}, 3)) [0, 2, 3, 11] sage: sorted(M.k_closure({0,2,3,11}, 4)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] sage: sorted(M.k_closure({0,1}, 4)) [0, 1, 4]

lattice_of_flats
()¶ Return the lattice of flats of the matroid.
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.lattice_of_flats() Finite lattice containing 16 elements

linear_subclasses
(line_length=None, subsets=None)¶ Return an iterable set of linear subclasses of the matroid.
A linear subclass is a set of hyperplanes (i.e. closed sets of rank \(r(M)  1\)) with the following property:
 If \(H_1\) and \(H_2\) are members, and \(r(H_1 \cap H_2) = r(M)  2\), then any hyperplane \(H_3\) containing \(H_1 \cap H_2\) is a member too.
A linear subclass is the set of hyperplanes of a
modular cut
and uniquely determines the modular cut. Hence the collection of linear subclasses is in 1to1 correspondence with the collection of singleelement extensions of a matroid. See [Oxl2011], section 7.2.INPUT:
line_length
– (default:None
) a natural number. If given, restricts the output to modular cuts that generate an extension by \(e\) that does not contain a minor \(N\) isomorphic to \(U_{2, k}\), wherek > line_length
, and such that \(e \in E(N)\).subsets
– (default:None
) a collection of subsets of the ground set. If given, restricts the output to linear subclasses such that each hyperplane contains an element ofsubsets
.
OUTPUT:
An iterable collection of linear subclasses.
Note
The
line_length
argument only checks for lines using the new element of the corresponding extension. It is still possible that a long line exists by contracting the new element!See also
M.flats()
,M.modular_cut()
,M.extension()
,sage.matroids.extension
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: len(list(M.linear_subclasses())) 16 sage: len(list(M.linear_subclasses(line_length=3))) 8 sage: len(list(M.linear_subclasses(subsets=[{'a', 'b'}]))) 5
The following matroid has an extension by element \(e\) such that contracting \(e\) creates a 6point line, but no 6point line minor uses \(e\). Consequently, this method returns the modular cut, but the
M.extensions()
method doesn’t return the corresponding extension:sage: M = Matroid(circuit_closures={2: ['abc', 'def'], ....: 3: ['abcdef']}) sage: len(list(M.extensions('g', line_length=5))) 43 sage: len(list(M.linear_subclasses(line_length=5))) 44

link
(S, T)¶ Given disjoint subsets \(S\) and \(T\), return a connector \(I\) and a separation \(X\), which are optimal dual solutions in Tutte’s Linking Theorem:
\[\begin{split}\max \{ r_N(S) + r_N(T)  r(N) \mid N = M/I\setminus J, E(N) = S\cup T\}=\\ \min \{ r_M(X) + r_M(Y)  r_M(E) \mid X \subseteq S, Y \subseteq T, E = X\cup Y, X\cap Y = \emptyset \}.\end{split}\]Here \(M\) denotes this matroid.
INPUT:
S
– a subset of the ground setT
– a subset of the ground set disjoint fromS
OUTPUT:
A tuple
(I, X)
containing a frozensetI
and a frozensetX
.ALGORITHM:
Compute a maximumcardinality common independent set \(I\) of of \(M / S \setminus T\) and \(M \setminus S / T\).
EXAMPLES:
sage: M = matroids.named_matroids.BetsyRoss() sage: S = set('ab') sage: T = set('cd') sage: I, X = M.link(S, T) sage: M.connectivity(X) 2 sage: J = M.groundset()(STI) sage: N = M/I\J sage: N.connectivity(S) 2

loops
()¶ Return the set of loops of the matroid.
A loop is an element \(u\) of the groundset such that the oneelement set \(\{ u \}\) is dependent.
OUTPUT:
A set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.loops() frozenset() sage: (M / ['a', 'b']).loops() frozenset({'f'})

matroid_polytope
()¶ Return the matroid polytope of
self
.This is defined as the convex hull of the vertices
\[e_B = \sum_{i \in B} e_i\]over all bases \(B\) of the matroid. Here \(e_i\) are the standard basis vectors of \(\RR^n\). An arbitrary labelling of the groundset by \({0,\dots,n1}\) is chosen.
See also
EXAMPLES:
sage: M = matroids.Whirl(4) sage: P = M.matroid_polytope(); P A 7dimensional polyhedron in ZZ^8 defined as the convex hull of 46 vertices sage: M = matroids.named_matroids.NonFano() sage: M.matroid_polytope() A 6dimensional polyhedron in ZZ^7 defined as the convex hull of 29 vertices
REFERENCE:

max_coindependent
(X)¶ Compute a maximal coindependent subset of
X
.A set is coindependent if it is independent in the dual matroid. A set is coindependent if and only if the complement is spanning (i.e. contains a basis of the matroid).
INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
A subset of
X
.See also
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.max_coindependent(['a', 'c', 'd', 'e', 'f'])) ['a', 'c', 'd', 'e'] sage: M.max_coindependent(['x']) Traceback (most recent call last): ... ValueError: input is not a subset of the groundset.

max_independent
(X)¶ Compute a maximal independent subset of
X
.INPUT:
X
– A subset ofself.groundset()
.
OUTPUT:
Subset of
X
.EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: sorted(M.max_independent(['a', 'c', 'd', 'e', 'f'])) ['a', 'd', 'e', 'f'] sage: M.max_independent(['x']) Traceback (most recent call last): ... ValueError: input is not a subset of the groundset.

max_weight_coindependent
(X=None, weights=None)¶ Return a maximumweight coindependent set contained in
X
.The weight of a subset
S
issum(weights(e) for e in S)
.INPUT:
X
– (default:None
) an iterable with a subset ofself.groundset()
.weights
– a dictionary or function mapping the elements ofX
to nonnegative weights.
OUTPUT:
A subset of
X
.ALGORITHM:
The greedy algorithm. If a weight function is given, then sort the elements of
X
by decreasing weight, and otherwise use the ordering in whichX
lists its elements. Then greedily select elements if they are coindependent of all that was selected before.EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = matroids.named_matroids.Fano() sage: X = M.max_weight_coindependent() sage: M.is_cobasis(X) True sage: wt = {'a': 1, 'b': 2, 'c': 2, 'd': 1/2, 'e': 1, 'f': 2, ....: 'g': 2} sage: setprint(M.max_weight_coindependent(weights=wt)) {'b', 'c', 'f', 'g'} sage: def wt(x): ....: return x ....: sage: M = matroids.Uniform(2, 8) sage: setprint(M.max_weight_coindependent(weights=wt)) {2, 3, 4, 5, 6, 7} sage: setprint(M.max_weight_coindependent()) {0, 1, 2, 3, 4, 5} sage: M.max_weight_coindependent(X=[], weights={}) frozenset()

max_weight_independent
(X=None, weights=None)¶ Return a maximumweight independent set contained in a subset.
The weight of a subset
S
issum(weights(e) for e in S)
.INPUT:
X
– (default:None
) an iterable with a subset ofself.groundset()
.weights
– a dictionary or function mapping the elements ofX
to nonnegative weights.
OUTPUT:
A subset of
X
.ALGORITHM:
The greedy algorithm. If a weight function is given, then sort the elements of
X
by decreasing weight, and otherwise use the ordering in whichX
lists its elements. Then greedily select elements if they are independent of all that was selected before.EXAMPLES:
sage: from sage.matroids.advanced import setprint sage: M = matroids.named_matroids.Fano() sage: X = M.max_weight_independent() sage: M.is_basis(X) True sage: wt = {'a': 1, 'b': 2, 'c': 2, 'd': 1/2, 'e': 1, ....: 'f': 2, 'g': 2} sage: setprint(M.max_weight_independent(weights=wt)) {'b', 'f', 'g'} sage: def wt(x): ....: return x ....: sage: M = matroids.Uniform(2, 8) sage: setprint(M.max_weight_independent(weights=wt)) {6, 7} sage: setprint(M.max_weight_independent()) {0, 1} sage: M.max_weight_coindependent(X=[], weights={}) frozenset()

minor
(contractions=None, deletions=None)¶ Return the minor of
self
obtained by contracting, respectively deleting, the element(s) ofcontractions
anddeletions
.A minor of a matroid is a matroid obtained by repeatedly removing elements in one of two ways: either
contract
ordelete
them. It can be shown that the final matroid does not depend on the order in which elements are removed.INPUT:
contractions
– (default:None
) an element or set of elements to be contracted.deletions
– (default:None
) an element or set of elements to be deleted.
OUTPUT:
A matroid.
Note
The output is either of the same type as
self
, or an instance ofMinorMatroid
.See also
EXAMPLES:
sage: M = matroids.Wheel(4) sage: N = M.minor(contractions=[7], deletions=[0]) sage: N.is_isomorphic(matroids.Wheel(3)) True
The sets of contractions and deletions need not be independent, respectively coindependent:
sage: M = matroids.named_matroids.Fano() sage: M.rank('abf') 2 sage: M.minor(contractions='abf') Binary matroid of rank 1 on 4 elements, type (1, 0)
However, they need to be subsets of the groundset, and disjoint:
sage: M = matroids.named_matroids.Vamos() sage: M.minor('abc', 'defg') M / {'a', 'b', 'c'} \ {'d', 'e', 'f', 'g'}, where M is Vamos: Matroid of rank 4 on 8 elements with circuitclosures {3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'}, {'e', 'f', 'g', 'h'}, {'a', 'b', 'g', 'h'}, {'c', 'd', 'e', 'f'}}, 4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}} sage: M.minor('defgh', 'abc') M / {'d', 'e', 'f', 'g'} \ {'a', 'b', 'c', 'h'}, where M is Vamos: Matroid of rank 4 on 8 elements with circuitclosures {3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'}, {'e', 'f', 'g', 'h'}, {'a', 'b', 'g', 'h'}, {'c', 'd', 'e', 'f'}}, 4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}} sage: M.minor([1, 2, 3], 'efg') Traceback (most recent call last): ... ValueError: input contractions is not a subset of the groundset. sage: M.minor('efg', [1, 2, 3]) Traceback (most recent call last): ... ValueError: input deletions is not a subset of the groundset. sage: M.minor('ade', 'efg') Traceback (most recent call last): ... ValueError: contraction and deletion sets are not disjoint.
Warning
There can be ambiguity if elements of the groundset are themselves iterable, and their elements are in the groundset. The main example of this is when an element is a string. See the documentation of the methods
contract()
anddelete()
for an example of this.

modular_cut
(subsets)¶ Compute the modular cut generated by
subsets
.A modular cut is a collection \(C\) of flats such that
 If \(F \in C\) and \(F'\) is a flat containing \(F\), then \(F' \in C\)
 If \(F_1, F_2 \in C\) form a modular pair of flats, then \(F_1\cap F_2 \in C\).
A flat is a closed set, a modular pair is a pair \(F_1, F_2\) of flats with \(r(F_1) + r(F_2) = r(F_1\cup F_2) + r(F_1\cap F_2)\), where \(r\) is the rank function of the matroid.
The modular cut generated by
subsets
is the smallest modular cut \(C\) for which closure`(S) in C` for all \(S\) insubsets
.There is a onetoone correspondence between the modular cuts of a matroid and the singleelement extensions of the matroid. See [Oxl2011] Section 7.2 for more information.
Note
Sage uses linear subclasses, rather than modular cuts, internally for matroid extension. A linear subclass is the set of hyperplanes (flats of rank \(r(M)  1\)) of a modular cut. It determines the modular cut uniquely (see [Oxl2011] Section 7.2).
INPUT:
subsets
– A collection of subsets of the groundset.
OUTPUT:
A collection of subsets.
See also
EXAMPLES:
Any extension of the Vamos matroid where the new point is placed on the lines through elements \(\{a, b\}\) and through \(\{c, d\}\) is an extension by a loop:
sage: M = matroids.named_matroids.Vamos() sage: frozenset([]) in M.modular_cut(['ab', 'cd']) True
In any extension of the matroid \(S_8 \setminus h\), a point on the lines through \(\{c, g\}\) and \(\{a, e\}\) also is on the line through \(\{b, f\}\):
sage: M = matroids.named_matroids.S8() sage: N = M \ 'h' sage: frozenset('bf') in N.modular_cut(['cg', 'ae']) True
The modular cut of the full groundset is equal to just the groundset:
sage: M = matroids.named_matroids.Fano() sage: M.modular_cut([M.groundset()]).difference( ....: [frozenset(M.groundset())]) set()

no_broken_circuits_sets
(ordering=None)¶ Return the no broken circuits (NBC) sets of
self
.An NBC set is a subset \(A\) of the ground set under some total ordering \(<\) such that \(A\) contains no broken circuit.
INPUT:
ordering
– a total ordering of the groundset given as a list
EXAMPLES:
sage: M = Matroid(circuits=[[1,2,3], [3,4,5], [1,2,4,5]]) sage: SimplicialComplex(M.no_broken_circuits_sets()) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 4), (1, 3, 5), (1, 2, 5), (1, 2, 4)} sage: SimplicialComplex(M.no_broken_circuits_sets([5,4,3,2,1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 4, 5), (2, 3, 5), (1, 3, 5), (2, 4, 5)}
sage: M = Matroid(circuits=[[1,2,3], [1,4,5], [2,3,4,5]]) sage: SimplicialComplex(M.no_broken_circuits_sets([5,4,3,2,1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(2, 3, 5), (1, 3, 5), (2, 4, 5), (3, 4, 5)}

nonbases
()¶ Return the list of nonbases of the matroid.
A nonbasis is a set with cardinality
self.full_rank()
that is not a basis.OUTPUT:
An iterable containing the nonbases of the matroid.
See also
EXAMPLES:
sage: M = matroids.Uniform(2, 4) sage: list(M.nonbases()) [] sage: [sorted(X) for X in matroids.named_matroids.P6().nonbases()] [['a', 'b', 'c']]
ALGORITHM:
Test all subsets of the groundset of cardinality
self.full_rank()

noncospanning_cocircuits
()¶ Return the list of noncospanning cocircuits of the matroid.
A noncospanning cocircuit is a cocircuit whose corank is strictly smaller than the corank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().dual() sage: sorted([sorted(C) for C in M.noncospanning_cocircuits()]) [['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'], ['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'], ['d', 'e', 'f']]

nonspanning_circuit_closures
()¶ Return the list of closures of nonspanning circuits of the matroid.
A nonspanning circuit closure is a closed set containing a nonspanning circuit.
OUTPUT:
A dictionary containing the nonspanning circuit closures of the matroid, indexed by their ranks.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: CC = M.nonspanning_circuit_closures() sage: len(CC[2]) 7 sage: len(CC[3]) Traceback (most recent call last): ... KeyError: 3

nonspanning_circuits
()¶ Return the list of nonspanning circuits of the matroid.
A nonspanning circuit is a circuit whose rank is strictly smaller than the rank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: sorted([sorted(C) for C in M.nonspanning_circuits()]) [['a', 'b', 'f'], ['a', 'c', 'e'], ['a', 'd', 'g'], ['b', 'c', 'd'], ['b', 'e', 'g'], ['c', 'f', 'g'], ['d', 'e', 'f']]

orlik_solomon_algebra
(R, ordering=None)¶ Return the OrlikSolomon algebra of
self
.INPUT:
R
– the base ringordering
– (optional) an ordering of the ground set
See also
EXAMPLES:
sage: M = matroids.Uniform(3, 4) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS OrlikSolomon algebra of U(3, 4): Matroid of rank 3 on 4 elements with circuitclosures {3: {{0, 1, 2, 3}}}

partition
()¶ Returns a minimum number of disjoint independent sets that covers the groundset.
OUTPUT:
A list of disjoint independent sets that covers the goundset.
EXAMPLES:
sage: M = matroids.named_matroids.Block_9_4() sage: P = M.partition() sage: all(map(M.is_independent,P)) True sage: set.union(*P)==M.groundset() True sage: sum(map(len,P))==len(M.groundset()) True sage: Matroid(matrix([])).partition() []
ALGORITHM:
Reduce partition to a matroid intersection between a matroid sum and a partition matroid. It’s known the direct method doesn’t gain much advantage over matroid intersection. [Cun1986]

plot
(B=None, lineorders=None, pos_method=None, pos_dict=None, save_pos=False)¶ Return geometric representation as a sage graphics object.
INPUT:
B
– (optional) a list containing a basis. If internal point placement is used, these elements will be placed as vertices of a triangle.lineorders
– (optional) A list of lists where each of the inner lists specify ground set elements in a certain order which will be used to draw the corresponding line in geometric representation (if it exists).pos_method
– An integer specifying positioning method.0
: default positioning1
: use pos_dict if it is notNone
2
: Force directed (Not yet implemented).
pos_dict
: A dictionary mapping ground set elements to their (x,y) positions.save_pos
: A boolean indicating that point placements (either internal or user provided) and line orders (if provided) will be cached in the matroid (M._cached_info
) and can be used for reproducing the geometric representation during the same session
OUTPUT:
A sage graphics object of type <class ‘sage.plot.graphics.Graphics’> that corresponds to the geometric representation of the matroid
EXAMPLES:
sage: M=matroids.named_matroids.Fano() sage: G=M.plot() sage: type(G) <class 'sage.plot.graphics.Graphics'> sage: G.show()

rank
(X=None)¶ Return the rank of
X
.The rank of a subset \(X\) is the size of the largest independent set contained in \(X\).
If
X
isNone
, the rank of the groundset is returned.INPUT:
X
– (default:None
) a subset of the groundset
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.rank() 3 sage: M.rank(['a', 'b', 'f']) 2 sage: M.rank(['a', 'b', 'x']) Traceback (most recent call last): ... ValueError: input is not a subset of the groundset.

show
(B=None, lineorders=None, pos_method=None, pos_dict=None, save_pos=False, lims=None)¶ Show the geometric representation of the matroid.
INPUT:
B
– (optional) a list containing elements of the groundset not in any particular order. If internal point placement is used, these elements will be placed as vertices of a triangle.lineorders
– (optional) A list of lists where each of the inner lists specify ground set elements in a certain order which will be used to draw the corresponding line in geometric representation (if it exists).pos_method
– An integer specifying positioning method0
: default positioning1
: use pos_dict if it is notNone
2
: Force directed (Not yet implemented).
pos_dict
– A dictionary mapping ground set elements to their (x,y) positions.save_pos
– A boolean indicating that point placements (either internal or user provided) and line orders (if provided) will be cached in the matroid (M._cached_info
) and can be used for reproducing the geometric representation during the same sessionlims
– A list of 4 elements[xmin,xmax,ymin,ymax]
EXAMPLES:
sage: M=matroids.named_matroids.TernaryDowling3() sage: M.show(B=['a','b','c']) sage: M.show(B=['a','b','c'],lineorders=[['f','e','i']]) sage: pos = {'a':(0,0), 'b': (0,1), 'c':(1,0), 'd':(1,1), 'e':(1,1), 'f':(1,1), 'g':(1,1),'h':(2,0), 'i':(0,2)} sage: M.show(pos_method=1, pos_dict=pos,lims=[3,3,3,3])

simplify
()¶ Return the simplification of the matroid.
A matroid is simple if it contains no circuits of length 1 or 2. The simplification of a matroid is obtained by deleting all loops (circuits of length 1) and deleting all but one element from each parallel class (a closed set of rank 1, that is, each pair in it forms a circuit of length 2).
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano().contract('a') sage: M.size()  M.simplify().size() 3

size
()¶ Return the size of the groundset.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Vamos() sage: M.size() 8

ternary_matroid
(randomized_tests=1, verify=True)¶ Return a ternary matroid representing
self
, if such a representation exists.INPUT:
randomized_tests
– (default: 1) an integer; the number of times a certain necessary condition for being ternary is tested, using randomizationverify
– (default:True
), a Boolean; ifTrue
, any output will be a ternary matroid representingself
; ifFalse
, any output will representself
if and only if the matroid is ternary
OUTPUT:
Either a
TernaryMatroid
, orNone
ALGORITHM:
First, compare the ternary matroids local to two random bases. If these matroids are not isomorphic, return
None
. This test is performedrandomized_tests
times. Next, ifverify
isTrue
, test if a ternary matroid local to some basis is isomorphic toself
.See also
M._local_ternary_matroid()
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.ternary_matroid() is None True sage: N = matroids.named_matroids.NonFano() sage: N.ternary_matroid() NonFano: Ternary matroid of rank 3 on 7 elements, type 0

truncation
()¶ Return a rank1 truncation of the matroid.
Let \(M\) be a matroid of rank \(r\). The truncation of \(M\) is the matroid obtained by declaring all subsets of size \(r\) dependent. It can be obtained by adding an element freely to the span of the matroid and then contracting that element.
OUTPUT:
A matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: N = M.truncation() sage: N.is_isomorphic(matroids.Uniform(2, 7)) True

tutte_polynomial
(x=None, y=None)¶ Return the Tutte polynomial of the matroid.
The Tutte polynomial of a matroid is the polynomial
\[T(x, y) = \sum_{A \subseteq E} (x  1)^{r(E)  r(A)} (y  1)^{r^*(E)  r^*(E\setminus A)},\]where \(E\) is the groundset of the matroid, \(r\) is the rank function, and \(r^*\) is the corank function. Tutte defined his polynomial differently:
\[T(x, y)=\sum_{B} x^i(B) y^e(B),\]where the sum ranges over all bases of the matroid, \(i(B)\) is the number of internally active elements of \(B\), and \(e(B)\) is the number of externally active elements of \(B\).
INPUT:
x
– (optional) a variable or numerical argument.y
– (optional) a variable or numerical argument.
OUTPUT:
The Tuttepolynomial \(T(x, y)\), where \(x\) and \(y\) are substituted with any values provided as input.
Todo
Make implementation more efficient, e.g. generalizing the approach from trac ticket #1314 from graphs to matroids.
EXAMPLES:
sage: M = matroids.named_matroids.Fano() sage: M.tutte_polynomial() y^4 + x^3 + 3*y^3 + 4*x^2 + 7*x*y + 6*y^2 + 3*x + 3*y sage: M.tutte_polynomial(1, 1) == M.bases_count() True
ALGORITHM:
Enumerate the bases and compute the internal and external activities for each \(B\).