# 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

**Objects**

A matroid on the set

*{0,...,n-1}*. Here*n*is the same as N_ELEMENTS.#### Properties of Matroid

**BASES**: common::Array<Set<Int>>Subsets of the ground set which form the bases of the matroid. Note that if you want to define a matroid via its bases, you should also specify N_ELEMENTS, because we allow matroids with loops.

**BINARY_VECTORS**: common::Matrix<Int, NonSymmetric>If the matroid is realizable over the field GF(2) with two elements, this property contains coordinates for some realization.

**COCIRCUITS**: common::Array<Set<Int>>Cocircuits (or bonds) of the matroid, i.e., minimal sets intersecting every basis.

**LABELS**: common::Array<String>Unique names assigned to the elements of the matroid.

For a matroid build from scratch, you should create this property by yourself. If you build the matroid with a construction client, (e.g. matroid_from_graph) the labels may be assigend for you in a meaningful way.

**LATTICE_OF_FLATS**: graph::FaceLatticeThe lattice of flats, this is a graph with all closed sets as nodes

**NON_BASES**: common::Array<Set<Int>>All subsets of the ground sets with cardinality RANK that are not bases.

**N_ELEMENTS**: common::IntSize of the ground set. The ground set itself always consists of the first integers starting with zero.

**POLYTOPE**: polytope::Polytope<Rational>Polytope whose vertices are the characteristic vectors of the bases.

**REGULAR**: common::BoolWhether the matroid is representable over every field, that is the repesentation is unimodular. NOTE: the property is 'undef' when its hard to decide, whether the matroid is ternary.

**REVLEX_BASIS_ENCODING**: common::StringA string listing the bases in revlex order. A '*' means the basis is present, a '0' that it is absent

**TERNARY**: common::BoolWhether the matroid is representable over GF(3) NOTE: the property is 'undef' when its hard to decide.

**TERNARY_VECTORS**: common::Matrix<Int, NonSymmetric>If the matroid is realizable over the field GF(3) with three elements, this property contains coordinates for some realization.

**VECTORS**: common::Matrix<Rational, NonSymmetric>If the matroid is realizable over the rationals, this property contains coordinates for some realization. Specifying coordinates is one way to define a matroid.

## User Functions

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

**internal_activity**() → Intcalculate 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 **_4ti2Circuits**(A) → Matrix

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 matroidInt r the rank of the matroidInt n the number of elements of the matroid##### Options

Bool dual whether to construct the dual matroid insteadBool check_basis_exchange_axiom whether to perform the check of the axiom after construction##### Returns

Array<Set> **bases_to_revlex_encoding**(bases, r, n) → StringEncode 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 matroidInt r the rank of the matroidInt n the number of elements of the matroid##### Returns

String **check_basis_exchange_axiom**(a) → IntCheck if a given list of sets satisfies the axioms to be the bases of a matroid.

##### Parameters

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

Int is_matroid are the given sets the bases of a matroid?**is_modular_cut**(M, C) → BoolCheck if a subset of the lattice of flats of a matroid is a modular cut

##### Parameters

Matroid M the matroidArray<Set> C a list of flats to check if they form a modular cut in M##### Returns

Bool **lex_extension**(M, C) → MatroidCalculate the lexicographic extension of a matroid in a modular cut

##### Parameters

Matroid M the original matroid to be extendedArray<Set> C a list of flats that form a modular cut in M##### Options

check_modular_cut whether to check if C in fact is a modular cut; default 1##### Returns

Matroid **matroid_plueckervector**(m) → ListReturnCreates the characteristic- and the rank-plueckervector of a matroid.

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

**contraction**(m, element) → Matroid**direct_sum**(m_1, m_2) → Matroid**parallel_extension**(m_1, e_1, m_2, e_2) → Matroid**parallel_extension**(m, e) → Matroid**series_extension**(m_1, e_1, m_2, e_2) → Matroid**series_extension**(m, e) → Matroid

These functions construct a new Matroid from other objects.

**matroid_from_characteristic_vector**(v, r, n) → MatroidCreates the matroid with a given characteristic plueckervector of rank

*r*and a ground set of*n*elements.**matroid_from_graph**(g) → Matroid**matroid_from_matroid_polytope**(p) → MatroidCreates a matroid from the corresponding matroid polytope

*p*.

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

**ag23_matroid**() → Matroid**ag32_matroid**() → Matroid**ag32_prime_matroid**() → Matroid**f8_matroid**() → Matroid**fano_matroid**() → MatroidCreates the Fano plane matroid of rank 3 with 7 elements.

Contained in extension`bundled:group`

.##### Returns

Matroid **l8_matroid**() → MatroidThe 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**() → MatroidAn excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

##### Returns

Matroid **n2_matroid**() → MatroidAn excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

##### Returns

Matroid **non_p8_matroid**() → Matroid**non_pappus_matroid**() → MatroidCreate 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**o7_matroid**() → Matroid**oxley_matroids**() → Array<Matroid>Produces many oxley matroids: ag23_matroid, ag32_matroid, ag32_prime_matroid, f8_matroid, j_matroid, l8_matroid, n1_matroid, n2_matroid, o7_matroid, p7_matroid, p8_matroid, non_p8_matroid, pappus_matroid, non_pappus_matroid, pg23_matroid, q3_gf3_star_matroid, q8_matroid, r8_matroid, r9a_matroid, r9b_matroid, r10_matroid, t8_matroid, vamos_matroid, non_vamos_matroid, wheel4_matroid

##### Returns

Array<Matroid> **p7_matroid**() → MatroidThe only other ternary 3-spike apart from the non-fano matroid. Non binary. Algebraic over all fields.

##### Returns

Matroid **p8_matroid**() → MatroidThe repesentaion over the reals is obtained from a 3-cube where one face is rotated by 45°. Non represetable if and only if the characeristic of the field is 2. Algebraic over all fields.

##### Returns

Matroid **pappus_matroid**() → MatroidCreate 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**projective_plane**(p) → Matroid**q3_gf3_star_matroid**() → Matroid**q8_matroid**() → MatroidA smallest non-represtable matroid. A excluded minor for fields that are not of characteristic 2 or have 3 elements. Non-algebraic.

##### Returns

Matroid **r10_matroid**() → Matroid**r8_matroid**() → Matroid**r9a_matroid**() → Matroid**r9b_matroid**() → Matroid**t8_matroid**() → MatroidReprestable if and only if the field has characteristic 3. A excluded minor for fields that are not of characteristic 2 or 3.

##### Returns

Matroid **uniform_matroid**(r, n) → Matroid**vamos_matroid**() → MatroidA smallest non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.

##### Returns

Matroid **wheel4_matroid**() → Matroid