# Circuit closures matroids¶

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 *


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'),
sage: M1 == M2
True
sage: 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


AUTHORS:

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

TESTS:

sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(matroids.named_matroids.Fano())
sage: TestSuite(M).run()


## Methods¶

class sage.matroids.circuit_closures_matroid.CircuitClosuresMatroid

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 $${n \choose 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 ground set 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 – (default: None) an arbitrary matroid.
• groundset – (default: None) the groundset of a matroid.
• circuit_closures – (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.named_matroids.Fano())
sage: M
Matroid of rank 3 on 7 elements with circuit-closures
{2: {{'b', 'e', 'g'}, {'b', 'c', 'd'}, {'a', 'c', 'e'},
{'c', 'f', 'g'}, {'d', 'e', 'f'}, {'a', 'd', 'g'},
{'a', 'b', '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.named_matroids.P8())
True

circuit_closures()

Return the list of closures of circuits of the matroid.

A circuit closure is a closed set containing a circuit.

OUTPUT:

A dictionary containing the circuit closures of the matroid, indexed by their ranks.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = CircuitClosuresMatroid(matroids.named_matroids.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']]

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:

Integer.

EXAMPLES:

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

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.named_matroids.Pappus()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']