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