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.
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::Group
The 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::Bool
Whether 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::Bool
Whether 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::Bool
Whether the matroid is representable over every field, that is the repesentation is unimodular. NOTE: the property is 'undef' when it's hard to decide whether the matroid is ternary.
- REVLEX_BASIS_ENCODING: common::String
A string listing the bases in revlex order. A '*' means the basis is present, a '0' that it is absent
- SELF_DUAL: common::Bool
Whether 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::Bool
Whether 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::Bool
Whether 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 and inclusion relations as edges.
- 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::Int
The number of cyclic flats, i.e. the number of nodes in LATTICE_OF_CYCLIC_FLATS.
- N_ELEMENTS: common::Int
Size 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 built from scratch, you should create this property by yourself. the labels may be assigned for you in a meaningful way. If you build the matroid with a construction client, (e.g. matroid_from_graph) the labels may be assigned 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
- derived from: Matroid
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.
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::Vector
Defines 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::Matrix
Defines 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) → List
Checks 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 presentationExample:- 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
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 matroidOptions
Bool dual whether to construct the dual matroid insteadBool check_basis_exchange_axiom whether to perform the check of the axiom after constructionReturns
Array<Set> - 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<Set> bases the list of bases of the matroidInt r the rank of the matroidInt n the number of elements of the matroidReturns
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<Set> B a list of would-be bases of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of bases of a matroidReturns
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<Set> F a list of would-be flats of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of flats of a matroidReturns
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<Set> H a list of would-be hyperplanes of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of hyperplanes of a matroidReturns
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<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) → Bool
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 . 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 matroidArray<Set> C a list of flats to check if they form a modular cut in MOptions
Bool verbose print diagnostic message in case C is not a modular cut; default is trueReturns
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) → Matroid
The matroid obtained from a matroid m by contraction of set S .
Parameters
Matroid m Set<Int> S indices of elements to be contractedOptions
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 BASESReturns
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 contractedOptions
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 BASESReturns
Matroid - deletion (m, S) → Matroid
The matroid obtained from a matroid m by deletion of set S .
Parameters
Matroid m Set<Int> S indices of elements to be deletedOptions
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 BASESReturns
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 deletedOptions
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 BASESReturns
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 matroidReturns
ValuatedMatroid<Addition,Scalar> 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.
- higgs_lift (M) → Matroid
Computes 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) → Matroid
Calculate 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 MOptions
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 trueReturns
Matroid - parallel_extension (m, e) → Matroid
- principal_extension (M, F) → Matroid
Computes the principal extension of a matroid with respect to a flat.
- principal_lift (M, F) → Matroid
Computes 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 MReturns
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, Scalar> (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 MaxScalar Coordinate type to use, default is RationalParameters
Matroid M A matroidReturns
ValuatedMatroid<Addition, Scalar> 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
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.
- matroid_from_cyclic_flats (F, R, N) → Matroid
Computes 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 elementsReturns
Matroid matroid with the specified lattice of cylcic flats - matroid_from_graph (g) → Matroid
- matroid_from_matroid_polytope (p) → Matroid
Creates a matroid from the corresponding matroid polytope p.
- positroid_from_decorated_permutation (perm, loops) → Matroid
Producing 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 () → Matroid
Creates the Fano plane matroid of rank 3 with 7 elements. Representable over a field of characteristic two.
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
- 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
- o7_matroid () → 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
- projective_plane (p) → 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
- r8_matroid () → 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
- 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