# Matroids

## Introduction

Matroids are a fundamental combinatorial object with connections to various fields of mathematics. It is an abstraction of linear independence in vector spaces and forests in graphs. One way to define a *matroid* is via the following two sets of data:

- a finite
*ground set*$E := \{1,\ldots,n\}$ and - a nonempty finite set $\mathcal{B} \subseteq \mathcal{P}(E)$ of
*bases*satisfying an exchange property.

There are however many equivalent ways to define a matroid. One can also define a matroid via its *circuits*, *hyperplanes*, a *graph*, or a *matrix*. For a detailed introduction of matroids we refer to the textbook [Oxl11].

## Construction

`matroid_from_bases`

— Method`matroid_from_bases(B, [n, E])`

**Arguments**

`B::AbstractVector`

: The set of bases of the matroid.`n::InterUnion`

: The size of the ground set. The ground set will be`{1,..n}`

in this case.`E::AbstractVector`

: An explicit ground set passed as vector.

Construct a `matroid`

with bases `B`

on the ground set `E`

(which can be the empty set). The set `B`

is a non-empty collection of subsets of the ground set `E`

satisfying an exchange property, and the default value for `E`

is the set `{1,..n}`

for a non-negative value `n`

.

See Section 1.2 of [Oxl11].

**Examples**

To construct a rank two matroid with five bases on four elements you can write:

```
julia> B = [[1,2],[1,3],[1,4],[2,3],[2,4]];
julia> M = matroid_from_bases(B,4)
Matroid of rank 2 on 4 elements
```

To construct the same matroid on the four elements 1,2,i,j you may write:

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j'])
Matroid of rank 2 on 4 elements
```

`matroid_from_nonbases`

— Method`matroid_from_nonbases(N, [n, E])`

**Arguments**

`N::AbstractVector`

: The set of nonbases of the matroid.`n::InterUnion`

: The size of the ground set. The ground set will be`{1,..n}`

in this case.`E::AbstractVector`

: An explicit ground set passed as vector.

Construct a `matroid`

with nonbases `N`

on the ground set `E`

(which can be the empty set). That means that the matroid has as bases all subsets of the size `|N[1]|`

of the ground set that are not in `N`

. The set `N`

can't be empty in this function. The described complement of `N`

needs to be a non-empty collection of subsets of the ground set `E`

satisfying an exchange property, and the default value for `E`

is the set `{1,..n}`

for a non-negative value `n`

.

See Section 1.2 of [Oxl11].

**Examples**

To construct the Fano matroid you may write:

```
julia> H = [[1,2,4],[2,3,5],[1,3,6],[3,4,7],[1,5,7],[2,6,7],[4,5,6]];
julia> M = matroid_from_nonbases(H,7)
Matroid of rank 3 on 7 elements
```

`matroid_from_circuits`

— Method`matroid_from_circuits(C, [n, E])`

**Arguments**

`C::AbstractVector`

: The set of circuits of the matroid.`n::InterUnion`

: The size of the ground set. The ground set will be`{1,..n}`

in this case.`E::AbstractVector`

: An explicit ground set passed as vector.

A matroid with circuits `C`

on the ground set `E`

(which can be the empty set). The set `C`

is a collection of subsets of the ground set `E`

satisfying an exchange property, and the default value for `E`

is the set `{1,..n}`

for a non-negative value `n`

.

See Section 1.1 of [Oxl11].

**Examples**

To construct a rank two matroid with five bases on four elements by its circuits you may write:

```
julia> C = [[1,2,3],[1,2,4],[3,4]];
julia> M = matroid_from_circuits(C,4)
Matroid of rank 2 on 4 elements
```

To construct the same matroid on the ground set `{1,2,i,j}`

you may write:

```
julia> C = [[1,2,'j'],[1,2,'i'],['i','j']];
julia> M = matroid_from_circuits(C,[1,2,'i','j'])
Matroid of rank 2 on 4 elements
```

`matroid_from_hyperplanes`

— Method`matroid_from_hyperplanes(H, [n, E])`

**Arguments**

`H::AbstractVector`

: The set of hyperplanes of the matroid.`n::InterUnion`

: The size of the ground set. The ground set will be`{1,..n}`

in this case.`E::AbstractVector`

: An explicit ground set passed as vector.

A matroid with hyperplanes `H`

on the ground set `E`

(which can be the empty set). A hyperplane is a flat of rank `r-1`

. The set `H`

is a collection of subsets of the ground set `E`

satisfying an exchange property, and the default value for `E`

is the set `{1,..n}`

for a non-negative value `n`

.

See Section 1.4 of [Oxl11].

**Examples**

To construct the Fano matroid you may write:

```
julia> H = [[1,2,4],[2,3,5],[1,3,6],[3,4,7],[1,5,7],[2,6,7],[4,5,6]];
julia> M = matroid_from_hyperplanes(H,7)
Matroid of rank 3 on 7 elements
```

`matroid_from_matrix_columns`

— Method`matroid_from_matrix_columns(A::MatrixElem)`

A matroid represented by the column vectors of a matrix `A`

.

See Section 1.1 of [Oxl11].

**Examples**

To construct the vector matroid (a.k.a linear matroid) of the matrix `A`

over the field with two elements write:

```
julia> A = matrix(GF(2),[[1,0,1,1],[0,1,1,1]]);
julia> M = matroid_from_matrix_columns(A)
Matroid of rank 2 on 4 elements
```

`matroid_from_matrix_rows`

— Method`matroid_from_matrix_columns(A::MatrixElem)`

A matroid represented by the row vectors of a matrix.

See Section 1.1 of [Oxl11].

**Examples**

To construct the linear matroid of the rows of the matrix `A`

over the field with two elements write:

```
julia> A = matrix(GF(2),[[1,0],[0,1],[1,1],[1,1]]);
julia> M = matroid_from_matrix_rows(A)
Matroid of rank 2 on 4 elements
```

`cycle_matroid`

— Function`cycle_matroid(g::Graph{Undirected})`

The cycle matroid of a graph `g`

.

See Section 1.1 of [Oxl11].

**Examples**

To construct the cycle matroid of the complete graph of 4 vertices write:

```
julia> g = complete_graph(4);
julia> M = cycle_matroid(g)
Matroid of rank 3 on 6 elements
```

`bond_matroid`

— Method`bond_matroid(g::Graph)`

The "bond matroid" or "cocycle matroid" of a graph which is the dual of a cycle matroid, i.e., cographic.

See Section 2.3 of [Oxl11].

**Examples**

To construct the bond or cocycle matroid of the complete graph of 4 vertices write:

```
julia> g = complete_graph(4);
julia> M = bond_matroid(g)
Matroid of rank 3 on 6 elements
```

or equivalently

```
julia> g = complete_graph(4);
julia> M = cocycle_matroid(g)
Matroid of rank 3 on 6 elements
```

`cocycle_matroid`

— MethodSee `bond_matroid`

.

`Matroid`

— Type`Matroid(pm_matroid::Polymake.BigObjectAllocated, [E::GroundsetType])`

Construct a `matroid`

from a `polymake`

matroid `M`

on the default ground set `{1,...,n}`

.

`matroid_from_revlex_basis_encoding`

— Method`matroid_from_revlex_basis_encoding(rvlx::String, r::IntegerUnion, n::IntegerUnion)`

Construct a `matroid`

from a revlex-basis-encoding-string `rvlx`

of rank `r`

and size `n`

.

**Examples**

```
julia> matroid_from_revlex_basis_encoding("0******0******0***0******0*0**0****", 3, 7)
Matroid of rank 3 on 7 elements
```

`matroid_from_matroid_hex`

— Method`matroid_from_matroid_hex(str::AbstractString)`

Returns a matroid from a string of hex characters.

**Examples**

To retrieve the fano matroid from its hex encoding write:

```
julia> matroid_from_matroid_hex("r3n7_3f7eefd6f")
Matroid of rank 3 on 7 elements
```

## Examples

`uniform_matroid`

— Method`uniform_matroid(r,n)`

Construct the uniform matroid of rank `r`

on the `n`

elements `{1,...,n}`

.

`fano_matroid`

— Method`fano_matroid()`

Construct the Fano matroid.

`moebius_kantor_matroid`

— Method`moebius_kantor_matroid()`

Construct the Möbius-Kantor matroid.

`non_fano_matroid`

— Method`non_fano_matroid()`

Construct the non-Fano matroid.

`non_pappus_matroid`

— Method`non_pappus_matroid()`

Construct the non-Pappus matroid.

`pappus_matroid`

— Method`pappus_matroid()`

Construct the Pappus matroid.

`perles_matroid`

— Method`perles_matroid()`

Construct the Perles matroid.

`R10_matroid`

— Method`R10_matroid()`

Construct the R10 matroid.

`vamos_matroid`

— Method`vamos_matroid()`

Construct the Vamos matroid.

`all_subsets_matroid`

— Method`all_subsets_matroid(r)`

Construct the all-subsets-matroid of rank `r`

, a.k.a. the matroid underlying the resonance arrangement or rank `r`

.

`projective_plane`

— Method`projective_plane(q::Int)`

The projective plane of order `q`

. Note that this only works for prime numbers `q`

for now.

See Section 6.1 of [Oxl11].

**Examples**

```
julia> M = projective_plane(3)
Matroid of rank 3 on 13 elements
```

`projective_geometry`

— Method`projective_geometry(r::Int, q::Int)`

The projective geometry of order `q`

and rank `r+1`

. Note that this only works for prime numbers `q`

for now.

See Section 6.1 of [Oxl11]. Warning: Following the book of Oxley, the rank of the resulting matroid is `r+1`

.

**Examples**

```
julia> M = projective_geometry(2, 3)
Matroid of rank 3 on 13 elements
```

`affine_geometry`

— Method`affine_geometry(r::Int, q::Int)`

The affine geometry of order `q`

and rank `r+1`

. Note that this only works for prime numbers `q`

for now.

See Section 6.1 of [Oxl11]. Warning: Following the book of Oxley, the rank of the resulting matroid is `r+1`

.

**Examples**

```
julia> M = affine_geometry(2, 3)
Matroid of rank 3 on 9 elements
```

### Modifying matroids

`dual_matroid`

— Method`dual_matroid(M::Matroid)`

The `dual matroid`

of a given matroid `M`

.

See page 65 and Sectrion 2 in [Oxl11].

**Examples**

To construct the dual of the Fano matroid write:

```
julia> M = dual_matroid(fano_matroid())
Matroid of rank 4 on 7 elements
```

`direct_sum`

— Method`direct_sum(M::Matroid, N::Matroid)`

The `direct sum`

of the matroids `M`

and `N`

. Optionally one can also pass a vector of matroids.

See Section 4.2 of [Oxl11].

To obtain the direct sum of the Fano and a uniform matroid type:

**Examples**

```
julia> direct_sum(fano_matroid(), uniform_matroid(2,4))
Matroid of rank 5 on 11 elements
```

To take the sum of three uniform matroids use:

**Examples**

```
julia> matroids = Vector([uniform_matroid(2,4), uniform_matroid(1,3), uniform_matroid(3,4)]);
julia> M = direct_sum(matroids)
Matroid of rank 6 on 11 elements
```

`deletion`

— Method`deletion(M, [S, e])`

**Arguments**

`M::Matroid`

: A matroid`M`

.`S::GroundsetType`

: A subset`S`

of the ground set of`M`

.`e::ElementType`

: An element`e`

of the ground set of`M`

.

The `deletion M\S`

of an element `e`

or a subset `S`

of the ground set `E`

of the matroid `M`

.

See Section 3 of [Oxl11].

**Examples**

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j']);
julia> N = deletion(M,'i')
Matroid of rank 2 on 3 elements
```

**Examples**

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j']);
julia> N = deletion(M,['i','j'])
Matroid of rank 2 on 2 elements
julia> matroid_groundset(N)
2-element Vector{Any}:
1
2
```

`restriction`

— Method`restriction(M, S)`

**Arguments**

`M::Matroid`

: A matroid`M`

.`S::GroundSetType`

: A subset`S`

of the ground set of`M`

.

The `restriction M|S`

on a subset `S`

of the ground set `E`

of the matroid `M`

.

See Section 3 of [Oxl11].

**Examples**

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j']);
julia> N = restriction(M,[1,2])
Matroid of rank 2 on 2 elements
julia> matroid_groundset(N)
2-element Vector{Any}:
1
2
```

`contraction`

— Method`contraction(M, [S, e])`

**Arguments**

`M::Matroid`

: A matroid`M`

.`S::GroundSetType`

: A subset`S`

of the ground set of`M`

.`e::ElementType`

: An element`e`

of the ground set of`M`

.

The `contraction M/S`

of an element or a subset `S`

of the ground set `E`

of the matroid `M`

.

See Section 3 of [Oxl11].

**Examples**

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j']);
julia> N = contraction(M,'i')
Matroid of rank 1 on 3 elements
```

**Examples**

```
julia> M = matroid_from_bases([[1,2],[1,'i'],[1,'j'],[2,'i'],[2,'j']],[1,2,'i','j']);
julia> N = contraction(M,['i','j'])
Matroid of rank 1 on 2 elements
julia> matroid_groundset(N)
2-element Vector{Any}:
1
2
```

`minor`

— Method`minor(M::Matroid, set_del::GroundsetType, set_cont::GroundsetType)`

The `minor M\S/T`

of disjoint subsets `S`

and `T`

of the ground set `E`

of the matroid `M`

.

See also `contraction`

and `deletion`

. You can find more in Section 3 of [Oxl11].

**Examples**

```
julia> M = fano_matroid();
julia> S = [1,2,3];
julia> T = [4];
julia> N = minor(M,S,T)
Matroid of rank 2 on 3 elements
```

`principal_extension`

— Method`principal_extension(M::Matroid, F::GroundsetType, e::ElementType)`

The `principal extension M +_F e`

of a matroid `M`

where the element `e`

is freely added to the flat `F`

.

See Section 7.2 of [Oxl11].

**Examples**

To add `5`

freely to the flat `{1,2}`

of the uniform matroid `U_{3,4}`

do

```
julia> M = uniform_matroid(3,4);
julia> N = principal_extension(M,[1,2],5)
Matroid of rank 3 on 5 elements
```

`free_extension`

— Method`free_extension(M::Matroid, e::ElementType)`

The `free extension M +_E e`

of a matroid `M`

where the element `e`

.

See $principal_extension$ and Section 7.2 of [Oxl11].

**Examples**

To add `5`

freely to the uniform matroid `U_{3,4}`

do

```
julia> M = uniform_matroid(3,4);
julia> N = free_extension(M,5)
Matroid of rank 3 on 5 elements
```

`series_extension`

— Method`series_extension(M::Matroid, f::ElementType, e::ElementType)`

The `series extension`

of a matroid `M`

where the element `e`

is added in series to `f`

.

This is actually a coextension see also Section 7.2 of [Oxl11].

**Examples**

To add `e`

in series to `1`

in the uniform matroid U_{3,4} do

```
julia> M = uniform_matroid(1,4);
julia> N = series_extension(M,1,'e')
Matroid of rank 2 on 5 elements
julia> cocircuits(N)[1]
2-element Vector{Any}:
1
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
```

`parallel_extension`

— Method`parallel_extension(M::Matroid, f::ElementType, e::ElementType)`

The `parallel extension M +_{cl(f)} e`

of a matroid `M`

where the element `e`

is added parallel to (the closure of) `f`

.

See Section 7.2 of [Oxl11].

**Examples**

To add `e`

parallel to `1`

in the uniform matroid `U_{3,4}`

do

```
julia> M = uniform_matroid(3,4);
julia> N = parallel_extension(M,1,'e')
Matroid of rank 3 on 5 elements
julia> circuits(N)[1]
2-element Vector{Any}:
1
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
```

## Properties

`matroid_groundset`

— Method`matroid_groundset(M::Matroid)`

The ground set `E`

of a matroid `M`

.

To obtain the ground set of the Fano matroid write:

**Examples**

```
julia> matroid_groundset(fano_matroid())
7-element Vector{Int64}:
1
2
3
4
5
6
7
```

`length`

— Method`length(M::Matroid)`

Return the size of the ground set of the matroid `M`

.

**Examples**

```
julia> length(fano_matroid())
7
```

`rank`

— Method`rank(M::Matroid)`

Return the rank of the matroid `M`

.

**Examples**

```
julia> rank(fano_matroid())
3
```

`rank`

— Method`rank(M::Matroid, set::GroundsetType)`

Return the rank of `set`

in the matroid `M`

.

**Examples**

```
julia> M = fano_matroid();
julia> rank(M, [1,2,3])
2
```

`bases`

— Method`bases([::Type{Int},] M::Matroid)`

Return the list of bases of the matroid `M`

. If `Int`

is passed as a first argument then the bases will be returned as indices instead of ground set elements.

**Examples**

```
julia> bases(uniform_matroid(2, 3))
3-element Vector{Vector{Int64}}:
[1, 2]
[1, 3]
[2, 3]
```

`nonbases`

— Method`nonbases(M::Matroid)`

Return the list of nonbases of the matroid `M`

.

**Examples**

```
julia> nonbases(fano_matroid())
7-element Vector{Vector{Int64}}:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 4, 7]
[3, 5, 6]
```

`circuits`

— Method`circuits(M::Matroid)`

Return the list of circuits of the matroid `M`

.

**Examples**

```
julia> circuits(uniform_matroid(2, 4))
4-element Vector{Vector{Int64}}:
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
```

`hyperplanes`

— Method`hyperplanes(M::Matroid)`

Return the list of hyperplanes of the matroid `M`

.

**Examples**

```
julia> hyperplanes(fano_matroid())
7-element Vector{Vector{Int64}}:
[3, 5, 6]
[3, 4, 7]
[2, 5, 7]
[2, 4, 6]
[1, 6, 7]
[1, 4, 5]
[1, 2, 3]
```

`flats`

— Function`flats(M::Matroid, [r::Int])`

Return the list of flats of the matroid `M`

. By default all flats are returned. One may specify a rank `r`

as the second parameter in which case only the flats of rank `r`

are returned.

**Examples**

```
julia> M = fano_matroid()
Matroid of rank 3 on 7 elements
julia> flats(M)
16-element Vector{Vector{Int64}}:
[]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
[1, 2, 3, 4, 5, 6, 7]
julia> flats(M, 2)
7-element Vector{Vector{Int64}}:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
```

`cyclic_flats`

— Function`cyclic_flats(M::Matroid, [r::Int])`

Return the list of cyclic flats of the matroid `M`

. These are the flats that are the union of cycles. See Section 2.1 in [Oxl11].

By default all cyclic flats are returned. One may specify a rank `r`

as the second parameter. In this case only the cyclic flats of this rank are returned.

**Examples**

```
julia> M = fano_matroid()
Matroid of rank 3 on 7 elements
julia> cyclic_flats(M)
9-element Vector{Vector{Int64}}:
[]
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
[1, 2, 3, 4, 5, 6, 7]
julia> cyclic_flats(M, 2)
7-element Vector{Vector{Int64}}:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
```

`closure`

— Method`closure(M::Matroid, set::GroundsetType)`

Return the closure of `set`

in the matroid `M`

.

**Examples**

```
julia> closure(fano_matroid(), [1,2])
3-element Vector{Int64}:
1
2
3
```

`nullity`

— Method`nullity(M::Matroid, set::GroundsetType)`

Return the nullity of `set`

in the matroid `M`

. This is defined to be `|set| - rk(set)`

.

**Examples**

```
julia> M = fano_matroid();
julia> nullity(M, [1,2,3])
1
```

`fundamental_circuit`

— Method`fundamental_circuit(M::Matroid, basis::GroundsetType, elem::ElementType)`

Return the unique circuit contained in the union of `basis`

and `elem`

of the matroid `M`

. See Section 1.2 of [Oxl11]. Note that `elem`

needs to be in the complement of the `basis`

in this case.

**Examples**

```
julia> M = fano_matroid();
julia> fundamental_circuit(M, [1,2,4], 7)
4-element Vector{Int64}:
1
2
4
7
julia> fundamental_circuit(M, [1,2,4], 3)
3-element Vector{Int64}:
1
2
3
```

`fundamental_cocircuit`

— Method`fundamental_cocircuit(M::Matroid, cobasis::GroundsetType, elem::ElementType)`

Return the unique circuit of the dual matroid of `M`

in the union of the complement of `basis`

and `elem`

. See Section 2.1 of [Oxl11]. Note that `elem`

needs to be an element of the `basis`

in this case.

**Examples**

```
julia> fundamental_cocircuit(fano_matroid(), [1,2,4], 4)
4-element Vector{Int64}:
4
5
6
7
```

`independent_sets`

— Method`independent_sets(M::Matroid)`

Return the list of independent sets of the matroid `M`

. These are all subsets of the bases.

**Examples**

```
julia> independent_sets(uniform_matroid(2, 3))
7-element Vector{Vector{Int64}}:
[]
[1]
[2]
[3]
[1, 3]
[2, 3]
[1, 2]
```

`spanning_sets`

— Method`spanning_sets(M::Matroid)`

Return the list of spanning sets of the matroid `M`

. These are all sets containing a basis.

**Examples**

```
julia> spanning_sets(uniform_matroid(2, 3))
4-element Vector{Vector{Int64}}:
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]
```

`cobases`

— Method`cobases(M::Matroid)`

Return the bases of the dual matroid of `M`

. See Section 2 in [Oxl11].

**Examples**

```
julia> cobases(uniform_matroid(2, 3))
3-element Vector{Vector{Int64}}:
[3]
[2]
[1]
```

`cocircuits`

— Method`cocircuits(M::Matroid)`

Return the circuits of the dual matroid of `M`

. See Section 2 in [Oxl11].

**Examples**

```
julia> cocircuits(uniform_matroid(2, 5))
5-element Vector{Vector{Int64}}:
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
```

`cohyperplanes`

— Method`cohyperplanes(M::Matroid)`

Return the hyperplanes of the dual matroid of `M`

. See Section 2 in [Oxl11].

**Examples**

```
julia> cohyperplanes(fano_matroid())
14-element Vector{Vector{Int64}}:
[4, 5, 6, 7]
[2, 3, 6, 7]
[2, 3, 4, 5]
[1, 3, 5, 7]
[1, 3, 4, 6]
[1, 2, 5, 6]
[1, 2, 4, 7]
[3, 5, 6]
[3, 4, 7]
[2, 5, 7]
[2, 4, 6]
[1, 6, 7]
[1, 4, 5]
[1, 2, 3]
```

`corank`

— Method`corank(M::Matroid, set::GroundsetType)`

Return the rank of `set`

in the dual matroid of `M`

.

**Examples**

```
julia> corank(fano_matroid(), [1,2,3])
3
```

`is_clutter`

— Method`is_clutter(sets::AbstractVector{T}) where T <: GroundsetType`

Checks if the collection of subsets `sets`

is a clutter. A collection of subsets is a clutter if none of the sets is a proper subset of another. See Section 2.1 in [Oxl11].

**Examples**

```
julia> is_clutter([[1,2], [1,2,3]])
false
julia> is_clutter(circuits(fano_matroid()))
true
```

`is_regular`

— Method`is_regular(M::Matroid)`

Checks if the matroid `M`

is regular, that is representable over every field. See Section 6.6 in [Oxl11].

**Examples**

```
julia> is_regular(uniform_matroid(2, 3))
true
julia> is_regular(fano_matroid())
false
```

`is_binary`

— Method`is_binary(M::Matroid)`

Checks if the matroid `M`

is binary, that is representable over the finite field `F_2`

. See Section 6.5 in [Oxl11].

**Examples**

```
julia> is_binary(uniform_matroid(2, 4))
false
julia> is_binary(fano_matroid())
true
```

`is_ternary`

— Method`is_ternary(M::Matroid)`

Checks if the matroid `M`

is ternary, that is representable over the finite field `F_3`

. See Section 4.1 in [Oxl11].

**Examples**

```
julia> is_ternary(uniform_matroid(2, 4))
true
julia> is_ternary(fano_matroid())
false
```

`n_connected_components`

— Method`n_connected_components(M::Matroid)`

Return the number of connected components of `M`

. See Section 4.1 in [Oxl11].

**Examples**

```
julia> n_connected_components(fano_matroid())
1
julia> n_connected_components(uniform_matroid(3, 3))
3
```

`connected_components`

— Method`connected_components(M::Matroid)`

Return the connected components of `M`

. The function returns a partition of the ground set where each part corresponds to one connected component. See Section 4.1 in [Oxl11].

**Examples**

```
julia> connected_components(fano_matroid())
1-element Vector{Vector{Int64}}:
[1, 2, 3, 4, 5, 6, 7]
julia> connected_components(uniform_matroid(3, 3))
3-element Vector{Vector{Int64}}:
[1]
[2]
[3]
```

`is_connected`

— Method`is_connected(M::Matroid)`

Check if the matroid `M`

is connected, that is has one connected component See Section 4.1 in [Oxl11].

**Examples**

```
julia> is_connected(fano_matroid())
true
julia> is_connected(uniform_matroid(3, 3))
false
```

`loops`

— Method`loops(M::Matroid)`

Return the loops of `M`

. A loop is an element of the ground set that is not contained in any basis.

**Examples**

```
julia> loops(matroid_from_bases([[1,2]], 4))
2-element Vector{Int64}:
3
4
julia> loops(fano_matroid())
Int64[]
```

`coloops`

— Method`coloops(M::Matroid)`

Return the coloops of `M`

. A coloop is an element of the ground set that is contained in every basis.

**Examples**

```
julia> coloops(matroid_from_bases([[1,2]], 4))
2-element Vector{Int64}:
1
2
julia> coloops(fano_matroid())
Int64[]
```

`is_loopless`

— Method`is_loopless(M::Matroid)`

Check if `M`

has a loop. Return `true`

if `M`

does not have a loop. See also `loops`

.

**Examples**

```
julia> is_loopless(matroid_from_bases([[1,2]], 4))
false
julia> is_loopless(fano_matroid())
true
```

`is_coloopless`

— Method`is_coloopless(M::Matroid)`

Check if `M`

has a coloop. Return `true`

if `M`

does not have a coloop. See also `coloops`

.

**Examples**

```
julia> is_coloopless(matroid_from_bases([[1,2]], 4))
false
julia> is_coloopless(fano_matroid())
true
```

`is_simple`

— Method`is_simple(M::Matroid)`

Check if `M`

has is simple. A matroid is simple if it doesn't have loops and doesn't have parallel elements. Return `true`

if `M`

is simple. See also `loops`

.

**Examples**

```
julia> is_simple(matroid_from_bases([[1,2]], 4))
false
julia> is_simple(fano_matroid())
true
```

`direct_sum_components`

— Method`direct_sum_components(M::Matroid)`

Return the connected components of `M`

as a list of matroids. See Section 4.1 in [Oxl11].

**Examples**

```
julia> direct_sum_components(fano_matroid())
1-element Vector{Matroid}:
Matroid of rank 3 on 7 elements
julia> direct_sum_components(uniform_matroid(3, 3))
3-element Vector{Matroid}:
Matroid of rank 1 on 1 elements
Matroid of rank 1 on 1 elements
Matroid of rank 1 on 1 elements
```

`connectivity_function`

— Method`connectivity_function(M::Matroid, set::GroundsetType)`

Return the value of the connectivity function of `set`

in the matroid `M`

. See Section 8.1 in [Oxl11].

**Examples**

```
julia> connectivity_function(fano_matroid(), [1,2,4])
3
```

`is_vertical_k_separation`

— Method`is_vertical_k_separation(M::Matroid, k::IntegerUnion, set::GroundsetType)`

Check if `set`

together with its complement defines a `k`

separation in `M`

See Section 8.6 in [Oxl11].

**Examples**

```
julia> is_vertical_k_separation(fano_matroid(), 2, [1,2,4])
false
```

`is_k_separation`

— Method`is_k_separation(M::Matroid, k::IntegerUnion, set::GroundsetType)`

Check if `set`

together with its complement defines a `k`

separation in `M`

See Section 8.1 in [Oxl11].

**Examples**

```
julia> is_k_separation(fano_matroid(), 2, [1,2,4])
false
```

`vertical_connectivity`

— Method`vertical_connectivity(M::Matroid)`

If 'M' has two disjoint cocircuits, its vertical connectivity is defined to be least positive integer k such that `M`

has a vertical k separation. Otherwise its vertical connectivity is defined to be the rank of `M`

. See Section 8.6 in [Oxl11].

**Examples**

```
julia> vertical_connectivity(fano_matroid())
3
```

`girth`

— Function`girth(M::Matroid, set::GroundsetType)`

Return the girth of `set`

in the matroid `M`

. This is the size of the smallest circuit contained in `set`

and infinite otherwise. See Section 8.6 in [Oxl11].

**Examples**

```
julia> girth(fano_matroid(), [1,2,3,4])
3
```

`tutte_connectivity`

— Method`tutte_connectivity(M::Matroid)`

The Tutte connectivity of `M`

is the least integer k such that `M`

has a k separation. It can be infinite if no k separation exists. See Section 8.6 in [Oxl11].

**Examples**

```
julia> tutte_connectivity(fano_matroid())
3
julia> tutte_connectivity(uniform_matroid(2,4))
infinity
```

`tutte_polynomial`

— Method`tutte_polynomial(M::Matroid)`

Return the Tutte polynomial of `M`

. This is polynomial in the variables x and y with integral coefficients. See Section 15.3 in [Oxl11].

**Examples**

```
julia> tutte_polynomial(fano_matroid())
x^3 + 4*x^2 + 7*x*y + 3*x + y^4 + 3*y^3 + 6*y^2 + 3*y
```

`characteristic_polynomial`

— Method`characteristic_polynomial(M::Matroid)`

Return the characteristic polynomial of `M`

. This is polynomial in the variable q with integral coefficients. It is computed as an evaluation of the Tutte polynmomial. See Section 15.2 in [Oxl11].

**Examples**

```
julia> characteristic_polynomial(fano_matroid())
q^3 - 7*q^2 + 14*q - 8
```

`reduced_characteristic_polynomial`

— Method`reduced_characteristic_polynomial(M::Matroid)`

Return the reduced characteristic polynomial of `M`

. This is the quotient of the characteristic polynomial by (q-1). See Section 15.2 in [Oxl11].

**Examples**

```
julia> reduced_characteristic_polynomial(fano_matroid())
q^2 - 6*q + 8
```

`revlex_basis_encoding`

— Method`revlex_basis_encoding(M::Matroid)`

Computes the revlex basis encoding of the matroid M.

**Examples**

To get the revlex basis encoding of the fano matroid and to produce a matrod form the encoding write:

```
julia> str = revlex_basis_encoding(fano_matroid())
"0******0******0***0******0*0**0****"
julia> matroid_from_revlex_basis_encoding(str, 3, 7)
Matroid of rank 3 on 7 elements
```

`is_isomorphic`

— Method`is_isomorphic(M1::Matroid, M2::Matroid)`

Checks if the matroid `M1`

is isomorphic to the matroid `M2`

under the action of the symmetric group that acts on their groundsets.

**Examples**

To compare two matrods write:

```
julia> H = [[1,2,4],[2,3,5],[1,3,6],[3,4,7],[1,5,7],[2,6,7],[4,5,6]];
julia> M = matroid_from_hyperplanes(H,7);
julia> is_isomorphic(M,fano_matroid())
true
```

`is_minor`

— Method`is_minor(M::Matroid, N::Matroid)`

Checks if the matroid `M`

is isomorphic to a minor of the matroid `N`

.

**Examples**

```
julia> is_minor(direct_sum(uniform_matroid(0,1), uniform_matroid(2,2)), fano_matroid())
false
julia> is_minor(direct_sum(uniform_matroid(0,1), uniform_matroid(2,2)), parallel_extension(uniform_matroid(3,4), 1, 5))
true
```

`matroid_hex`

— Method`matroid_hex(M::Matroid)`

Stores a matroid as a string of hex characters. The first part of the string is "r" followed by the rank of the matroid. This is followed by "n" and the number of elements. The rest of the string is the revlex basis encoding. The encoding is done by converting the basis encoding to a vector of bits and then to a string of characters. The bits are padded to a multiple of 4 and then converted to hex characters.

**Examples**

To get the hex encoding of the fano matroid write:

```
julia> matroid_hex(fano_matroid())
"r3n7_3f7eefd6f"
```

`automorphism_group`

— Method`automorphism_group(M::Matroid)`

Given a matroid `M`

return its automorphism group as a `PermGroup`

. The group acts on the elements of `M`

.

**Examples**

```
julia> M = uniform_matroid(2, 4)
Matroid of rank 2 on 4 elements
julia> automorphism_group(M)
Permutation group of degree 4
```

`matroid_base_polytope`

— Method`matroid_base_polytope(M::Matroid)`

The base polytope of the matroid `M`

.

**Examples**

```
julia> D = matroid_base_polytope(uniform_matroid(2,4));
julia> vertices(D)
6-element SubObjectIterator{PointVector{QQFieldElem}}:
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 1, 1, 0]
[0, 1, 0, 1]
[0, 0, 1, 1]
```

### Chow Rings

`chow_ring`

— Method`chow_ring(M::Matroid; ring::MPolyRing=nothing, extended::Bool=false)`

Return the Chow ring of a matroid, optionally also with the simplicial generators and the polynomial ring.

**Examples**

The following computes the Chow ring of the Fano matroid.

```
julia> M = fano_matroid();
julia> R = chow_ring(M);
julia> R[1]*R[8]
-x_{3,4,7}^2
```

The following computes the Chow ring of the Fano matroid including variables for the simplicial generators.

```
julia> M = fano_matroid();
julia> R = chow_ring(M, extended=true);
julia> f = R[22] + R[8] - R[29]
x_{1,2,3} + h_{1,2,3} - h_{1,2,3,4,5,6,7}
julia> f==0
true
```

The following computes the Chow ring of the free matroid on three elements in a given graded polynomial ring.

```
julia> M = uniform_matroid(3,3);
julia> GR, _ = graded_polynomial_ring(QQ,["a","b","c","d","e","f"]);
julia> R = chow_ring(M, ring=GR);
julia> hilbert_series_reduced(R)
(t^2 + 4*t + 1, 1)
```

`augmented_chow_ring`

— Method`augmented_chow_ring(M::Matroid)`

Return an augmented Chow ring of a matroid. As described in [BHMPW20].

**Examples**

```
julia> M = fano_matroid();
julia> R = augmented_chow_ring(M);
```

### Quantum Automorphisms

`quantum_symmetric_group`

— Method`quantum_symmetric_group(n::Int)`

Return the ideal that defines the quantum symmetric group on `n`

elements. It is comprised of `2*n + n^2 + 2*n*n*(n-1)`

many generators.

The relations are:

- row and column sum relations:
`2*n`

relations - idempotent relations:
`n^2`

relations - relations of type
`u[i,j]*u[i,k]`

and`u[j,i]*u[k,i]`

for`k != j`

:`2*n*n*(n-1)`

relations

**Example**

```
julia> S4 = quantum_symmetric_group(4);
julia> length(gens(S4))
120
```

`quantum_automorphism_group`

— Method`quantum_automorphism_group(M::Matroid, structure::Symbol=:bases)`

Return the ideal that defines the quantum automorphism group of a matroid for a given structure.

**Examples**

```
julia> G = complete_graph(4)
Undirected graph with 4 nodes and the following edges:
(2, 1)(3, 1)(3, 2)(4, 1)(4, 2)(4, 3)
julia> M = cycle_matroid(G);
julia> qAut = quantum_automorphism_group(M,:bases);
julia> length(gens(qAut))
23448
```