application matroid

Matroids encode the concept of “(in)dependence” in an abstract way. You can define matroids via vector configurations or graphs, do basic conversions between different descriptions and perform basic operations such as deletions and contractions.

imports from:

application common
application graph

uses:

application group
application ideal
application polytope
application topaz

Objects

Matroid:
A matroid on the set {0,…,n-1}. Here n is the same as N_ELEMENTS.
ValuatedMatroid:
A valuated matroid. It is given by a matroid and some form of valuation, either on bases or circuits. It has two template parameters:

Functions

Advanced properties

More complex properties of the matroid.

check_transversality(Matroid M)

Checks whether a matroid is transversal. If so, returns one possible transversal presentation

Parameters:

Matroid M

Returns:

List

Example:

Computes whether the uniform matroid of rank 3 on 4 elements is transversal.

 > @a = check_transversality(uniform_matroid(3,4));
 > print $a[0];
 true

 > print $a[1];
 {0 1 2 3}
 {0 1 2 3}
 {0 1 2 3}

is_nested_matroid(Matroid M)

Checks whether a matroid is nested, i.e. its lattice of cyclic flats is a chain.

Parameters:: Matroid M
Returns:: Bool

Combinatorics

Combinatorial functions.

_4ti2Circuits(Matrix A)

Calculate the circuits of a set of points given as the rows of a Matrix A. The circuits are given as a matrix such that vA=0 for all rows v.

Parameters:: Matrix A: Matrix containing the points as rows.
Returns:: Matrix

Producing a matroid from matroids

These functions construct a new Matroid from other objects of the same type.

contraction(Matroid m, Set<Int> S)

The matroid obtained from a matroid m by contraction of set S .

Parameters:

Matroid m

Set<Int> S: indices of elements to be contracted

Options:

Array<String> computed_properties: This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES

Returns:

Matroid

Example:

This takes the uniform matroid of rank 2 on 3 elements and contracts the first two elements. It first only computes CIRCUITS and VECTORS, not BASES. The second computation only computes the bases.

 > $u = uniform_matroid(2,3);
 > $d = contraction( $u, (new Set([0,1])), computed_properties=>[qw(CIRCUITS VECTORS)]);
 > print join(",",$d->list_properties());
 N_ELEMENTS,CIRCUITS,VECTORS

 > $d2 = contraction($u, new Set([0,1]));
 > print join(",",$d2->list_properties());
 N_ELEMENTS,BASES

contraction(Matroid m, Int x)

The matroid obtained from a matroid m by contraction of element x .

Parameters:: Matroid m; Int x: index of element to be contracted
Options:: Array<String> computed_properties: This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
Returns:: Matroid

deletion(Matroid m, Set<Int> S)

The matroid obtained from a matroid m by deletion of set S .

Parameters:

Matroid m

Set<Int> S: indices of elements to be deleted

Options:

Returns:

Matroid

Example:

This takes the uniform matroid of rank 2 on 3 elements and deletes the first two elements. It first only computes CIRCUITS and VECTORS, not BASES. The second computation only computes the bases.

 > $u = uniform_matroid(2,3);
 > $d = deletion( $u, (new Set([0,1])), computed_properties=>[qw(CIRCUITS VECTORS)]);
 > print join(",",$d->list_properties());
 N_ELEMENTS,CIRCUITS,VECTORS

 > $d2 = deletion($u, new Set([0,1]));
 > print join(",",$d2->list_properties());
 N_ELEMENTS,BASES

deletion(Matroid m, Int x)

The matroid obtained from a matroid m by deletion of element x .

Parameters:: Matroid m; Int x: index of element to be deleted
Options:: Array<String> computed_properties: This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
Returns:: Matroid

direct_sum(Matroid m_1, Matroid m_2)

The direct sum of matroids m1 and m2

Parameters:: Matroid m_1; Matroid m_2
Returns:: Matroid

dual(Matroid m)

Produces the dual of a given matroid m. Not quite the same as calling m→DUAL. The latter returns a subobject and properties of this subobject are only computed upon demand. This function returns the dual as an independent object by computing its BASES.

Parameters:: Matroid m: “
Returns:: Matroid

dual(ValuatedMatroid<Addition,Scalar> M)

Computes the dual of a valuated matroid.

Parameters:: ValuatedMatroid<Addition,Scalar> M: A valuated matroid
Returns:: ValuatedMatroid<Addition,Scalar>

free_extension(Matroid M)

Computes the free extension of a matroid, i.e. the principal_extension, with F the full ground set.

Parameters:: Matroid M: A matroid
Returns:: Matroid

higgs_lift(Matroid M)

Computes the Higgs lift of a matroid, i.e. the principal_lift with respect to the full ground set.

Parameters:: Matroid M: A matroid.
Returns:: Matroid

intersection(Matroid M)

Computes the intersection of a list of matroids. Intersection is the dual of matroid union v, that is, the intersection of M and N is (M* v N*)*

Parameters:: Matroid M: A list of matroids, defined on the same ground set.
Returns:: Matroid

lex_extension(Matroid M, Array<Set> C)

Calculate the lexicographic extension of a matroid in a modular cut

Parameters:: Matroid M: the original matroid to be extended; Array<Set> C: a list of flats that form a modular cut in M
Options:: Bool check_modular_cut: whether to check if C in fact is a modular cut; default is true; Bool verbose: print diagnostic message in case C is not a modular cut; default is true
Returns:: Matroid

parallel_extension(Matroid m_1, Int e_1, Matroid m_2, Int e_2)

The parallel extension of matroids m1 and m2 with basepoints e1 and e2

Parameters:: Matroid m_1; Int e_1; Matroid m_2; Int e_2
Returns:: Matroid

parallel_extension(Matroid m, Int e)

The parallel extension of a matroid m and uniform(1,2) with basepoint e

Parameters:: Matroid m; Int e
Returns:: Matroid

principal_extension(Matroid M, Set<Int> F)

Computes the principal extension of a matroid with respect to a flat.

Parameters:: Matroid M: A matroid; Set<Int> F: A set F, which is a flat of M
Returns:: Matroid

principal_lift(Matroid M, Set<Int> F)

Computes the principal lift of a matroid with respect to a flat F

Parameters:: Matroid M: A matroid; Set<Int> F: A set F, which is a flat of M
Returns:: Matroid

principal_truncation(Matroid M, Set<Int> F)

Computes the principal truncation of a matroid with respect to a flat.

Parameters:: Matroid M: A matroid; Set<Int> F: A set F, which is a flat of M
Returns:: Matroid

series_extension(Matroid m_1, Int e_1, Matroid m_2, Int e_2)

The series extension of matroids m1 and m2 with basepoints e1 and e2

Parameters:: Matroid m_1; Int e_1; Matroid m_2; Int e_2
Returns:: Matroid

series_extension(Matroid m, Int e)

The series extension of a matroid m and uniform(1,2) with basepoint e

Parameters:: Matroid m; Int e
Returns:: Matroid

trivial_valuation<Addition, Scalar>(Matroid M)

This function takes a matroid and gives it the trivial valuation to produce a valuated matroid

Type Parameters:: Addition: The tropical addition to use, i.e. Min or Max; Scalar: Coordinate type to use, default is Rational
Parameters:: Matroid M: A matroid
Returns:: ValuatedMatroid<Addition,Scalar>

truncation(Matroid M)

Computes the truncation of M, i.e. the principal_truncation, with F the full ground set

Parameters:: Matroid M: A matroid
Returns:: Matroid

two_sum(Matroid m_1, Int e_1, Matroid m_2, Int e_2)

The 2-sum of matroids m1 and m2 with basepoints e1 and e2

Parameters:: Matroid m_1; Int e_1; Matroid m_2; Int e_2
Returns:: Matroid

union(Matroid M)

Computes the union of a list of matroids, i.e. the matroid whose independent sets are all unions of independent sets of the given matroids

Parameters:: Matroid M: A list of matroids, defined on the same ground set.
Returns:: Matroid

Producing a matroid from other objects

These functions construct a new Matroid from other objects.

matroid_from_characteristic_vector(Vector<Integer> v, Int r, Int n)

Creates the matroid with a given characteristic plueckervector of rank r and a ground set of n elements.

Parameters:: Vector<Integer> v; Int r; Int n
Returns:: Matroid

matroid_from_cyclic_flats(Array<Set<Int>> F, Array<Set<Int>> R, Int N)

Computes the face lattice of the given sets by inclusion.

Parameters:: Array<Set<Int>> F: faces of the lattice of cyclic flats; Array<Set<Int>> R: ranks of the faces; Int N: number of elements
Returns:: Matroid

matroid_from_graph(Graph g)

Creates a graphical matroid from a graph g.

Parameters:: Graph g
Returns:: Matroid

matroid_from_matroid_polytope(Polytope p)

Creates a matroid from the corresponding matroid polytope p.

Parameters:: Polytope p
Returns:: Matroid

positroid_from_decorated_permutation(Array<Int> perm, Set<Int> loops)

Producing a positroid from a decorated permutation

Parameters:: Array<Int> perm: a permutation; Set<Int> loops: the loops/decoration
Returns:: Matroid

Producing a matroid from scratch

With these clients you can create special examples of matroids belonging to parameterized families.

ag23_matroid()

Configuration of the 9 points in the affine plane AG(2,3).

Returns:: Matroid

ag32_matroid()

Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube.

Returns:: Matroid

ag32_prime_matroid()

The unique relaxation of ag32_matroid.

Returns:: Matroid

f8_matroid()

A minimal non-representable matroid. Non-algebraic.

Returns:: Matroid

fano_matroid()

Creates the Fano plane matroid of rank 3 with 7 elements. Representable over a field of characteristic two. The labeling of the elements corresponds to the binary encoding of 1,2,…,7 mod 7.

Returns:: Matroid

j_matroid()

An excluded minor for some properties (see [Oxley:matroid theory (2nd ed.) page 650]). Non binary. Algebraic over all fields.

Returns:: Matroid

l8_matroid()

The 4-point planes are the six faces of the cube an the two twisted plannes. Identically self-dual. Representable over all field with more then 4 elements and algebraic over all fields.

Returns:: Matroid

n1_matroid()

An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

Returns:: Matroid

n2_matroid()

An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

Returns:: Matroid

non_fano_matroid()

Representable if and only if the field has not characteristic 2. The labeling of the elements is similar to those of the Fano matroid.

Returns:: Matroid

non_p8_matroid()

Obtained from p8_matroid by relaxing its only pair of disjoint circuit-hyperplanes.

Returns:: Matroid

non_pappus_matroid()

Create the matroid encoding the violation of Pappus' Theorem. Not realizable over any field. An excluded minor for all finite fields with more than four elements. Algebraic over all field that do not have characteristic 0.

Returns:: Matroid

non_vamos_matroid()

A matroid related to the Vamos matroid (see [Oxley:matroid theory (2nd ed.) page 72])

Returns:: Matroid

o7_matroid()

The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields.

Returns:: Matroid

p7_matroid()

The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.

Returns:: Matroid

p8_matroid()

The repesentation over the reals is obtained from a 3-cube where one face is rotated by 45°. Non-representable if and only if the characeristic of the field is 2. Algebraic over all fields.

Returns:: Matroid

pappus_matroid()

Create the matroid corresponding to Pappus' Theorem. Realizable if and only if the size of the field is not 2,3 or 5. An excluded minor for the field with 5 elements.

Returns:: Matroid

pg23_matroid()

Configuration of the 13 points in the projective plane PG(2,3).

Returns:: Matroid

projective_plane(Integer p)

Creates the projective plane matroid of rank 3 with p^2+p+1 elements, where p is a prime.

Parameters:: Integer p
Returns:: Matroid

q3_gf3_star_matroid()

The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.

Returns:: Matroid

q8_matroid()

A minimal non-representable matroid. An excluded minor for fields that are not of characteristic 2 or have 3 elements. Non-algebraic.

Returns:: Matroid

r10_matroid()

A regular matroid that's not graphical nor cographical. Algebraic over all fields.

Returns:: Matroid

r8_matroid()

The real affine cube.

Returns:: Matroid

r9a_matroid()

Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

Returns:: Matroid

r9b_matroid()

Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

Returns:: Matroid

random_matroid(Int n)

Produces a random matroid, with n elements, using the algorithm proposed in Donald E. Knuth's paper RANDOM MATROIDS from 1975.

Parameters:: Int n: the number of elements
Options:: Int seed: controls the outcome of the random number generator;
Returns:: Matroid

special_matroid(String s)

This function can be used to ask for various special matroids, most of which occur in Oxley's book [Oxley: Matroid theory (2nd ed.)]. There is a separate function for each of these matroids.

Parameters:: String s: The name of the matroid

t8_matroid()

Representable if and only if the field has characteristic 3. An excluded minor for fields that are not of characteristic 2 or 3.

Returns:: Matroid

uniform_matroid(Int r, Int n)

Creates the uniform matroid of rank r with n elements.

Parameters:: Int r; Int n
Returns:: Matroid

vamos_matroid()

A minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.

Returns:: Matroid

wheel4_matroid()

The rank-4 wheel.

Returns:: Matroid

Other

Special purpose functions.

bases_from_revlex_encoding(String encoding, Int r, Int n)

Decode the bases of a given matroid from a string containing all possible binom(n,r) tuples of indices in revlex order. If the current tuple is a basis, a '*' is recorded, else a '0'.

Parameters:: String encoding: the revlex encoding of the list of bases of the matroid; Int r: the rank of the matroid; Int n: the number of elements of the matroid
Options:: Bool dual: whether to construct the dual matroid instead; Bool check_basis_exchange_axiom: whether to perform the check of the axiom after construction
Returns:: Array<Set>

bases_to_revlex_encoding(Array<Set> bases, Int r, Int n)

Encode the bases of a given matroid as a string. All possible binom(n,r) tuples of indices are traversed in revlex order. If the current tuple is a basis, a '*' is recorded, else a '0'.

Parameters:: Array<Set> bases: the list of bases of the matroid; Int r: the rank of the matroid; Int n: the number of elements of the matroid
Returns:: String

check_basis_exchange_axiom(Array<Set> B)

Check if a given list of sets satisfies the axioms to be the bases of a matroid.

Parameters:: Array<Set> B: a list of would-be bases of a matroid
Options:: Bool verbose: print a proof if the given sets do not form the set of bases of a matroid
Returns:: Bool

check_circuits_axiom(Array<Set> C)

Check if a given list of sets satisfies the axioms to be the circuits of a matroid.

Parameters:: Array<Set> C: a list of would-be circuits of a matroid
Options:: Bool verbose: print a proof if the given sets do not form the set of circuits of a matroid
Returns:: Bool

check_flat_axiom(Array<Set> F)

Check if a given list of sets satisfies the axioms to be the flats of a matroid.

Parameters:: Array<Set> F: a list of would-be flats of a matroid
Options:: Bool verbose: print a proof if the given sets do not form the set of flats of a matroid
Returns:: Bool

check_hyperplane_axiom(Array<Set> H)

Check if a given list of sets satisfies the axioms to be the hyperplanes of a matroid.

Parameters:: Array<Set> H: a list of would-be hyperplanes of a matroid
Options:: Bool verbose: print a proof if the given sets do not form the set of hyperplanes of a matroid
Returns:: Bool

check_valuated_basis_axioms(Array<Set<Int>> bases, Vector<TropicalNumber<Addition,Scalar>> valuation)

Takes a list of sets and a vector of valuations and checks if they fulfill the valuated basis axioms

Parameters:: Array<Set<Int>> bases; Vector<TropicalNumber<Addition,Scalar>> valuation
Options:: Bool verbose: . Whether the function should output when some axiom is not fulfilled. False by default.
Returns:: Bool

check_valuated_circuit_axioms(Matrix<TropicalNumber<Addition,Scalar>> M)

Takes a matrix of TropicalNumbers and checks if the rows fulfill the valuated circuit axioms

Parameters:: Matrix<TropicalNumber<Addition,Scalar>> M
Options:: Bool verbose: . Whether the function should output when some axiom is not fulfilled. False by default.
Returns:: Bool

internal_activity()

calculate the internal activity of a base with respect to a given ordering of all bases. Let the given base B = B_j be the j-th one in the given ordering B_1, B_2, … The internal activity of B_j is the number of “necessary” elements in B_j, i.e., the number of elements i in B_j such that B_j - {i} is not a subset of any B_k, k<j.

Returns:: Int

is_modular_cut(Matroid M, Array<Set> C)

Check if a subset of the lattice of flats of a matroid is a modular cut

Parameters:: Matroid M: the matroid; Array<Set> C: a list of flats to check if they form a modular cut in M
Options:: Bool verbose: print diagnostic message in case C is not a modular cut; default is true
Returns:: Bool

matroid_plueckervector(Matroid m)

Creates the characteristic- and the rank-plueckervector of a matroid.

Parameters:: Matroid m
Returns:: List

minimal_base(Matroid matroid, Vector weights)

Calculates a minimal weight basis.

Parameters:: Matroid matroid; Vector weights: for the elements of the matroid
Returns:: Set

Table of Contents

application matroid

Objects

Functions

Advanced properties

Combinatorics

Producing a matroid from matroids

Producing a matroid from other objects

Producing a matroid from scratch

Other