Circuits matroids#
Matroids are characterized by a list of circuits, which are minimal dependent
sets. The CircuitsMatroid
class implements matroids using this information
as data.
A CircuitsMatroid
can be created from another matroid or from a list of
circuits. For a full description of allowed inputs, see
below
. It is
recommended to use the Matroid()
function for a more flexible way of constructing a CircuitsMatroid
and
other classes of matroids. For direct access to the CircuitsMatroid
constructor, run:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid
>>> from sage.all import *
>>> from sage.matroids.circuits_matroid import CircuitsMatroid
AUTHORS:
Giorgos Mousa (2023-12-23): initial version
- class sage.matroids.circuits_matroid.CircuitsMatroid[source]#
Bases:
Matroid
A matroid defined by its circuits.
INPUT:
M
– matroid (default:None
)groundset
– list (default:None
); the groundset of the matroidcircuits
– list (default:None
); the collection of circuits of the matroidnsc_defined
– boolean (default:False
); whether the matroid was defined by its nonspanning circuits
Note
For a more flexible means of input, use the
Matroid()
function.- bases_iterator()[source]#
Return an iterator over the bases of the matroid.
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: it = M.bases_iterator() sage: it.__next__() frozenset({0, 1}) sage: sorted(M.bases_iterator(), key=str) [frozenset({0, 1}), frozenset({0, 2}), frozenset({0, 3}), frozenset({1, 2}), frozenset({1, 3}), frozenset({2, 3})]
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.Uniform(Integer(2), Integer(4))) >>> it = M.bases_iterator() >>> it.__next__() frozenset({0, 1}) >>> sorted(M.bases_iterator(), key=str) [frozenset({0, 1}), frozenset({0, 2}), frozenset({0, 3}), frozenset({1, 2}), frozenset({1, 3}), frozenset({2, 3})]
- broken_circuit_complex(ordering=None, reduced=False)[source]#
Return the broken circuit complex of
self
.The broken circuit complex of a matroid with a total ordering \(<\) on the groundset is obtained from the
NBC sets
under subset inclusion.INPUT:
ordering
– list (optional); a total ordering of the groundsetreduced
– boolean (default:False
); whether to return the reduced broken circuit complex (the link at the smallest element)
OUTPUT: a simplicial complex of the NBC sets under inclusion
EXAMPLES:
sage: M = Matroid(circuits=[[1, 2, 3], [3, 4, 5], [1, 2, 4, 5]]) sage: M.broken_circuit_complex() Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)} sage: M.broken_circuit_complex([5, 4, 3, 2, 1]) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)} sage: M.broken_circuit_complex([5, 4, 3, 2, 1], reduced=True) Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 3), (1, 4), (2, 3), (2, 4)}
>>> from sage.all import * >>> M = Matroid(circuits=[[Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]]) >>> M.broken_circuit_complex() Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)} >>> M.broken_circuit_complex([Integer(5), Integer(4), Integer(3), Integer(2), Integer(1)]) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)} >>> M.broken_circuit_complex([Integer(5), Integer(4), Integer(3), Integer(2), Integer(1)], reduced=True) Simplicial complex with vertex set (1, 2, 3, 4) and facets {(1, 3), (1, 4), (2, 3), (2, 4)}
For a matroid with loops, the broken circuit complex is not defined, and the method yields an error:
sage: M = Matroid(groundset=[0, 1, 2], circuits=[[0]]) sage: M.broken_circuit_complex() Traceback (most recent call last): ... ValueError: broken circuit complex of matroid with loops is not defined
>>> from sage.all import * >>> M = Matroid(groundset=[Integer(0), Integer(1), Integer(2)], circuits=[[Integer(0)]]) >>> M.broken_circuit_complex() Traceback (most recent call last): ... ValueError: broken circuit complex of matroid with loops is not defined
- circuits(k=None)[source]#
Return the circuits of the matroid.
INPUT:
k
– integer (optional); the length of the circuits
OUTPUT:
SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: M.circuits() SetSystem of 4 sets over 4 elements sage: list(M.circuits(0)) [] sage: sorted(M.circuits(3), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.Uniform(Integer(2), Integer(4))) >>> M.circuits() SetSystem of 4 sets over 4 elements >>> list(M.circuits(Integer(0))) [] >>> sorted(M.circuits(Integer(3)), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
- circuits_iterator(k=None)[source]#
Return an iterator over the circuits of the matroid.
INPUT:
k
– integer (optional); the length of the circuits
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: sum(1 for C in M.circuits_iterator()) 4 sage: list(M.circuits_iterator(0)) [] sage: sorted(M.circuits_iterator(3), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.Uniform(Integer(2), Integer(4))) >>> sum(Integer(1) for C in M.circuits_iterator()) 4 >>> list(M.circuits_iterator(Integer(0))) [] >>> sorted(M.circuits_iterator(Integer(3)), key=str) [frozenset({0, 1, 2}), frozenset({0, 1, 3}), frozenset({0, 2, 3}), frozenset({1, 2, 3})]
- dependent_sets(k)[source]#
Return the dependent sets of fixed size.
INPUT:
k
– integer
OUTPUT:
SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.catalog.Vamos()) sage: M.dependent_sets(3) SetSystem of 0 sets over 8 elements sage: sorted([sorted(X) for X in M.dependent_sets(4)]) [['a', 'b', 'c', 'd'], ['a', 'b', 'e', 'f'], ['a', 'b', 'g', 'h'], ['c', 'd', 'e', 'f'], ['e', 'f', 'g', 'h']]
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.catalog.Vamos()) >>> M.dependent_sets(Integer(3)) SetSystem of 0 sets over 8 elements >>> sorted([sorted(X) for X in M.dependent_sets(Integer(4))]) [['a', 'b', 'c', 'd'], ['a', 'b', 'e', 'f'], ['a', 'b', 'g', 'h'], ['c', 'd', 'e', 'f'], ['e', 'f', 'g', 'h']]
- 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.Theta(20) sage: M.full_rank() 20
>>> from sage.all import * >>> M = matroids.Theta(Integer(20)) >>> M.full_rank() 20
- girth()[source]#
Return the girth of the matroid.
The girth is the size of the smallest circuit. In case the matroid has no circuits the girth is \(\infty\).
EXAMPLES:
sage: matroids.Theta(10).girth() 3
>>> from sage.all import * >>> matroids.Theta(Integer(10)).girth() 3
REFERENCES:
[Oxl2011], p. 327.
- groundset()[source]#
Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT: set
EXAMPLES:
sage: M = matroids.Theta(2) sage: sorted(M.groundset()) ['x0', 'x1', 'y0', 'y1']
>>> from sage.all import * >>> M = matroids.Theta(Integer(2)) >>> sorted(M.groundset()) ['x0', 'x1', 'y0', 'y1']
- independent_sets(k=-1)[source]#
Return the independent sets of the matroid.
INPUT:
k
– integer (optional); if specified, return the size-\(k\) independent sets of the matroid
OUTPUT:
SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.catalog.Pappus()) sage: M.independent_sets(4) SetSystem of 0 sets over 9 elements sage: M.independent_sets(3) SetSystem of 75 sets over 9 elements sage: frozenset({'a', 'c', 'e'}) in _ True
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.catalog.Pappus()) >>> M.independent_sets(Integer(4)) SetSystem of 0 sets over 9 elements >>> M.independent_sets(Integer(3)) SetSystem of 75 sets over 9 elements >>> frozenset({'a', 'c', 'e'}) in _ True
See also
M.bases()
- is_paving()[source]#
Return if
self
is paving.A matroid is paving if each of its circuits has size \(r\) or \(r+1\).
OUTPUT: boolean
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.catalog.Vamos()) sage: M.is_paving() True
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.catalog.Vamos()) >>> M.is_paving() True
- is_valid()[source]#
Test if
self
obeys the matroid axioms.For a matroid defined by its circuits, we check the circuit axioms.
OUTPUT: boolean
EXAMPLES:
sage: C = [[1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() True sage: C = [[1, 2], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[3, 6], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[3, 6], [1, 2, 3], [3, 4, 5], [1, 2, 6], [6, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() True sage: C = [[], [1, 2, 3], [3, 4, 5], [1, 2, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False sage: C = [[1, 2, 3], [3, 4, 5]] sage: M = Matroid(circuits=C) sage: M.is_valid() False
>>> from sage.all import * >>> C = [[Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() True >>> C = [[Integer(1), Integer(2)], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() False >>> C = [[Integer(3), Integer(6)], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() False >>> C = [[Integer(3), Integer(6)], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(6)], [Integer(6), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() True >>> C = [[], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() False >>> C = [[Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)]] >>> M = Matroid(circuits=C) >>> M.is_valid() False
- no_broken_circuits_facets(ordering=None, reduced=False)[source]#
Return the no broken circuits (NBC) facets of
self
.INPUT:
ordering
– list (optional); a total ordering of the groundsetreduced
– boolean (default:False
)
OUTPUT:
SetSystem
EXAMPLES:
sage: M = Matroid(circuits=[[0, 1, 2]]) sage: M.no_broken_circuits_facets(ordering=[1, 0, 2]) SetSystem of 2 sets over 3 elements sage: sorted([sorted(X) for X in _]) [[0, 1], [1, 2]] sage: M.no_broken_circuits_facets(ordering=[1, 0, 2], reduced=True) SetSystem of 2 sets over 3 elements sage: sorted([sorted(X) for X in _]) [[0], [2]]
>>> from sage.all import * >>> M = Matroid(circuits=[[Integer(0), Integer(1), Integer(2)]]) >>> M.no_broken_circuits_facets(ordering=[Integer(1), Integer(0), Integer(2)]) SetSystem of 2 sets over 3 elements >>> sorted([sorted(X) for X in _]) [[0, 1], [1, 2]] >>> M.no_broken_circuits_facets(ordering=[Integer(1), Integer(0), Integer(2)], reduced=True) SetSystem of 2 sets over 3 elements >>> sorted([sorted(X) for X in _]) [[0], [2]]
- no_broken_circuits_sets(ordering=None, reduced=False)[source]#
Return the no broken circuits (NBC) sets of
self
.An NBC set is a subset \(A\) of the groundset under some total ordering \(<\) such that \(A\) contains no broken circuit.
INPUT:
ordering
– list (optional); a total ordering of the groundsetreduced
– boolean (default:False
)
OUTPUT:
SetSystem
EXAMPLES:
sage: M = Matroid(circuits=[[1, 2, 3], [3, 4, 5], [1, 2, 4, 5]]) sage: SimplicialComplex(M.no_broken_circuits_sets()) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)} sage: SimplicialComplex(M.no_broken_circuits_sets([5, 4, 3, 2, 1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)}
>>> from sage.all import * >>> M = Matroid(circuits=[[Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)], [Integer(1), Integer(2), Integer(4), Integer(5)]]) >>> SimplicialComplex(M.no_broken_circuits_sets()) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)} >>> SimplicialComplex(M.no_broken_circuits_sets([Integer(5), Integer(4), Integer(3), Integer(2), Integer(1)])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)}
sage: M = Matroid(circuits=[[1, 2, 3], [1, 4, 5], [2, 3, 4, 5]]) sage: SimplicialComplex(M.no_broken_circuits_sets([5, 4, 3, 2, 1])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (2, 3, 5), (2, 4, 5), (3, 4, 5)}
>>> from sage.all import * >>> M = Matroid(circuits=[[Integer(1), Integer(2), Integer(3)], [Integer(1), Integer(4), Integer(5)], [Integer(2), Integer(3), Integer(4), Integer(5)]]) >>> SimplicialComplex(M.no_broken_circuits_sets([Integer(5), Integer(4), Integer(3), Integer(2), Integer(1)])) Simplicial complex with vertex set (1, 2, 3, 4, 5) and facets {(1, 3, 5), (2, 3, 5), (2, 4, 5), (3, 4, 5)}
- nonspanning_circuits()[source]#
Return the nonspanning circuits of the matroid.
OUTPUT:
SetSystem
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: M.nonspanning_circuits() SetSystem of 0 sets over 4 elements sage: M = matroids.Theta(5) sage: M.nonspanning_circuits() SetSystem of 15 sets over 10 elements
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.Uniform(Integer(2), Integer(4))) >>> M.nonspanning_circuits() SetSystem of 0 sets over 4 elements >>> M = matroids.Theta(Integer(5)) >>> M.nonspanning_circuits() SetSystem of 15 sets over 10 elements
- nonspanning_circuits_iterator()[source]#
Return an iterator over the nonspanning circuits of the matroid.
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(matroids.Uniform(2, 4)) sage: list(M.nonspanning_circuits_iterator()) []
>>> from sage.all import * >>> from sage.matroids.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(matroids.Uniform(Integer(2), Integer(4))) >>> list(M.nonspanning_circuits_iterator()) []
- relabel(mapping)[source]#
Return an isomorphic matroid with relabeled groundset.
The output is obtained by relabeling each element \(e\) by
mapping[e]
, wheremapping
is a given injective map. Ifmapping[e]
is not defined, then the identity map is assumed.INPUT:
mapping
– a Python object such thatmapping[e]
is the new label of \(e\)
OUTPUT: matroid
EXAMPLES:
sage: from sage.matroids.circuits_matroid import CircuitsMatroid sage: M = CircuitsMatroid(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.circuits_matroid import CircuitsMatroid >>> M = CircuitsMatroid(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