Dual matroids

Theory

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 = matroids.catalog.Fano()
sage: N = M.dual()
sage: M.is_basis('abc')
True
sage: N.is_basis('defg')
True
sage: M.dual().dual() == M
True

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> N = M.dual()
>>> M.is_basis('abc')
True
>>> N.is_basis('defg')
True
>>> M.dual().dual() == M
True

Implementation

The class DualMatroid wraps around a matroid instance to represent its dual. Only useful for classes that don’t have an explicit construction of the dual (such as RankMatroid and CircuitClosuresMatroid). It is also used as the default implementation of the method M.dual(). For direct access to the DualMatroid constructor, run:

sage: from sage.matroids.advanced import *

>>> from sage.all import *
>>> from sage.matroids.advanced import *

See also sage.matroids.advanced.

AUTHORS:

  • Rudi Pendavingh, Michael Welsh, Stefan van Zwam (2013-04-01): initial version

class sage.matroids.dual_matroid.DualMatroid(matroid)[source]

Bases: Matroid

Dual of a matroid.

For some matroid representations it can be computationally expensive to derive an explicit representation of the dual. This class wraps around any matroid to provide an abstract dual. It also serves as the default implementation of the dual.

INPUT:

  • matroid – matroid

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = matroids.catalog.Vamos()
sage: Md = DualMatroid(M)  # indirect doctest
sage: Md.rank('abd') == M.corank('abd')
True
sage: Md
Dual of 'Vamos: Matroid of rank 4 on 8 elements with circuit-closures
{3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'}, {'a', 'b', 'g', 'h'},
     {'c', 'd', 'e', 'f'}, {'e', 'f', 'g', 'h'}},
 4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}}'

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = matroids.catalog.Vamos()
>>> Md = DualMatroid(M)  # indirect doctest
>>> Md.rank('abd') == M.corank('abd')
True
>>> Md
Dual of 'Vamos: Matroid of rank 4 on 8 elements with circuit-closures
{3: {{'a', 'b', 'c', 'd'}, {'a', 'b', 'e', 'f'}, {'a', 'b', 'g', 'h'},
     {'c', 'd', 'e', 'f'}, {'e', 'f', 'g', 'h'}},
 4: {{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}}}'
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\). Note that the dual of the dual of \(M\) equals \(M\), so if this is the DualMatroid instance wrapping \(M\) then the returned matroid is \(M\).

OUTPUT: the dual matroid

EXAMPLES:

sage: M = matroids.catalog.Pappus().dual()
sage: N = M.dual()
sage: N.rank()
3
sage: N
Pappus: Matroid of rank 3 on 9 elements with 9 nonspanning circuits

>>> from sage.all import *
>>> M = matroids.catalog.Pappus().dual()
>>> N = M.dual()
>>> N.rank()
3
>>> N
Pappus: Matroid of rank 3 on 9 elements with 9 nonspanning circuits
groundset()[source]

Return the groundset of the matroid.

The groundset is the set of elements that comprise the matroid.

OUTPUT: set

EXAMPLES:

sage: M = matroids.catalog.Pappus().dual()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

>>> from sage.all import *
>>> M = matroids.catalog.Pappus().dual()
>>> sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
is_valid(certificate=False)[source]

Test if self obeys the matroid axioms.

For a DualMatroid, we check its dual.

INPUT:

  • certificate – boolean (default: False)

OUTPUT: boolean, or (boolean, dictionary)

EXAMPLES:

sage: M = matroids.catalog.K5dual()
sage: type(M)
<class 'sage.matroids.dual_matroid.DualMatroid'>
sage: M.is_valid()
True
sage: M = Matroid([[0, 1], [2, 3]])
sage: M.dual().is_valid()
False

>>> from sage.all import *
>>> M = matroids.catalog.K5dual()
>>> type(M)
<class 'sage.matroids.dual_matroid.DualMatroid'>
>>> M.is_valid()
True
>>> M = Matroid([[Integer(0), Integer(1)], [Integer(2), Integer(3)]])
>>> M.dual().is_valid()
False
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: M = matroids.catalog.K5dual(range(10))
sage: type(M)
<class 'sage.matroids.dual_matroid.DualMatroid'>
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: N = M.dual().relabel({0:10})
sage: sorted(N.groundset())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: N.is_isomorphic(matroids.catalog.K5())
True

>>> from sage.all import *
>>> M = matroids.catalog.K5dual(range(Integer(10)))
>>> type(M)
<class 'sage.matroids.dual_matroid.DualMatroid'>
>>> sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> N = M.dual().relabel({Integer(0):Integer(10)})
>>> sorted(N.groundset())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> N.is_isomorphic(matroids.catalog.K5())
True