# 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

More complex properties of the matroid.

**AUTOMORPHISM_GROUP**: group::GroupThe automorphism group of the matroid, operating on the ground set.

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

**CATENARY_G_INVARIANT**: common::Map<Vector<Int>, Integer>This is an equivalent characterization of the G_INVARIANT given by Bonin and Kung ([Bonin, Kung: The G-invariant and catenary data of a matroid (2015)]). It lives in the free abelian group over all (n,r)-compositions (where n = N_ELEMENTS and r = RANK). Those are sequences (a0,...,ar) with a0 >= 0, a_j > 0 for j > 0 and sum a_i = n For each maximal chain of flats F0,...,Fr = E of M, the corresponding composition is a0 = |F0| and a_i = |Fi \ Fi-1| for i > 0. For a composition a, let v(M,a) be the number of maximal chains of flats with composition a. Then G(M) := sum_a v(M,a) * a, where the sum runs over all compositions a.

**G_INVARIANT**: common::Map<Set<Int>, Integer>The G-invariant of the matroid (see [Derksen: Symmetric and quasi-symmetric functions associated to polymatroids, J. Algebr. Comb. 30 (2009), 43-86]) We use the formulation by Bonin and Kung in [Bonin, Kung: The G-invariant and catenary data of a matroid (2015)]: The G-invariant is an element of the free abelian group over all (n,r)-sequences (where n = N_ELEMENTS and r = RANK), i.e. 0/1-sequences (r_1,...,r_n), where exactly r entries are 1. We identify each such sequence with its support, i.e. the set of entries equal to 1, so the G-invariant can be represented as a map which takes an r-set to the coefficient of the corresponding (n,r)-sequence. The formal definition goes as follows: For each permutation p on n, we define a sequence r(p) = (r_1,...,r_n) by r_1 = rank({p(1)}) and r_j = rank( {p(1),...,p(j)}) - rank( {p(1),...,p(j-1)}). Then G(M) := sum_p r(p), where the sum runs over all permutations p.

**IDENTICALLY_SELF_DUAL**: common::BoolWhether the matroid is equal to its dual. Note that this does not check for isomorphy, if you want to check whether the matroid is isomorphic to its dual, ask for SELF_DUAL.

**LAMINAR**: common::BoolWhether the matroid is laminar. This is the case if and only if for any two circuits C1,C2 with non-empty intersection, their closures are comparable (i.e. one contains the other) see also [Fife, Oxley: Laminar matroids. arXiv: 1606.08354]

**MAXIMAL_TRANSVERSAL_PRESENTATION**: common::IncidenceMatrix<NonSymmetric>If the matroid is transversal, this is the unique maximal presentation. I.e. the set system consists of RANK many sets and none of the sets can be increased without changing the matroid.

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

**SELF_DUAL**: common::BoolWhether the matroid is isomorphic to its dual If you want to check whether it is actually equal (not just isomorphic), ask for IDENTICALLY_SELF_DUAL.

**SPARSE_PAVING**: common::BoolWhether the matroid is sparse_paving, i.e both the matroid and it's dual are paving

**SPLIT_FLACETS**: common::Array<Array<Set<Int>>>The flats that correspond to split facets of the matroid POLYTOPE. The facets are either hypersimplex facets or splits

**TERNARY**: common::BoolWhether the matroid is representable over GF(3) NOTE: the property may be 'undef' if the current implementation cannot 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.

**TUTTE_POLYNOMIAL**: common::Polynomial<Rational, Int>The Tutte polynomial of a matroid. It is a polynomial in the two variables x and y, which are chosen such that the tutte polynomial of a single coloop is x and the tutte polynomial of a single loop is y.

These are properties that form (part of) an axiom system defining a matroid. Most of these can be used to create a 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.

**LATTICE_OF_CYCLIC_FLATS**: graph::Lattice<BasicDecoration, Sequential>The lattice of cyclic flats of the matroid. A flat is a cyclic flat, if and only if it is a union of circuits. Their ranks can also be read off of this property using nodes_of_dim(..)

**LATTICE_OF_FLATS**: graph::Lattice<BasicDecoration, Sequential>The 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.

These are properties of a matroid that count something.

**N_CYCLIC_FLATS**: common::IntThe number of cyclic flats, i.e. the number of nodes in LATTICE_OF_CYCLIC_FLATS.

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

These are properties that can be used to define a matroid, but do not actually constitute an axiom system.

**TRANSVERSAL_PRESENTATION**: common::Array<Set<Int>>A transversal matroid can be defined via a multiset of subsets of the ground set (0,...,n-1) (i.e. N_ELEMENTS needs to be specified). Its bases are the maximal matchings of the bipartite incidence graph.

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

Special purpose properties.

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

#### User Methods of Matroid

More complex properties of the matroid.

**COTRANSVERSAL**()Whether the dual of the matroid is transversal, i.e. same as DUAL.TRANSVERSAL

**is_isomorphic_to**(M) → Bool**STRICT_GAMMOID**()Alias for COTRANSVERSAL

These are methods that form (part of) an axiom system defining a matroid. Most of these can be used to create a matroid.

**COCIRCUITS**()UNDOCUMENTED**COLOOPS**()UNDOCUMENTED

These are methods of a matroid that count something.

**N_COCIRCUITS**()UNDOCUMENTED**N_COLOOPS**()UNDOCUMENTED

#### Permutations of Matroid

**HyperplanePerm**UNDOCUMENTED

A valuated matroid. It is given by a matroid and some form of valuation, either on bases or circuits. It has two template parameters: Addition: Either Min or Max. Has no default. Scalar: An ordered group in which the valuation lives, Rational by default.

**derived from:**Matroid#### Properties of ValuatedMatroid

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

**SUBDIVISION**: common::Array<Set<Int>>This is the matroid subdivision of POLYTOPE according to the lifting defined by VALUATION_ON_BASES (or minus VALUATION_ON_BASES in the case of max).

properties related to the valuation of the matroid.

**VALUATION_ON_BASES**: common::VectorDefines a valuation on each basis. Entry number i is a valuation on the i-th element of BASES. Must fulfill the tropical Plücker relations.

**VALUATION_ON_CIRCUITS**: common::MatrixDefines a valuation on each circuit. Row i is a representative of the i-th element of CIRCUITS. Must fulfill the tropical circuit valuation axioms. The representative is normalized such that the first non-tropical-zero entry is 0.

## User Functions

More complex properties of the matroid.

**check_transversality**(M) → ListChecks whether a matroid is transversal. If so, returns one possible transversal presentation

##### Parameters

Matroid M ##### Returns

List (Bool, Array<Set<Int> >) 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];`

`1`

`> print $a[1];`

`{0 1 2 3}`

`{0 1 2 3}`

`{0 1 2 3}`

**is_nested_matroid**(M) → Bool

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

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

Int is_matroid are the given sets the bases of a matroid?**check_flat_axiom**(F) → IntCheck 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

Int are_flats are the given sets the flats of a matroid?**check_hyperplane_axiom**(H) → IntCheck 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

Int are_hyperplanes are the given sets the hyperplanes of a matroid?**check_valuated_basis_axioms**(bases, valuation) → BoolTakes 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 . Whether this is a basis valuation**check_valuated_circuit_axioms**(M) → BoolTakes 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 . Whether the matrix is a circuit valuation**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 **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##### Options

Bool verbose print diagnostic message in case C is not a modular cut; default is true##### Returns

Bool **matroid_plueckervector**(m) → List**minimal_base**(matroid, weights) → Set

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

**contraction**(m, S) → MatroidThe 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**(m, x) → MatroidThe 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**(m, S) → MatroidThe 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**(m, x) → MatroidThe 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 *m*. If none is given, the default is BASES##### Returns

Matroid **direct_sum**(m_1, m_2) → Matroid**dual**(m) → Matroid**dual**(M) → ValuatedMatroid<Addition,Scalar>Computes the dual of a valuated matroid.

##### Parameters

ValuatedMatroid<Addition,Scalar> M A valuated matroid##### Returns

ValuatedMatroid<Addition,Scalar> The dual valuated matroid.**free_extension**(M) → MatroidComputes the free extension of a matroid, i.e. the principal_extension, with F the full ground set.

**higgs_lift**(M) → MatroidComputes the Higgs lift of a matroid, i.e. the principal_lift with respect to the full ground set.

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

Bool check_modular_cut whether to check if C in fact is a modular cut; default is trueBool verbose print diagnostic message in case C is not a modular cut; default is true##### Returns

Matroid **parallel_extension**(m, e) → Matroid**principal_extension**(M, F) → MatroidComputes the principal extension of a matroid with respect to a flat.

**principal_lift**(M, F) → MatroidComputes the principal lift of a matroid with respect to a flat F

##### Parameters

Matroid M A matroidSet<Int> 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**series_extension**(m, e) → 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<Addition,Scalar> The matroid with a trivial valuation**truncation**(M) → MatroidComputes the truncation of M, i.e. the principal_truncation, with F the full ground set

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_cyclic_flats**(F, R, N) → MatroidComputes the face lattice of the given sets by inclusion.

##### Parameters

Array<Set<int>> F faces of the lattice of cyclic flatsArray<Set<int>> R ranks of the facesInt N number of elements##### Returns

Matroid matroid with the specified lattice of cylcic flats**matroid_from_graph**(g) → Matroid**matroid_from_matroid_polytope**(p) → MatroidCreates a matroid from the corresponding matroid polytope

*p*.**positroid_from_decorated_permutation**(perm, loops) → MatroidProducing a positroid from a decorated permutation

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. Representable over a field of characteristic two.

##### 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_fano_matroid**() → MatroidThe 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**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**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 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**() → 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**() → MatroidThe rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.

##### Returns

Matroid **q8_matroid**() → MatroidA 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**r8_matroid**() → Matroid**r9a_matroid**() → MatroidNot representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

##### Returns

Matroid **r9b_matroid**() → MatroidNot 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'
- '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**() → MatroidRepresentable 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**vamos_matroid**() → MatroidA minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.

##### Returns

Matroid **wheel4_matroid**() → Matroid