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

AUTHORS:

  • Giorgos Mousa (2023-12-23): initial version

class sage.matroids.circuits_matroid.CircuitsMatroid#

Bases: Matroid

A matroid defined by its circuits.

INPUT:

  • M – a matroid (default: None)

  • groundset – a list (default: None); the groundset of the matroid

  • circuits – a 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()#

Return the bases of the matroid.

OUTPUT: a SetSystem

EXAMPLES:

sage: from sage.matroids.circuits_matroid import CircuitsMatroid
sage: M = CircuitsMatroid(matroids.Uniform(2, 4))
sage: len(M.bases())
6
bases_iterator()#

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})]
circuits(k=None)#

Return the circuits of the matroid.

INPUT:

  • k – an integer (optional); the length of the circuits

OUTPUT: a SetSystem

EXAMPLES:

sage: from sage.matroids.circuits_matroid import CircuitsMatroid
sage: M = CircuitsMatroid(matroids.Uniform(2, 4))
sage: M.circuits()
Iterator over a system of subsets
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})]
circuits_iterator(k=None)#

Return an iterator over the circuits of the matroid.

INPUT:

  • k – an 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})]
full_rank()#

Return the rank of the matroid.

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

OUTPUT: an integer; the rank of the matroid

EXAMPLES:

sage: M = matroids.Theta(20)
sage: M.full_rank()
20
girth()#

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

REFERENCES:

[Oxl2011], p. 327.

groundset()#

Return the groundset of the matroid.

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

OUTPUT: a set

EXAMPLES:

sage: M = matroids.Theta(2)
sage: sorted(M.groundset())
['x0', 'x1', 'y0', 'y1']
is_paving()#

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
is_valid()#

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
no_broken_circuits_sets(ordering=None)#

Return the no broken circuits (NBC) sets of self.

An NBC set is a subset \(A\) of the ground set under some total ordering \(<\) such that \(A\) contains no broken circuit.

INPUT:

  • ordering – a total ordering of the groundset given as a list

OUTPUT: a list of frozensets

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)}

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)}
nonspanning_circuits()#

Return the nonspanning circuits of the matroid.

OUTPUT: a SetSystem

EXAMPLES:

sage: from sage.matroids.circuits_matroid import CircuitsMatroid
sage: M = CircuitsMatroid(matroids.Uniform(2, 4))
sage: M.nonspanning_circuits()
Iterator over a system of subsets
nonspanning_circuits_iterator()#

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())
[]