# 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: common, graph
uses: group, ideal, polytope, topaz

## User Functions

•

### Advanced properties

More complex properties of the matroid.

•
check_transversality (M) → List

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

##### Parameters
 Matroid M
##### Returns
 List (Bool, Array >) First a bool indicating whether M is transversal If this is true, the second entry is a transversal presentation

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 (M) → Bool

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

##### Parameters
 Matroid M
##### Returns
 Bool Whether M is nested.
•

### Combinatorics

These functions capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

•
_4ti2Circuits (A) → Matrix

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
•

### Other

Special purpose functions.

•
bases_from_revlex_encoding (encoding, r, n) → Array<Set>

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
•
bases_to_revlex_encoding (bases, r, n) → String

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 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 (B) → Bool

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

##### Parameters
 Array 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 are the given sets the bases of a matroid?
•
check_flat_axiom (F) → Bool

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

##### Parameters
 Array 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 are the given sets the flats of a matroid?
•
check_hyperplane_axiom (H) → Bool

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

##### Parameters
 Array 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 are the given sets the hyperplanes of a matroid?
•
check_valuated_basis_axioms (bases, valuation) → Bool

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

##### Parameters
 Array > bases Vector > valuation
##### Options
 Bool verbose . Whether the function should output when some axiom is not fulfilled. False by default.
##### Returns
 Bool . Whether this is a basis valuation
•
check_valuated_circuit_axioms (M) → Bool

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

##### Parameters
 Matrix > M
##### Options
 Bool verbose . Whether the function should output when some axiom is not fulfilled. False by default.
##### Returns
 Bool . Whether the matrix is a circuit valuation
•
internal_activity () → Int

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 (M, C) → Bool

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

##### Parameters
 Matroid M the matroid Array 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 (m) → List

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

##### Parameters
 Matroid m
##### Returns
 List (Vector, Vector)
•
minimal_base (matroid, weights) → Set

Calculates a minimal weight basis.

##### Parameters
 Matroid matroid Vector weights for the elements of the matroid
##### Returns
 Set minimal weight basis
•

### Producing a matroid from matroids

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

•
contraction (m, S) → Matroid

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

##### Parameters
 Matroid m Set S indices of elements to be contracted
##### Options
 Array 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 (m, x) → Matroid

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 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 (m, S) → Matroid

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

##### Parameters
 Matroid m Set S indices of elements to be deleted
##### Options
 Array 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 (m, x) → Matroid

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 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 (m_1, m_2) → Matroid

The direct sum of matroids m1 and m2

##### Parameters
 Matroid m_1 Matroid m_2
##### Returns
 Matroid
•
dual (m) → Matroid

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 (M) → ValuatedMatroid<Addition,Scalar>

Computes the dual of a valuated matroid.

##### Parameters
 ValuatedMatroid M A valuated matroid
##### Returns
 ValuatedMatroid The dual valuated matroid.
•
free_extension (M) → Matroid

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 The free extension of M
•
higgs_lift (M) → Matroid

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 The Higgs lift L_E(M)
•
intersection (M) → Matroid

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 The intersection of all matroids in M
•
lex_extension (M, C) → Matroid

Calculate the lexicographic extension of a matroid in a modular cut

##### Parameters
 Matroid M the original matroid to be extended Array 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 (m_1, e_1, m_2, e_2) → Matroid

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 (m, e) → Matroid

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

##### Parameters
 Matroid m Int e
##### Returns
 Matroid
•
principal_extension (M, F) → Matroid

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

##### Parameters
 Matroid M A matroid Set F A set F, which is a flat of M
##### Returns
 Matroid The principal extension M +_F n. If M is a matroid on 0 .. n-1, then the principal extension has ground set 0 .. n. Its bases are the bases of M, plus the sets B-q+n, where B is a basis of M and q is in B and F.
•
principal_lift (M, F) → Matroid

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

##### Parameters
 Matroid M A matroid Set F A set F, which is a flat of M
##### Returns
 Matroid The principal lift L_F(M) = T_F(M*)*, where T_F is the principal_truncation and * denotes the dualizing operator
•
principal_truncation (M, F) → Matroid

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

##### Parameters
 Matroid M A matroid Set F A set F, which is a flat of M
##### Returns
 Matroid The truncation T_F(M), i.e. the matroid whose bases are all sets B-p, where B is a basis of M and p is in F and B.
•
series_extension (m_1, e_1, m_2, e_2) → Matroid

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 (m, e) → Matroid

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

##### Parameters
 Matroid m Int e
##### Returns
 Matroid
•
trivial_valuation <Addition> (M) → ValuatedMatroid<Addition,Scalar>

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
##### Parameters
 Matroid M A matroid
##### Returns
 ValuatedMatroid The matroid with a trivial valuation
•
truncation (M) → Matroid

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

##### Parameters
 Matroid M A matroid
##### Returns
 Matroid The truncation T(M)
•
two_sum (m_1, e_1, m_2, e_2) → Matroid

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

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 The union of all matroids in M
•

### Producing a matroid from other objects

These functions construct a new Matroid from other objects.

•
matroid_from_characteristic_vector (v, r, n) → Matroid

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

##### Parameters
 Vector v Int r Int n
##### Returns
 Matroid
•
matroid_from_cyclic_flats (F, R, N) → Matroid

Computes the face lattice of the given sets by inclusion.

##### Parameters
 Array> F faces of the lattice of cyclic flats Array> R ranks of the faces Int N number of elements
##### Returns
 Matroid matroid with the specified lattice of cylcic flats
•
matroid_from_graph (g) → Matroid

Creates a graphical matroid from a graph g.

##### Parameters
 graph::Graph g
##### Returns
 Matroid
•
matroid_from_matroid_polytope (p) → Matroid

Creates a matroid from the corresponding matroid polytope p.

##### Parameters
 polytope::Polytope p
##### Returns
 Matroid
•
positroid_from_decorated_permutation (perm, loops) → Matroid

Producing a positroid from a decorated permutation

##### Parameters
 Array perm a permutation Set 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 () → Matroid

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

##### Returns
 Matroid
•
ag32_matroid () → Matroid

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

##### Returns
 Matroid
•
ag32_prime_matroid () → Matroid

The unique relaxation of ag32_matroid.

##### Returns
 Matroid
•
f8_matroid () → Matroid

A minimal non-representable matroid. Non-algebraic.

##### Returns
 Matroid
•
fano_matroid () → Matroid

Creates the Fano plane matroid of rank 3 with 7 elements. Representable over a field of characteristic two.

##### Returns
 Matroid
•
j_matroid () → 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 () → 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 () → Matroid

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

##### Returns
 Matroid
•
n2_matroid () → Matroid

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

##### Returns
 Matroid
•
non_fano_matroid () → Matroid

The embedding into the reals of the seven points that define the Fano matroid. Representable if and only if the field has not characteristic 2.

##### Returns
 Matroid
•
non_p8_matroid () → Matroid

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

##### Returns
 Matroid
•
non_pappus_matroid () → 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 () → Matroid

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

##### Returns
 Matroid
•
o7_matroid () → Matroid

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

##### Returns
 Matroid
•
p7_matroid () → Matroid

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

##### Returns
 Matroid
•
p8_matroid () → 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 () → 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 () → Matroid

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

##### Returns
 Matroid
•
projective_plane (p) → Matroid

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

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

##### Returns
 Matroid
•
q8_matroid () → 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 () → Matroid

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

##### Returns
 Matroid
•
r8_matroid () → Matroid

The real affine cube.

##### Returns
 Matroid
•
r9a_matroid () → Matroid

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

##### Returns
 Matroid
•
r9b_matroid () → Matroid

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

##### Returns
 Matroid
•
special_matroid (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 matroidPossible values:'ag23'Configuration of the 9 points in the affine plane AG(2,3). 'ag32'Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube. 'ag32_prime'The unique relaxation of ag32_matroid. 'fano'The Fano matroid 'f8'A minimal non-representable matroid. Also non-algebraic. 'j'An excluded minor for some properties (see [Oxley:matroid theory (2nd ed.) page 650]). Not binary. Algebraic over all fields. 'l8'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. 'n1'An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]). 'n2'An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]). 'o7'The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields. 'p7'The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields. 'p8'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. 'non_p8'Obtained from p8_matroid by relaxing its only pair of disjoint circuit-hyperplanes. 'pappus'The Pappus matroid 'non_pappus'The non-Pappus matroid 'pg23'Configuration of the 13 points in the projective plane PG(2,3). 'q3_gf3_star'The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2. 'q8'A minimal non-representable matroid. An excluded minor for fields that are not of characteristic 2 or have 3 elements. Non-algebraic. 'r8'The real affine cube. 'r9a'Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html 'r9b'Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html 'r10'A regular matroid that's not graphical nor cographical. Algebraic over all fields. 't8'Representable if and only if the field has characteristic 3. An excluded minor for fields that are not of characteristic 2 or 3. 'vamos'The Vamos matroid 'non_vamos'The non-Vamos matroid 'wheel4'The 4-wheel 'non_fano'The non-Fano matroid
•
t8_matroid () → 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 (r, n) → Matroid

Creates the uniform matroid of rank r with n elements.

##### Parameters
 Int r Int n
##### Returns
 Matroid
•
vamos_matroid () → Matroid

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

##### Returns
 Matroid
•
wheel4_matroid () → Matroid

The rank-4 wheel.

##### Returns
 Matroid