Basis matroids#
In a matroid, a basis is an inclusionwise maximal independent set. The common cardinality of all bases is the rank of the matroid. Matroids are uniquely determined by their set of bases.
This module defines the class
BasisMatroid
, which
internally represents a matroid as a set of bases. It is a subclass of
BasisExchangeMatroid
, and as
such it inherits all method from that class and from the class
Matroid
. Additionally, it provides the
following methods:
Construction#
A BasisMatroid
can be created from another matroid, from a list of bases,
or from a list of nonbases. For a full description of allowed inputs, see
below
. It is recommended
to use the Matroid()
function for
easy construction of a BasisMatroid
. For direct access to the
BasisMatroid
constructor, run:
sage: from sage.matroids.advanced import *
See also sage.matroids.advanced
.
EXAMPLES:
sage: from sage.matroids.advanced import *
sage: M1 = BasisMatroid(groundset='abcd', bases=['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
sage: M2 = Matroid(['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
sage: M1 == M2
True
Implementation#
The set of bases is compactly stored in a bitset which takes
\(O(binomial(N, R))\) bits of space, where \(N\) is the cardinality of the
groundset and \(R\) is the rank. BasisMatroid
inherits the matroid oracle
from its parent class BasisExchangeMatroid
, by providing the elementary
functions for exploring the base exchange graph. In addition, BasisMatroid
has methods for constructing minors, duals, single-element extensions, for
testing matroid isomorphism and minor inclusion.
AUTHORS:
Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
Methods#
- class sage.matroids.basis_matroid.BasisMatroid#
Bases:
BasisExchangeMatroid
Create general matroid, stored as a set of bases.
INPUT:
M
(optional) – a matroid.groundset
(optional) – any iterable set.bases
(optional) – a set of subsets ofgroundset
.nonbases
(optional) – a set of subsets ofgroundset
.rank
(optional) – a natural number
EXAMPLES:
The empty matroid:
sage: from sage.matroids.advanced import * sage: M = BasisMatroid() sage: M.groundset() frozenset() sage: M.full_rank() 0
Create a BasisMatroid instance out of any other matroid:
sage: from sage.matroids.advanced import * sage: F = matroids.catalog.Fano() sage: M = BasisMatroid(F) sage: F.groundset() == M.groundset() True sage: len(set(F.bases()).difference(M.bases())) 0
It is possible to provide either bases or nonbases:
sage: from sage.matroids.advanced import * sage: M1 = BasisMatroid(groundset='abc', bases=['ab', 'ac'] ) sage: M2 = BasisMatroid(groundset='abc', nonbases=['bc']) sage: M1 == M2 True
Providing only groundset and rank creates a uniform matroid:
sage: from sage.matroids.advanced import * sage: M1 = BasisMatroid(matroids.Uniform(2, 5)) sage: M2 = BasisMatroid(groundset=range(5), rank=2) sage: M1 == M2 True
We do not check if the provided input forms an actual matroid:
sage: from sage.matroids.advanced import * sage: M1 = BasisMatroid(groundset='abcd', bases=['ab', 'cd']) sage: M1.full_rank() 2 sage: M1.is_valid() False
- 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 = Matroid(bases=matroids.catalog.Fano().bases()) sage: M Matroid of rank 3 on 7 elements with 28 bases sage: len(M.bases()) 28
- bases_count()#
Return the number of bases of the matroid.
OUTPUT:
Integer.
EXAMPLES:
sage: M = Matroid(bases=matroids.catalog.Fano().bases()) sage: M Matroid of rank 3 on 7 elements with 28 bases sage: M.bases_count() 28
- 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\).
OUTPUT:
The dual matroid.
EXAMPLES:
sage: M = Matroid(bases=matroids.catalog.Pappus().bases()) sage: M.dual() Matroid of rank 6 on 9 elements with 75 bases
ALGORITHM:
A BasisMatroid on \(n\) elements and of rank \(r\) is stored as a bitvector of length \(\binom{n}{r}\). The \(i\)-th bit in this vector indicates that the \(i\)-th \(r\)-set in the lexicographic enumeration of \(r\)-subsets of the groundset is a basis. Reversing this bitvector yields a bitvector that indicates whether the complement of an \((n - r)\)-set is a basis, i.e. gives the bitvector of the bases of the dual.
- is_distinguished(e)#
Return whether
e
is a ‘distinguished’ element of the groundset.The set of distinguished elements is an isomorphism invariant. Each matroid has at least one distinguished element. The typical application of this method is the execution of an orderly algorithm for generating all matroids up to isomorphism in a minor-closed class, by successively enumerating the single-element extensions and coextensions of the matroids generated so far.
INPUT:
e
– an element of the ground set
OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.catalog.N1()) sage: sorted([e for e in M.groundset() if M.is_distinguished(e)]) ['c', 'g', 'h', 'j']
- 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 = Matroid(bases=matroids.catalog.Fano().bases()) sage: M Matroid of rank 3 on 7 elements with 28 bases sage: len(M.nonbases()) 7
- relabel(l)#
Return an isomorphic matroid with relabeled groundset.
The output is obtained by relabeling each element
e
byl[e]
, wherel
is a given injective map. Ife not in l
then the identity map is assumed.INPUT:
l
– a python object such that \(l[e]\) is the new label of \(e\).
OUTPUT:
A matroid.
Todo
Write abstract
RelabeledMatroid
class, and addrelabel()
method to the mainMatroid
class, together with_relabel()
method that can be replaced by subclasses. Use the code fromis_isomorphism()
inrelabel()
to deal with a variety of input methods for the relabeling.EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.catalog.Fano()) sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g'] sage: N = M.relabel({'g':'x'}) sage: sorted(N.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'x']
- truncation()#
Return a rank-1 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 = Matroid(bases=matroids.catalog.N2().bases()) sage: M.truncation() Matroid of rank 5 on 12 elements with 702 bases sage: M.f_vector() [1, 12, 66, 190, 258, 99, 1] sage: M.truncation().f_vector() [1, 12, 66, 190, 258, 1]