# 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_basesMethod
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
source
matroid_from_nonbasesMethod
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| 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

source
matroid_from_circuitsMethod
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
source
matroid_from_hyperplanesMethod
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

source
matroid_from_matrix_columnsMethod
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
source
matroid_from_matrix_rowsMethod
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
source
cycle_matroidMethod
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
source
bond_matroidMethod
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
source
MatroidType
Matroid(pm_matroid::Polymake.BigObjectAllocated, [E::GroundsetType])

Construct a matroid from a polymake matroid M on the default ground set {1,...,n}.

source
matroid_from_revlex_basis_encodingMethod
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
source

## Examples

uniform_matroidMethod
uniform_matroid(r,n)

Construct the uniform matroid of rank r on the n elements {1,...,n}.

source
all_subsets_matroidMethod
all_subsets_matroid(r)

Construct the all-subsets-matroid of rank r, a.k.a. the matroid underlying the resonance arrangement or rank r.

source
projective_planeMethod
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

source
projective_geometryMethod
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

source
affine_geometryMethod
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
source

### Modifying matroids

dual_matroidMethod
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
source
direct_sumMethod
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
source
deletionMethod
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
source
restrictionMethod
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
source
contractionMethod
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
source
minorMethod
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 = ;

julia>  N = minor(M,S,T)
Matroid of rank 2 on 3 elements
source
principal_extensionMethod
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
source
free_extensionMethod
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
source
series_extensionMethod
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)
2-element Vector{Any}:
1
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
source
parallel_extensionMethod
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)
2-element Vector{Any}:
1
'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
source

## Properties

matroid_groundsetMethod
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
source
lengthMethod
length(M::Matroid)

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

Examples

julia> length(fano_matroid())
7
source
rankMethod
rank(M::Matroid)

Return the rank of the matroid M.

Examples

julia> rank(fano_matroid())
3
source
rankMethod
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
source
basesMethod
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]
source
nonbasesMethod
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]
source
circuitsMethod
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]
source
hyperplanesMethod
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]
source
flatsFunction
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}:
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> flats(M, 2)
7-element Vector{Vector}:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
source
cyclic_flatsFunction
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}:
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}:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 6]
[2, 5, 7]
[3, 5, 6]
[3, 4, 7]
source
closureMethod
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
source
nullityMethod
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
source
fundamental_circuitMethod
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
source
fundamental_cocircuitMethod
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
source
independent_setsMethod
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, 3]
[2, 3]
[1, 2]
source
spanning_setsMethod
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]
source
cobasesMethod
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}}:



source
cocircuitsMethod
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]
source
cohyperplanesMethod
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]
source
corankMethod
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
source
is_clutterMethod
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
source
is_regularMethod
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
source
is_binaryMethod
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
source
is_ternaryMethod
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
source
n_connected_componentsMethod
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
source
connected_componentsMethod
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}}:



source
is_connectedMethod
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
source
loopsMethod
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[]
source
coloopsMethod
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[]
source
is_looplessMethod
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
source
is_colooplessMethod
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
source
is_simpleMethod
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
source
direct_sum_componentsMethod
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
source
connectivity_functionMethod
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

source
is_vertical_k_separationMethod
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

source
is_k_separationMethod
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

source
vertical_connectivityMethod
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

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

Examples

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

source
tutte_connectivityMethod
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()

source
tutte_polynomialMethod
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

source
characteristic_polynomialMethod
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

source
reduced_characteristic_polynomialMethod
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

source
revlex_basis_encodingMethod
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
source
is_isomorphicMethod
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

source
is_minorMethod
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
source

### Chow Rings

chow_ringMethod
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*R
-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 + R - R
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> R = chow_ring(M, ring=GR);

julia> hilbert_series_reduced(R)
(t^2 + 4*t + 1, 1)

source

## 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_coordinatesFunction
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 Mand the submatrix with columns indexed byB' 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 by ideal with 4 generators
at products of 28 elements
source

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_spaceFunction
matroid_realization_space(M::Matroid, A::GroundsetType, F::AbstractAlgebra.Ring=ZZ)

Return 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 by ideal with 4 generators
at products of 9 elements
source
automorphism_groupMethod
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)
Group([ (3,4), (1,2), (2,3) ])
source