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:

is_distinguished()

relabel()

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 *

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 of groundset.
nonbases (optional) – a set of subsets of groundset.
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.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

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.named_matroids.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.named_matroids.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.named_matroids.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.