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:
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
The set of bases is compactly stored in a bitset which takes
bits of space, where
is the cardinality of the
groundset and
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:
TESTS:
sage: F = matroids.named_matroids.Fano()
sage: M = Matroid(bases=F.bases())
sage: TestSuite(M).run()
Bases: sage.matroids.basis_exchange_matroid.BasisExchangeMatroid
Create general matroid, stored as a set of bases.
INPUT:
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.named_matroids.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
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.named_matroids.Fano().bases())
sage: M
Matroid of rank 3 on 7 elements with 28 bases
sage: len(M.bases())
28
Return the number of bases of the matroid.
OUTPUT:
Integer.
EXAMPLES:
sage: M = Matroid(bases=matroids.named_matroids.Fano().bases())
sage: M
Matroid of rank 3 on 7 elements with 28 bases
sage: M.bases_count()
28
Return the dual of the matroid.
Let be a matroid with ground set
. If
is the set of bases
of
, then the set
is the set of bases of
another matroid, the dual of
.
OUTPUT:
The dual matroid.
EXAMPLES:
sage: M = Matroid(bases=matroids.named_matroids.Pappus().bases())
sage: M.dual()
Matroid of rank 6 on 9 elements with 75 bases
ALGORITHM:
A BasisMatroid on elements and of rank
is stored as a
bitvector of length
. The
-th bit in this vector
indicates that the
-th
-set in the lexicographic enumeration of
-subsets of the groundset is a basis. Reversing this bitvector
yields a bitvector that indicates whether the complement of an
-set is a basis, i.e. gives the bitvector of the bases of the
dual.
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:
OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.matroids.advanced import *
sage: M = BasisMatroid(matroids.named_matroids.N1())
sage: sorted([e for e in M.groundset() if M.is_distinguished(e)])
['c', 'g', 'h', 'j']
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.named_matroids.Fano().bases())
sage: M
Matroid of rank 3 on 7 elements with 28 bases
sage: len(M.nonbases())
7
Return an isomorphic matroid with relabeled groundset.
The output is obtained by relabeling each element e by l[e], where l is a given injective map. If e not in l then the identity map is assumed.
INPUT:
OUTPUT:
A matroid.
Todo
Write abstract RelabeledMatroid class, and add relabel() method to the main Matroid class, together with _relabel() method that can be replaced by subclasses. Use the code from is_isomorphism() in relabel() to deal with a variety of input methods for the relabeling.
EXAMPLES:
sage: from sage.matroids.advanced import *
sage: M = BasisMatroid(matroids.named_matroids.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']
Return a rank-1 truncation of the matroid.
Let be a matroid of rank
. The truncation of
is the
matroid obtained by declaring all subsets of size
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.named_matroids.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]