Minors of matroids#
Theory#
Let \(M\) be a matroid with groundset \(E\). There are two standard ways to
remove an element from \(E\) so that the result is again a matroid, deletion
and contraction. Deletion is simply omitting the elements from a set \(D\)
from \(E\) and keeping all remaining independent sets. This is denoted M \ D
(this also works in Sage). Contraction is the dual operation:
M / C == (M.dual() \ C).dual()
.
EXAMPLES:
sage: M = matroids.catalog.Fano()
sage: M.delete(['a', 'c' ]) == M.delete(['a', 'c'])
True
sage: M / 'a' == M.contract('a')
True
sage: (M / 'c').delete('ab') == M.minor(contractions='c', deletions='ab')
True
>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> M.delete(['a', 'c' ]) == M.delete(['a', 'c'])
True
>>> M / 'a' == M.contract('a')
True
>>> (M / 'c').delete('ab') == M.minor(contractions='c', deletions='ab')
True
If a contraction set is not independent (or a deletion set not coindependent), this is taken care of:
sage: M = matroids.catalog.Fano()
sage: M.rank('abf')
2
sage: M / 'abf' == (M / 'ab').delete('f')
True
sage: M / 'abf' == (M / 'af').delete('b')
True
>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> M.rank('abf')
2
>>> M / 'abf' == (M / 'ab').delete('f')
True
>>> M / 'abf' == (M / 'af').delete('b')
True
See also
Implementation#
The class MinorMatroid
wraps around a matroid instance to represent a minor. Only useful for classes
that don’t have an explicit construction of minors
(such as RankMatroid
and
CircuitClosuresMatroid
).
It is also used as default implementation of the minor methods
M.minor(C, D)
,
M.delete(D)
,
M.contract(C)
.
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
Methods#
- class sage.matroids.minor_matroid.MinorMatroid(matroid, contractions=None, deletions=None)[source]#
Bases:
Matroid
Minor of a matroid.
For some matroid representations, it can be computationally expensive to derive an explicit representation of a minor. This class wraps around any matroid to provide an abstract minor. It also serves as default implementation.
Return a minor.
INPUT:
matroid
– matroidcontractions
– An object with Python’sfrozenset
interface containing a subset ofself.groundset()
.deletions
– An object with Python’sfrozenset
interface containing a subset ofself.groundset()
.
OUTPUT:
A
MinorMatroid
instance representingmatroid / contractions \ deletions
.Warning
This class does NOT do any checks. Besides the assumptions above, we assume the following:
contractions
is independentdeletions
is coindependentcontractions
anddeletions
are disjoint.
EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = matroids.catalog.Vamos() sage: N = MinorMatroid(matroid=M, contractions=set(['a']), ....: deletions=set()) sage: N._minor(contractions=set(), deletions=set(['b', 'c'])) M / {'a'} \ {'b', 'c'}, where M is 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() >>> N = MinorMatroid(matroid=M, contractions=set(['a']), ... deletions=set()) >>> N._minor(contractions=set(), deletions=set(['b', 'c'])) M / {'a'} \ {'b', 'c'}, where M is 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'}}}
- groundset()[source]#
Return the groundset of the matroid.
EXAMPLES:
sage: M = matroids.catalog.Pappus().contract(['c']) sage: sorted(M.groundset()) ['a', 'b', 'd', 'e', 'f', 'g', 'h', 'i']
>>> from sage.all import * >>> M = matroids.catalog.Pappus().contract(['c']) >>> sorted(M.groundset()) ['a', 'b', 'd', 'e', 'f', 'g', 'h', 'i']