Matroids

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(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(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(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(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_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(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(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

See bond_matroid.

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(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

uniform_matroid(r,n)

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

fano_matroid()

Construct the Fano matroid.

moebius_kantor_matroid()

Construct the Möbius-Kantor matroid.

non_fano_matroid()

Construct the non-Fano matroid.

non_pappus_matroid()

Construct the non-Pappus matroid.

pappus_matroid()

Construct the Pappus matroid.

perles_matroid()

Construct the Perles matroid.

R10_matroid()

Construct the R10 matroid.

vamos_matroid()

Construct the Vamos matroid.

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(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(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(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

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

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

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

Examples

julia> length(fano_matroid())
7

rank(M::Matroid)

Return the rank of the matroid M.

Examples

julia> rank(fano_matroid())
3

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([::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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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

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(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_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 [AHK18] and [BES19].

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(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);