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 matroid

  • circuits – list (default: None); the collection of circuits of the matroid

  • nsc_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 groundset

  • reduced – 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 groundset

  • reduced – 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 groundset

  • reduced – 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], 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.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