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

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

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)
tutte_polynomial(M::Matroid; parent::ZZMPolyRing)
tutte_polynomial(parent::ZZMPolyRing, 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)
characteristic_polynomial(M::Matroid; parent::ZZPolyRing)
characteristic_polynomial(parent::ZZPolyRing, 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)
reduced_characteristic_polynomial(M::Matroid; parent::ZZPolyRing)
reduced_characteristic_polynomial(parent::ZZPolyRing, 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

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

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