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

• 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:

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

---

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

---

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:

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

---

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

---

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

---

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

---