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 *

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

See also sage.matroids.advanced.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M1 = CircuitClosuresMatroid(groundset='abcdef',
....:                 circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: M2 = Matroid(circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: M3 = Matroid(circuit_closures=[(2, 'abc'),
....:                                (3, 'abcdef'), (2, 'ade')])
sage: M1 == M2
True
sage: M1 == M3
True

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M1 = CircuitClosuresMatroid(groundset='abcdef',
...                 circuit_closures={Integer(2): ['abc', 'ade'], Integer(3): ['abcdef']})
>>> M2 = Matroid(circuit_closures={Integer(2): ['abc', 'ade'], Integer(3): ['abcdef']})
>>> M3 = Matroid(circuit_closures=[(Integer(2), 'abc'),
...                                (Integer(3), 'abcdef'), (Integer(2), 'ade')])
>>> M1 == M2
True
>>> M1 == M3
True

Note that the class does not implement custom minor and dual operations:

sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(groundset='abcdef',
....:                 circuit_closures={2: ['abc', 'ade'], 3: ['abcdef']})
sage: isinstance(M.contract('a'), MinorMatroid)
True
sage: isinstance(M.dual(), DualMatroid)
True

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = CircuitClosuresMatroid(groundset='abcdef',
...                 circuit_closures={Integer(2): ['abc', 'ade'], Integer(3): ['abcdef']})
>>> isinstance(M.contract('a'), MinorMatroid)
True
>>> isinstance(M.dual(), DualMatroid)
True

AUTHORS:

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

class sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid[source]#

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 groundset 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 – matroid (default: None)

  • groundset – groundset of a matroid (default: None)

  • circuit_closures – dict (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.catalog.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.catalog.P8())
True

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = CircuitClosuresMatroid(matroids.catalog.Fano())
>>> 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'}}}
>>> M = CircuitClosuresMatroid(groundset='abcdefgh',
...            circuit_closures={Integer(3): ['edfg', 'acdg', 'bcfg', 'cefh',
...                 'afgh', 'abce', 'abdf', 'begh', 'bcdh', 'adeh'],
...                              Integer(4): ['abcdefgh']})
>>> M.equals(matroids.catalog.P8())
True
circuit_closures()[source]#

Return the closures of circuits of the matroid.

A circuit closure is a closed set containing a circuit.

OUTPUT: dictionary containing the circuit closures of the matroid, indexed by their ranks

See also

Matroid.circuit(), Matroid.closure()

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(matroids.catalog.Fano())
sage: CC = M.circuit_closures()
sage: len(CC[2])
7
sage: len(CC[3])
1
sage: len(CC[1])
Traceback (most recent call last):
...
KeyError: 1
sage: [sorted(X) for X in CC[3]]
[['a', 'b', 'c', 'd', 'e', 'f', 'g']]

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = CircuitClosuresMatroid(matroids.catalog.Fano())
>>> CC = M.circuit_closures()
>>> len(CC[Integer(2)])
7
>>> len(CC[Integer(3)])
1
>>> len(CC[Integer(1)])
Traceback (most recent call last):
...
KeyError: 1
>>> [sorted(X) for X in CC[Integer(3)]]
[['a', 'b', 'c', 'd', 'e', 'f', 'g']]
full_rank()[source]#

Return the rank of the matroid.

The rank of the matroid is the size of the largest independent subset of the groundset.

OUTPUT: integer

EXAMPLES:

sage: M = matroids.catalog.Vamos()
sage: M.full_rank()
4
sage: M.dual().full_rank()
4

>>> from sage.all import *
>>> M = matroids.catalog.Vamos()
>>> M.full_rank()
4
>>> M.dual().full_rank()
4
groundset()[source]#

Return the groundset of the matroid.

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

OUTPUT: frozenset

EXAMPLES:

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

>>> from sage.all import *
>>> M = matroids.catalog.Pappus()
>>> sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
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: from sage.matroids.circuit_closures_matroid import CircuitClosuresMatroid
sage: M = CircuitClosuresMatroid(matroids.catalog.RelaxedNonFano())
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
sage: N = M.relabel({'g': 'x', 0: 'z'})  # 'g': 'x' is ignored
sage: from sage.matroids.utilities import cmp_elements_key
sage: sorted(N.groundset(), key=cmp_elements_key)
[1, 2, 3, 4, 5, 6, 'z']
sage: M.is_isomorphic(N)
True

>>> from sage.all import *
>>> from sage.matroids.circuit_closures_matroid import CircuitClosuresMatroid
>>> M = CircuitClosuresMatroid(matroids.catalog.RelaxedNonFano())
>>> sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]
>>> N = M.relabel({'g': 'x', Integer(0): 'z'})  # 'g': 'x' is ignored
>>> from sage.matroids.utilities import cmp_elements_key
>>> sorted(N.groundset(), key=cmp_elements_key)
[1, 2, 3, 4, 5, 6, 'z']
>>> M.is_isomorphic(N)
True