Minors of matroids

Theory

Let \(M\) be a matroid with ground set \(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.named_matroids.Fano()
sage: M \ ['a', 'c' ] == M.delete(['a', 'c'])
True
sage: M / 'a' == M.contract('a')
True
sage: M / 'c' \ '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.named_matroids.Fano()
sage: M.rank('abf')
2
sage: M / 'abf' == M / 'ab' \ 'f'
True
sage: M / 'abf' == M / 'af' \ 'b'
True

See also

M.delete(), M.contract(), M.minor(),

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 *

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)

Bases: sage.matroids.matroid.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 – a matroid.
  • contractions – An object with Python’s frozenset interface containing a subset of self.groundset().
  • deletions – An object with Python’s frozenset interface containing a subset of self.groundset().

OUTPUT:

A MinorMatroid instance representing matroid / contractions \ deletions.

Warning

This class does NOT do any checks. Besides the assumptions above, we assume the following:

  • contractions is independent
  • deletions is coindependent
  • contractions and deletions are disjoint.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = matroids.named_matroids.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'}}}
groundset()

Return the groundset of the matroid.

EXAMPLES:

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