Circuit closures matroids#

Matroids are characterized by a list of all tuples \((C, k)\), where \(C\) is the closure of a circuit, and \(k\) the rank of \(C\). The CircuitClosuresMatroid class implements matroids using this information as data.

Construction#

A CircuitClosuresMatroid can be created from another matroid or from a list of circuit-closures. For a full description of allowed inputs, see below. It is recommended to use the Matroid() function for a more flexible construction of a CircuitClosuresMatroid. For direct access to the CircuitClosuresMatroid constructor, run:

sage: from sage.matroids.advanced import *

Methods#

class sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid#

Bases: Matroid

A general matroid \(M\) is characterized by its rank \(r(M)\) and the set of pairs

\((k, \{\) closure \((C) : C ` circuit of ` M, r(C)=k\})\) for \(k=0, .., r(M)-1\)

As each independent set of size \(k\) is in at most one closure(\(C\)) of rank \(k\), and each closure(\(C\)) of rank \(k\) contains at least \(k + 1\) independent sets of size \(k\), there are at most \(\binom{n}{k}/(k + 1)\) such closures-of-circuits of rank \(k\). Each closure(\(C\)) takes \(O(n)\) bits to store, giving an upper bound of \(O(2^n)\) on the space complexity of the entire matroid.

A subset \(X\) of the ground set is independent if and only if

\(| X \cap ` closure `(C) | \leq k\) for all circuits \(C\) of \(M\) with \(r(C)=k\).

So determining whether a set is independent takes time proportional to the space complexity of the matroid.

INPUT:

M – (default: None) an arbitrary matroid.
groundset – (default: None) the groundset of a matroid.
circuit_closures – (default: None) the collection of circuit closures of a matroid, presented as a dictionary whose keys are ranks, and whose values are sets of circuit closures of the specified rank.

OUTPUT:

If the input is a matroid M, return a CircuitClosuresMatroid instance representing M.
Otherwise, return a CircuitClosuresMatroid instance based on groundset and circuit_closures.

Note

For a more flexible means of input, use the Matroid() function.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(matroids.named_matroids.Fano())
sage: M
Matroid of rank 3 on 7 elements with circuit-closures
{2: {{'a', 'b', 'f'}, {'a', 'c', 'e'}, {'a', 'd', 'g'},
     {'b', 'c', 'd'}, {'b', 'e', 'g'}, {'c', 'f', 'g'},
     {'d', 'e', 'f'}}, 3: {{'a', 'b', 'c', 'd', 'e', 'f', 'g'}}}
sage: M = CircuitClosuresMatroid(groundset='abcdefgh',
....:            circuit_closures={3: ['edfg', 'acdg', 'bcfg', 'cefh',
....:                 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'],
....:                              4: ['abcdefgh']})
sage: M.equals(matroids.named_matroids.P8())
True

circuit_closures()#

Return the list of closures of circuits of the matroid.

A circuit closure is a closed set containing a circuit.

OUTPUT:

A dictionary containing the circuit closures of the matroid, indexed by their ranks.