Iterators for linear subclasses#

The classes below are iterators returned by the functions M.linear_subclasses() and M.extensions(). See the documentation of these methods for more detail. For direct access to these classes, run:

sage: from sage.matroids.advanced import *

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

See also sage.matroids.advanced.

AUTHORS:

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

Methods#

class sage.matroids.extension.CutNode[source]#

Bases: object

An internal class used for creating linear subclasses of a matroids in a depth-first manner.

A linear subclass is a set of hyperplanes \(mc\) with the property that certain sets of hyperplanes must either be fully contained in \(mc\) or intersect \(mc\) in at most 1 element. The way we generate them is by a depth-first search. This class represents a node in the search tree.

It contains the set of hyperplanes selected so far, as well as a collection of hyperplanes whose insertion has been explored elsewhere in the search tree.

The class has methods for selecting a hyperplane to insert, for inserting hyperplanes and closing the set to become a linear subclass again, and for adding a hyperplane to the set of forbidden hyperplanes, and similarly closing that set.

class sage.matroids.extension.LinearSubclasses[source]#

Bases: object

An iterable set of linear subclasses of a matroid.

Enumerate linear subclasses of a given matroid. A linear subclass is a collection of hyperplanes (flats of rank \(r - 1\) where \(r\) is the rank of the matroid) with the property that no modular triple of hyperplanes has exactly two members in the linear subclass. A triple of hyperplanes in a matroid of rank \(r\) is modular if its intersection has rank \(r - 2\).

INPUT:

  • M – a matroid.

  • line_length – (default: None) an integer.

  • subsets – (default: None) a set of subsets of the groundset of M.

  • splice – (default: None) a matroid \(N\) such that for some \(e \in E(N)\) and some \(f \in E(M)\), we have \(N\setminus e= M\setminus f\).

OUTPUT:

An enumerator for the linear subclasses of M.

If line_length is not None, the enumeration is restricted to linear subclasses mc so containing at least one of each set of line_length hyperplanes which have a common intersection of rank \(r - 2\).

If subsets is not None, the enumeration is restricted to linear subclasses mc containing all hyperplanes which fully contain some set from subsets.

If splice is not None, then the enumeration is restricted to linear subclasses \(mc\) such that if \(M'\) is the extension of \(M\) by \(e\) that arises from \(mc\), then \(M'\setminus f = N\).

EXAMPLES:

sage: from sage.matroids.extension import LinearSubclasses
sage: M = matroids.Uniform(3, 6)
sage: len([mc for mc in LinearSubclasses(M)])
83
sage: len([mc for mc in LinearSubclasses(M, line_length=5)])
22
sage: for mc in LinearSubclasses(M, subsets=[[0, 1], [2, 3], [4, 5]]):
....:     print(len(mc))
3
15

>>> from sage.all import *
>>> from sage.matroids.extension import LinearSubclasses
>>> M = matroids.Uniform(Integer(3), Integer(6))
>>> len([mc for mc in LinearSubclasses(M)])
83
>>> len([mc for mc in LinearSubclasses(M, line_length=Integer(5))])
22
>>> for mc in LinearSubclasses(M, subsets=[[Integer(0), Integer(1)], [Integer(2), Integer(3)], [Integer(4), Integer(5)]]):
...     print(len(mc))
3
15

Note that this class is intended for runtime, internal use, so no loads/dumps mechanism was implemented.

class sage.matroids.extension.LinearSubclassesIter[source]#

Bases: object

An iterator for a set of linear subclass.

class sage.matroids.extension.MatroidExtensions[source]#

Bases: LinearSubclasses

An iterable set of single-element extensions of a given matroid.

INPUT:

  • M – a matroid

  • e – an element

  • line_length (default: None) – an integer

  • subsets (default: None) – a set of subsets of the groundset of M

  • splice – a matroid \(N\) such that for some \(f \in E(M)\), we have \(N\setminus e= M\setminus f\).

OUTPUT:

An enumerator for the extensions of M to a matroid N so that \(N\setminus e = M\). If line_length is not None, the enumeration is restricted to extensions \(N\) without \(U(2, k)\)-minors, where k > line_length.

If subsets is not None, the enumeration is restricted to extensions \(N\) of \(M\) by element \(e\) so that all hyperplanes of \(M\) which fully contain some set from subsets, will also span \(e\).

If splice is not None, then the enumeration is restricted to extensions \(M'\) such that \(M'\setminus f = N\), where \(E(M)\setminus E(N)=\{f\}\).

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = matroids.Uniform(3, 6)
sage: len([N for N in MatroidExtensions(M, 'x')])
83
sage: len([N for N in MatroidExtensions(M, 'x', line_length=5)])
22
sage: for N in MatroidExtensions(M, 'x', subsets=[[0, 1], [2, 3],
....:                                             [4, 5]]): print(N)
Matroid of rank 3 on 7 elements with 32 bases
Matroid of rank 3 on 7 elements with 20 bases
sage: M = BasisMatroid(matroids.catalog.BetsyRoss()); M
Matroid of rank 3 on 11 elements with 140 bases
sage: e = 'k'; f = 'h'; Me = M.delete(e); Mf=M.delete(f)
sage: for N in MatroidExtensions(Mf, f, splice=Me): print(N)
Matroid of rank 3 on 11 elements with 141 bases
Matroid of rank 3 on 11 elements with 140 bases
sage: for N in MatroidExtensions(Me, e, splice=Mf): print(N)
Matroid of rank 3 on 11 elements with 141 bases
Matroid of rank 3 on 11 elements with 140 bases

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = matroids.Uniform(Integer(3), Integer(6))
>>> len([N for N in MatroidExtensions(M, 'x')])
83
>>> len([N for N in MatroidExtensions(M, 'x', line_length=Integer(5))])
22
>>> for N in MatroidExtensions(M, 'x', subsets=[[Integer(0), Integer(1)], [Integer(2), Integer(3)],
...                                             [Integer(4), Integer(5)]]): print(N)
Matroid of rank 3 on 7 elements with 32 bases
Matroid of rank 3 on 7 elements with 20 bases
>>> M = BasisMatroid(matroids.catalog.BetsyRoss()); M
Matroid of rank 3 on 11 elements with 140 bases
>>> e = 'k'; f = 'h'; Me = M.delete(e); Mf=M.delete(f)
>>> for N in MatroidExtensions(Mf, f, splice=Me): print(N)
Matroid of rank 3 on 11 elements with 141 bases
Matroid of rank 3 on 11 elements with 140 bases
>>> for N in MatroidExtensions(Me, e, splice=Mf): print(N)
Matroid of rank 3 on 11 elements with 141 bases
Matroid of rank 3 on 11 elements with 140 bases

Note that this class is intended for runtime, internal use, so no loads/dumps mechanism was implemented.