documentation:master:matroid

# Differences

This shows you the differences between two versions of the page.

 — documentation:master:matroid [2020/01/27 05:39] (current) Line 1: Line 1: + ====== 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|common]] + * application [[.:​graph|graph]] + uses: + * application [[.:​group|group]] + * application [[.:​ideal|ideal]] + * application [[.:​polytope|polytope]] + * application [[.:​topaz|topaz]] + + ===== Objects ===== + ** ''​[[.:​matroid:​Matroid |Matroid]]'':​\\ ​ A matroid on the set //​{0,​...,​n-1}//​. ​ Here //n// is the same as ''​[[.:​matroid:​Matroid#​N_ELEMENTS |N_ELEMENTS]]''​. + ** ''​[[.:​matroid:​ValuatedMatroid |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: + + ===== Functions ===== + + ==== Advanced properties ==== + More complex properties of the matroid. + ---- + {{anchor:​check_transversality:​}} + ?  **''​check_transversality([[.:​matroid:​Matroid |Matroid]] M)''​** + :: Checks whether a matroid is transversal. If so, returns one possible transversal presentation + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M''​ + ? Returns: + :''​[[.:​common#​List |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} + ​ + + + ---- + {{anchor:​is_nested_matroid:​}} + ?  **''​is_nested_matroid([[.:​matroid:​Matroid |Matroid]] M)''​** + :: Checks whether a matroid is nested, i.e. its lattice of cyclic flats is a chain. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M''​ + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + + ==== Combinatorics ==== + ​Combinatorial functions. + ---- + {{anchor:​_4ti2circuits:​}} + ?  **''​_4ti2Circuits([[.:​common#​Matrix |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: + :: ''​[[.:​common#​Matrix |Matrix]]''​ ''​A'':​ Matrix containing the points as rows. + ? Returns: + :''​[[.:​common#​Matrix |Matrix]]''​ + + + ---- + + ==== Producing a matroid from matroids ==== + These functions construct a new ''​[[.:​matroid:​Matroid |Matroid]]''​ from other objects of the same type. + ---- + {{anchor:​contraction:​}} + ?  **''​contraction([[.:​matroid:​Matroid |Matroid]] m, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> S)''​** + :: The matroid obtained from a matroid //m// by __contraction__ of set //S// . + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​S'':​ indices of elements to be contracted + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |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:​Matroid |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:​Matroid |Matroid]] m, [[.:​common#​Int |Int]] x)''​** + :: The matroid obtained from a matroid //m// by __contraction__ of element //x// . + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​x'':​ index of element to be contracted + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​deletion:​}} + ? **''​deletion([[.:​matroid:​Matroid |Matroid]] m, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> S)''​** + :: The matroid obtained from a matroid //m// by __deletion__ of set //S// . + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​S'':​ indices of elements to be deleted + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |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:​Matroid |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:​Matroid |Matroid]] m, [[.:​common#​Int |Int]] x)''​** + :: The matroid obtained from a matroid //m// by __deletion__ of element //x// . + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​x'':​ index of element to be deleted + ? Options: + : + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​String |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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​direct_sum:​}} + ?  **''​direct_sum([[.:​matroid:​Matroid |Matroid]] m_1, [[.:​matroid:​Matroid |Matroid]] m_2)''​** + :: The direct sum of matroids m1 and m2 + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_1''​ + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_2''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​dual:​}} + ?  **''​dual([[.:​matroid:​Matroid |Matroid]] m)''​** + :: Produces the __dual__ of a given matroid //m//. Not quite the same as calling m->''​[[.:​matroid:​Matroid#​DUAL |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 ''​[[.:​matroid:​Matroid#​BASES |BASES]]''​. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m'':​ " + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + ?  **''​dual([[.:​matroid:​ValuatedMatroid |ValuatedMatroid]]<​Addition,​Scalar>​ M)''​** + :: Computes the dual of a valuated matroid. + ? Parameters: + :: ''​[[.:​matroid:​ValuatedMatroid |ValuatedMatroid]]<​Addition,​Scalar>''​ ''​M'':​ A valuated matroid + ? Returns: + :''​[[.:​matroid:​ValuatedMatroid |ValuatedMatroid]]<​Addition,​Scalar>''​ + + + ---- + {{anchor:​free_extension:​}} + ?  **''​free_extension([[.:​matroid:​Matroid |Matroid]] M)''​** + :: Computes the free extension of a matroid, i.e. the ''​[[.:​matroid#​principal_extension |principal_extension]]'',​ with F the full ground set. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​higgs_lift:​}} + ?  **''​higgs_lift([[.:​matroid:​Matroid |Matroid]] M)''​** + :: Computes the Higgs lift of a matroid, i.e. the ''​[[.:​matroid#​principal_lift |principal_lift]]''​ with respect to the full ground set. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​intersection:​}} + ?  **''​intersection([[.:​matroid:​Matroid |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:​Matroid |Matroid]]''​ ''​M'':​ A list of matroids, defined on the same ground set. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​lex_extension:​}} + ?  **''​lex_extension([[.:​matroid:​Matroid |Matroid]] M, [[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> C)''​** + :: Calculate the lexicographic extension of a matroid in a modular cut + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ the original matroid to be extended + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​C'':​ a list of flats that form a modular cut in M + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​check_modular_cut'':​ whether to check if C in fact is a modular cut; default is true + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print diagnostic message in case C is not a modular cut; default is true + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​parallel_extension:​}} + ?  **''​parallel_extension([[.:​matroid:​Matroid |Matroid]] m_1, [[.:​common#​Int |Int]] e_1, [[.:​matroid:​Matroid |Matroid]] m_2, [[.:​common#​Int |Int]] e_2)''​** + :: The parallel extension of matroids m1 and m2 with basepoints e1 and e2 + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_1''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_1''​ + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_2''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_2''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + ?  **''​parallel_extension([[.:​matroid:​Matroid |Matroid]] m, [[.:​common#​Int |Int]] e)''​** + :: The parallel extension of a matroid m and uniform(1,​2) with basepoint e + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​principal_extension:​}} + ?  **''​principal_extension([[.:​matroid:​Matroid |Matroid]] M, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> F)''​** + :: Computes the principal extension of a matroid with respect to a flat. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ A set F, which is a flat of M + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​principal_lift:​}} + ?  **''​principal_lift([[.:​matroid:​Matroid |Matroid]] M, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> F)''​** + :: Computes the principal lift of a matroid with respect to a flat F + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ A set F, which is a flat of M + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​principal_truncation:​}} + ?  **''​principal_truncation([[.:​matroid:​Matroid |Matroid]] M, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> F)''​** + :: Computes the principal truncation of a matroid with respect to a flat. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​F'':​ A set F, which is a flat of M + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​series_extension:​}} + ?  **''​series_extension([[.:​matroid:​Matroid |Matroid]] m_1, [[.:​common#​Int |Int]] e_1, [[.:​matroid:​Matroid |Matroid]] m_2, [[.:​common#​Int |Int]] e_2)''​** + :: The series extension of matroids m1 and m2 with basepoints e1 and e2 + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_1''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_1''​ + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_2''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_2''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + ?  **''​series_extension([[.:​matroid:​Matroid |Matroid]] m, [[.:​common#​Int |Int]] e)''​** + :: The series extension of a matroid m and uniform(1,​2) with basepoint e + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​trivial_valuation:​}} + ?  **''​trivial_valuation<​Addition,​ Scalar>​([[.:​matroid:​Matroid |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 ''​[[.:​common#​Rational |Rational]]''​ + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + ? Returns: + :''​[[.:​matroid:​ValuatedMatroid |ValuatedMatroid]]<​Addition,​Scalar>''​ + + + ---- + {{anchor:​truncation:​}} + ?  **''​truncation([[.:​matroid:​Matroid |Matroid]] M)''​** + :: Computes the truncation of M, i.e. the ''​[[.:​matroid#​principal_truncation |principal_truncation]]'',​ with F the full ground set + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ A matroid + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​two_sum:​}} + ?  **''​two_sum([[.:​matroid:​Matroid |Matroid]] m_1, [[.:​common#​Int |Int]] e_1, [[.:​matroid:​Matroid |Matroid]] m_2, [[.:​common#​Int |Int]] e_2)''​** + :: The 2-sum of matroids m1 and m2  with basepoints e1 and e2 + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_1''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_1''​ + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m_2''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​e_2''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​union:​}} + ?  **''​union([[.:​matroid:​Matroid |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:​Matroid |Matroid]]''​ ''​M'':​ A list of matroids, defined on the same ground set. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + + ==== Producing a matroid from other objects ==== + These functions construct a new ''​[[.:​matroid:​Matroid |Matroid]]''​ from other objects. + ---- + {{anchor:​matroid_from_characteristic_vector:​}} + ?  **''​matroid_from_characteristic_vector([[.:​common#​Vector |Vector]]<​[[.:​common#​Integer |Integer]]>​ v, [[.:​common#​Int |Int]] r, [[.:​common#​Int |Int]] n)''​** + :: Creates the matroid with a given characteristic plueckervector of rank //r// and a ground set of //n// elements. + ? Parameters: + :: ''​[[.:​common#​Vector |Vector]]<​[[.:​common#​Integer |Integer]]>''​ ''​v''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​r''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​matroid_from_cyclic_flats:​}} + ?  **''​matroid_from_cyclic_flats([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%% F, [[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%% R, [[.:​common#​Int |Int]] N)''​** + :: Computes the face lattice of the given sets by inclusion. + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​F'':​ faces of the lattice of cyclic flats + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​R'':​ ranks of the faces + :: ''​[[.:​common#​Int |Int]]''​ ''​N'':​ number of elements + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​matroid_from_graph:​}} + ?  **''​matroid_from_graph([[.:​graph:​Graph |Graph]] g)''​** + :: Creates a graphical matroid from a graph //g//. + ? Parameters: + :: ''​[[.:​graph:​Graph |Graph]]''​ ''​g''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​matroid_from_matroid_polytope:​}} + ?  **''​matroid_from_matroid_polytope([[.:​polytope:​Polytope |Polytope]] p)''​** + :: Creates a matroid from the corresponding matroid polytope //p//. + ? Parameters: + :: ''​[[.:​polytope:​Polytope |Polytope]]''​ ''​p''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​positroid_from_decorated_permutation:​}} + ?  **''​positroid_from_decorated_permutation([[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]> perm, [[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]> loops)''​** + :: Producing a positroid from a decorated permutation + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Int |Int]]>''​ ''​perm'':​ a permutation + :: ''​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]>''​ ''​loops'':​ the loops/​decoration + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + + ==== Producing a matroid from scratch ==== + With these clients you can create special examples of matroids belonging to parameterized families. + ---- + {{anchor:​ag23_matroid:​}} + ?  **''​ag23_matroid()''​** + :: Configuration of the 9 points in the affine plane AG(2,3). + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​ag32_matroid:​}} + ?  **''​ag32_matroid()''​** + :: Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​ag32_prime_matroid:​}} + ?  **''​ag32_prime_matroid()''​** + :: The unique relaxation of ''​[[.:​matroid#​ag32_matroid |ag32_matroid]]''​. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​f8_matroid:​}} + ?  **''​f8_matroid()''​** + :: A minimal non-representable matroid. Non-algebraic. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​fano_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​j_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​l8_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​n1_matroid:​}} + ?  **''​n1_matroid()''​** + :: An excluded minor for the dyadic matroids (see [Oxley:​matroid theory (2nd ed.) page 558]). + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​n2_matroid:​}} + ?  **''​n2_matroid()''​** + :: An excluded minor for the dyadic matroids (see [Oxley:​matroid theory (2nd ed.) page 558]). + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​non_fano_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​non_p8_matroid:​}} + ?  **''​non_p8_matroid()''​** + :: Obtained ​ from ''​[[.:​matroid#​p8_matroid |p8_matroid]]''​ by relaxing its only pair of disjoint circuit-hyperplanes.  ​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​non_pappus_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​non_vamos_matroid:​}} + ?  **''​non_vamos_matroid()''​** + :: A matroid related to the Vamos matroid (see [Oxley:​matroid theory (2nd ed.) page 72]) + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​o7_matroid:​}} + ?  **''​o7_matroid()''​** + :: The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​p7_matroid:​}} + ?  **''​p7_matroid()''​** + :: The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​p8_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​pappus_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​pg23_matroid:​}} + ?  **''​pg23_matroid()''​** + :: Configuration of the 13 points in the projective plane PG(2,3). + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​projective_plane:​}} + ?  **''​projective_plane([[.:​common#​Integer |Integer]] p)''​** + :: Creates the projective plane matroid of rank 3 with //p^2+p+1// elements, where p is a prime. + ? Parameters: + :: ''​[[.:​common#​Integer |Integer]]''​ ''​p''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​q3_gf3_star_matroid:​}} + ?  **''​q3_gf3_star_matroid()''​** + :: The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​q8_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​r10_matroid:​}} + ?  **''​r10_matroid()''​** + :: A regular matroid that's not graphical nor cographical. Algebraic over all fields. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​r8_matroid:​}} + ?  **''​r8_matroid()''​** + :: The real affine cube. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​r9a_matroid:​}} + ?  **''​r9a_matroid()''​** + :: Not representable over any field. Taken from http://​doc.sagemath.org/​html/​en/​reference/​matroids/​sage/​matroids/​catalog.html + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​r9b_matroid:​}} + ?  **''​r9b_matroid()''​** + :: Not representable over any field. Taken from http://​doc.sagemath.org/​html/​en/​reference/​matroids/​sage/​matroids/​catalog.html + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​special_matroid:​}} + ?  **''​special_matroid([[.:​common#​String |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: + :: ''​[[.:​common#​String |String]]''​ ''​s'':​ The name of the matroid + + + ---- + {{anchor:​t8_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:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​uniform_matroid:​}} + ?  **''​uniform_matroid([[.:​common#​Int |Int]] r, [[.:​common#​Int |Int]] n)''​** + :: Creates the uniform matroid of rank //r// with //n// elements. + ? Parameters: + :: ''​[[.:​common#​Int |Int]]''​ ''​r''​ + :: ''​[[.:​common#​Int |Int]]''​ ''​n''​ + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​vamos_matroid:​}} + ?  **''​vamos_matroid()''​** + :: A minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + {{anchor:​wheel4_matroid:​}} + ?  **''​wheel4_matroid()''​** + :: The rank-4 wheel. + ? Returns: + :''​[[.:​matroid:​Matroid |Matroid]]''​ + + + ---- + + ==== Other ==== + ​Special purpose functions. + ---- + {{anchor:​bases_from_revlex_encoding:​}} + ?  **''​bases_from_revlex_encoding([[.:​common#​String |String]] encoding, [[.:​common#​Int |Int]] r, [[.:​common#​Int |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: + :: ''​[[.:​common#​String |String]]''​ ''​encoding'':​ the revlex encoding of the list of bases of the matroid + :: ''​[[.:​common#​Int |Int]]''​ ''​r'':​ the rank of the matroid + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of elements of the matroid + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​dual'':​ whether to construct the dual matroid instead + :: ''​[[.:​common#​Bool |Bool]]''​ ''​check_basis_exchange_axiom'':​ whether to perform the check of the axiom after construction + ? Returns: + :''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ + + + ---- + {{anchor:​bases_to_revlex_encoding:​}} + ?  **''​bases_to_revlex_encoding([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> bases, [[.:​common#​Int |Int]] r, [[.:​common#​Int |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: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​bases'':​ the list of bases of the matroid + :: ''​[[.:​common#​Int |Int]]''​ ''​r'':​ the rank of the matroid + :: ''​[[.:​common#​Int |Int]]''​ ''​n'':​ the number of elements of the matroid + ? Returns: + :''​[[.:​common#​String |String]]''​ + + + ---- + {{anchor:​check_basis_exchange_axiom:​}} + ?  **''​check_basis_exchange_axiom([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> B)''​** + :: Check if a given list of sets satisfies the axioms to be the bases of a matroid. + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​B'':​ a list of would-be bases of a matroid + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print a proof if the given sets do not form the set of bases of a matroid + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​check_flat_axiom:​}} + ?  **''​check_flat_axiom([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> F)''​** + :: Check if a given list of sets satisfies the axioms to be the flats of a matroid. + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​F'':​ a list of would-be flats of a matroid + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print a proof if the given sets do not form the set of flats of a matroid + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​check_hyperplane_axiom:​}} + ?  **''​check_hyperplane_axiom([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]> H)''​** + :: Check if a given list of sets satisfies the axioms to be the hyperplanes of a matroid. + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​H'':​ a list of would-be hyperplanes of a matroid + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print a proof if the given sets do not form the set of hyperplanes of a matroid + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​check_valuated_basis_axioms:​}} + ?  **''​check_valuated_basis_axioms([[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%% bases, [[.:​common#​Vector |Vector]]<​[[.:​common#​TropicalNumber |TropicalNumber]]<​Addition,​Scalar%%>>​%% valuation)''​** + :: Takes a list of sets and a vector of valuations and checks if they fulfill the valuated basis axioms + ? Parameters: + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]<​[[.:​common#​Int |Int]]%%>>​%%''​ ''​bases''​ + :: ''​[[.:​common#​Vector |Vector]]<​[[.:​common#​TropicalNumber |TropicalNumber]]<​Addition,​Scalar%%>>​%%''​ ''​valuation''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ . Whether the function should output when some axiom is not fulfilled. False by default. + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​check_valuated_circuit_axioms:​}} + ?  **''​check_valuated_circuit_axioms([[.:​common#​Matrix |Matrix]]<​[[.:​common#​TropicalNumber |TropicalNumber]]<​Addition,​Scalar%%>>​%% M)''​** + :: Takes a matrix of TropicalNumbers and checks if the rows fulfill the valuated circuit axioms + ? Parameters: + :: ''​[[.:​common#​Matrix |Matrix]]<​[[.:​common#​TropicalNumber |TropicalNumber]]<​Addition,​Scalar%%>>​%%''​ ''​M''​ + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ . Whether the function should output when some axiom is not fulfilled. False by default. + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​internal_activity:​}} + ?  **''​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 C)''​** + :: Check if a subset of the lattice of flats of a matroid is a modular cut + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​M'':​ the matroid + :: ''​[[.:​common#​Array |Array]]<​[[.:​common#​Set |Set]]>''​ ''​C'':​ a list of flats to check if they form a modular cut in M + ? Options: + : + :: ''​[[.:​common#​Bool |Bool]]''​ ''​verbose'':​ print diagnostic message in case C is not a modular cut; default is true + ? Returns: + :''​[[.:​common#​Bool |Bool]]''​ + + + ---- + {{anchor:​matroid_plueckervector:​}} + ?  **''​matroid_plueckervector([[.:​matroid:​Matroid |Matroid]] m)''​** + :: Creates the characteristic- and the rank-plueckervector of a matroid. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​m''​ + ? Returns: + :''​[[.:​common#​List |List]]''​ + + + ---- + {{anchor:​minimal_base:​}} + ?  **''​minimal_base([[.:​matroid:​Matroid |Matroid]] matroid, [[.:​common#​Vector |Vector]] weights)''​** + :: Calculates a minimal weight basis. + ? Parameters: + :: ''​[[.:​matroid:​Matroid |Matroid]]''​ ''​matroid''​ + :: ''​[[.:​common#​Vector |Vector]]''​ ''​weights'':​ for the elements of the matroid + ? Returns: + :''​[[.:​common#​Set |Set]]''​ + + + ----
• documentation/master/matroid.txt