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 *

>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M1 = BasisMatroid(groundset='abcd', bases=['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
>>> M2 = Matroid(['ab', 'ac', 'ad', 'bc', 'bd', 'cd'])
>>> 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

class sage.matroids.basis_matroid.BasisMatroid[source]#

Bases: BasisExchangeMatroid

Create general matroid, stored as a set of bases.

INPUT:

  • M – matroid (optional)

  • groundset – any iterable set (optional)

  • bases – set of subsets of the groundset (optional)

  • nonbases – set of subsets of the groundset (optional)

  • rank – natural number (optional)

EXAMPLES:

The empty matroid:

sage: from sage.matroids.advanced import *
sage: M = BasisMatroid()
sage: M.groundset()
frozenset()
sage: M.full_rank()
0

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = BasisMatroid()
>>> M.groundset()
frozenset()
>>> 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

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> F = matroids.catalog.Fano()
>>> M = BasisMatroid(F)
>>> F.groundset() == M.groundset()
True
>>> 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

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M1 = BasisMatroid(groundset='abc', bases=['ab', 'ac'] )
>>> M2 = BasisMatroid(groundset='abc', nonbases=['bc'])
>>> 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

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M1 = BasisMatroid(matroids.Uniform(Integer(2), Integer(5)))
>>> M2 = BasisMatroid(groundset=range(Integer(5)), rank=Integer(2))
>>> 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

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M1 = BasisMatroid(groundset='abcd', bases=['ab', 'cd'])
>>> M1.full_rank()
2
>>> M1.is_valid()
False
bases()[source]#

Return the bases of the matroid.

A basis is a maximal independent set.

OUTPUT: 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

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.Fano().bases())
>>> M
Matroid of rank 3 on 7 elements with 28 bases
>>> len(M.bases())
28
bases_count()[source]#

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

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.Fano().bases())
>>> M
Matroid of rank 3 on 7 elements with 28 bases
>>> M.bases_count()
28
dual()[source]#

Return the dual of the matroid.

Let \(M\) be a matroid with groundset \(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\).

EXAMPLES:

sage: M = Matroid(bases=matroids.catalog.Pappus().bases())
sage: M.dual()
Matroid of rank 6 on 9 elements with 75 bases

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.Pappus().bases())
>>> 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)[source]#

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 – element of the groundset

OUTPUT: boolean

See also

M.extensions(), M.linear_subclasses(), sage.matroids.extension

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']

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = BasisMatroid(matroids.catalog.N1())
>>> sorted([e for e in M.groundset() if M.is_distinguished(e)])
['c', 'g', 'h', 'j']
nonbases()[source]#

Return the nonbases of the matroid.

A nonbasis is a set with cardinality self.full_rank() that is not a basis.

OUTPUT: iterable containing the nonbases of the matroid

See also

Matroid.basis()

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

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.Fano().bases())
>>> M
Matroid of rank 3 on 7 elements with 28 bases
>>> len(M.nonbases())
7
relabel(mapping)[source]#

Return an isomorphic matroid with relabeled groundset.

The output is obtained by relabeling each element \(e\) by mapping[e], where mapping is a given injective map. If mapping[e] is not defined, then the identity map is assumed.

INPUT:

  • mapping – a Python object such that mapping[e] is the new label of \(e\)

OUTPUT: matroid

EXAMPLES:

sage: from sage.matroids.advanced import BasisMatroid
sage: M = BasisMatroid(matroids.catalog.Fano())
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
sage: N = M.relabel({'a': 0, 'g': 'x'})
sage: from sage.matroids.utilities import cmp_elements_key
sage: sorted(N.groundset(), key=cmp_elements_key)
[0, 'b', 'c', 'd', 'e', 'f', 'x']
sage: N.is_isomorphic(M)
True

>>> from sage.all import *
>>> from sage.matroids.advanced import BasisMatroid
>>> M = BasisMatroid(matroids.catalog.Fano())
>>> sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> N = M.relabel({'a': Integer(0), 'g': 'x'})
>>> from sage.matroids.utilities import cmp_elements_key
>>> sorted(N.groundset(), key=cmp_elements_key)
[0, 'b', 'c', 'd', 'e', 'f', 'x']
>>> N.is_isomorphic(M)
True
truncation()[source]#

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: matroid

See also

M.extension(), M.contract()

EXAMPLES:

sage: M = Matroid(bases=matroids.catalog.N2().bases())
sage: M.truncation()
Matroid of rank 5 on 12 elements with 702 bases
sage: M.whitney_numbers2()
[1, 12, 66, 190, 258, 99, 1]
sage: M.truncation().whitney_numbers2()
[1, 12, 66, 190, 258, 1]

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.N2().bases())
>>> M.truncation()
Matroid of rank 5 on 12 elements with 702 bases
>>> M.whitney_numbers2()
[1, 12, 66, 190, 258, 99, 1]
>>> M.truncation().whitney_numbers2()
[1, 12, 66, 190, 258, 1]