# 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 James Oxley (2011).

## 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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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`

— Method`cycle_matroid(g::Graph)`

The cycle matroid of a graph `g`

.

See Section 1.1 of James Oxley (2011).

**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 James Oxley (2011).

**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
```

## 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.

`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.

`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 James Oxley (2011).

**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 James Oxley (2011). 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 James Oxley (2011). 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 James Oxley (2011).

**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 James Oxley (2011).

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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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(M::Matroid)`

Return the list of bases of the matroid `M`

.

**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{T} where T}:
Any[]
[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{T} where T}:
[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 James Oxley (2011).

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{T} where T}:
Any[]
[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{T} where T}:
[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 James Oxley (2011). 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 James Oxley (2011). 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{Integer}}:
[]
[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{Integer}}:
[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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

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

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

`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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 infintie otherwise. See Section 8.6 in James Oxley (2011).

**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 James Oxley (2011).

**Examples**

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

`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 James Oxley (2011).

**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 James Oxley (2011).

**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 James Oxley (2011).

**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 and the minimal revlex basis encoding among isomorphic matroids

**Examples**

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

```
julia> string1, string2 = revlex_basis_encoding(fano_matroid())
("0******0******0***0******0*0**0****", "0******0******0***0******0*0**0****")
julia> matroid_from_revlex_basis_encoding(string2, 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
```

### 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.

See Karim Adiprasito, June Huh, Eric Katz (2018) and Spencer Backman, Christopher Eur, Connor Simpson (2019).

**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, _ = GradedPolynomialRing(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 Tom Braden, June Huh, Jacob P. Matherne, Nicholas Proudfoot, Botong Wang (2020).

**Examples**

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

## Matroid strata and realization spaces

For a matroid $M$, of rank $d$ on a ground set $E$ of size $n$ realizable over a ring $K$, its *matroid realization space* $\mathsf{Gr}(M)$ is the locally closed subscheme of the Grassmannian $\mathsf{Gr}(d,K^n)$ of $d$-dimensional subspaces of $K^n$ realizing $M$. Precisely,

\[ \mathsf{Gr}(M) = \{F \in \mathsf{Gr}(d,K^n) \, : \, p_{I}(F) \neq 0 \text{ iff } I \in \mathcal{B}(M)\}\]

where $\mathcal{B}(M)$ denotes the set of bases of $M$ and $p_{I}(F)$ denotes the $I$th Pl\"ucker coordinate of the linear subspace $F \subset K^n$. The coordinate ring of $\mathsf{Gr}(M)$ can be computed using matrix coordinates, see Construction 2.2 of D. Corey (2021). The following function computes this ring.

`matroid_stratum_matrix_coordinates`

— Function`matroid_stratum_matrix_coordinates(M::Matroid, B::GroundsetType, F::AbstractAlgebra.Ring = ZZ)`

Return the data of the coordinate ring of the matroid stratum of M in the Grassmannian with respect to matrix coordinates. Here, `B`

is a basis of `M`

`and the submatrix with columns indexed by`

B' is the identity. This function returns a pair `(A, W)`

where `A`

is the coordinate matrix, and `W`

is the coordinate ring of the stratum, in general this is a localized quotient ring.

**Examples**

```
julia> M = fano_matroid();
julia> (A, W) = matroid_stratum_matrix_coordinates(M, [1,2,4], GF(2));
julia> A # The coordinate matrix with entries in the polynomial ring `R`.
[1 0 x[1, 1] 0 x[1, 2] 0 x[1, 4]]
[0 1 x[2, 1] 0 0 x[2, 3] x[2, 4]]
[0 0 0 1 x[3, 2] x[3, 3] x[3, 4]]
julia> W # The coordinate ring of the stratum; in general a localized quotient ring `(R/I)[S⁻¹]`.
Localization of Quotient of Multivariate Polynomial Ring in 9 variables x[1, 1], x[2, 1], x[1, 2], x[3, 2], ..., x[3, 4] over Galois field with characteristic 2 by ideal(x[2, 3]*x[3, 4] + x[3, 3]*x[2, 4], x[1, 2]*x[3, 4] + x[3, 2]*x[1, 4], x[1, 1]*x[2, 4] + x[2, 1]*x[1, 4], x[1, 1]*x[3, 2]*x[2, 3] + x[2, 1]*x[1, 2]*x[3, 3]) at the multiplicative set powers of gfp_mpoly[x[3, 3]*x[1, 4], x[1, 1]*x[2, 3]*x[3, 4] + x[1, 1]*x[3, 3]*x[2, 4] + x[2, 1]*x[3, 3]*x[1, 4], x[2, 3]*x[1, 4], x[1, 2]*x[2, 3]*x[3, 4] + x[1, 2]*x[3, 3]*x[2, 4] + x[3, 2]*x[2, 3]*x[1, 4], x[3, 2]*x[2, 4], x[1, 1]*x[3, 2]*x[2, 4] + x[2, 1]*x[1, 2]*x[3, 4] + x[2, 1]*x[3, 2]*x[1, 4], x[1, 2]*x[2, 4], x[2, 4], x[1, 4], x[2, 1]*x[3, 4], x[1, 1]*x[3, 4], x[3, 4], x[3, 2]*x[2, 3], x[1, 2]*x[3, 3], x[1, 2]*x[2, 3], x[2, 3], x[1, 1]*x[2, 3], x[2, 1]*x[3, 3], x[1, 1]*x[3, 3], x[3, 3], x[1, 2], x[2, 1]*x[1, 2], x[2, 1]*x[3, 2], x[1, 1]*x[3, 2], x[3, 2], x[2, 1], x[1, 1], 1]
```

When the matroid $M$ is connected, the diagonal torus of $\mathsf{PGL}(n)$ acts freely on $\mathsf{Gr}(M)$ and its quotient is the *realization space* $R(M)$ of $M$. There are two main differences between the coordinate rings $K[\mathsf{Gr}(M)]$ and $K[R(M)]$.

- To comupte $K[R(M)]$, we assume that $d+1$ columns $A = \{a_1,\ldots,a_{d+1}\}$ of the reference matrix $X$ are the unit vectors $e_1,\ldots,e_n$ and $e_1+ \cdots + e_n$. Note that every $d$ element subset of $A$ must be a basis of $M$. Disconnected matroids do not satisfy this property.
- The columns of the reference matrix $X$ may be treated as projective coordinates.

The coordinate ring of $R(M)$ is computed in the following function.

`matroid_realization_space`

— Function`matroid_realization_space(M::Matroid, A::GroundsetType, F::AbstractAlgebra.Ring=ZZ)`

Returns the data of the coordinate ring of the realization space of the matroid `M`

using matrix coordinates. The matroid `M`

should be a simple and connected matroid, say its rank is $d$, and ground set $[n]$. The vector `A`

is `rank(M)+1`

consists of $d+1$ elements (in order) of $[n]$ such that each $d$-element subset is a basis of $M$.

This function returns a pair `(X, W)`

where `X`

is the reduced $d×n$ matrix of variables, and the coordinate ring of the matroid realization space is `W`

.

**Examples**

```
julia> M = fano_matroid();
julia> (X, W) = matroid_realization_space(M, [1,2,4,7], GF(2));
julia> X # The coordinate matrix.
[1 0 x[1, 1] 0 x[1, 2] 0 1]
[0 1 1 0 0 x[2, 3] 1]
[0 0 0 1 1 1 1]
julia> W # The coordinate ring of the stratum.
Localization of Quotient of Multivariate Polynomial Ring in x[1, 1], x[1, 2], x[2, 3] over Galois field with characteristic 2 by ideal(x[2, 3] + 1, x[1, 2] + 1, x[1, 1] + 1, x[1, 1]*x[2, 3] + x[1, 2]) at the multiplicative set powers of gfp_mpoly[1, x[1, 1]*x[2, 3] + x[1, 1] + 1, x[2, 3], x[1, 2]*x[2, 3] + x[1, 2] + x[2, 3], x[1, 1] + x[1, 2] + 1, x[1, 2], x[1, 1], x[1, 2]*x[2, 3], x[1, 1]*x[2, 3]]
```