| |
| — | documentation:master:matroid [2023/11/04 05:42] (current) – created - external edit 127.0.0.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. |
| | :: <code perl> > @a = check_transversality(uniform_matroid(3,4)); |
| | > print $a[0]; |
| | true |
| | </code> |
| | :: <code perl> > print $a[1]; |
| | {0 1 2 3} |
| | {0 1 2 3} |
| | {0 1 2 3} |
| | </code> |
| | |
| | |
| | ---- |
| | {{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. |
| | :: <code perl> > $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 |
| | </code> |
| | :: <code perl> > $d2 = contraction($u, new Set([0,1])); |
| | > print join(",",$d2->list_properties()); |
| | N_ELEMENTS,BASES |
| | </code> |
| | ? **''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. |
| | :: <code perl> > $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 |
| | </code> |
| | :: <code perl> > $d2 = deletion($u, new Set([0,1])); |
| | > print join(",",$d2->list_properties()); |
| | N_ELEMENTS,BASES |
| | </code> |
| | ? **''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:random_matroid:}} |
| | ? **''random_matroid([[.:common#Int |Int]] n)''** |
| | :: Produces a random matroid, with //n// elements, using the algorithm proposed in Donald E. Knuth's paper RANDOM MATROIDS from 1975. |
| | ? Parameters: |
| | :: ''[[.:common#Int |Int]]'' ''n'': the number of elements |
| | ? Options: |
| | : |
| | :: ''[[.:common#Int |Int]]'' ''seed'': controls the outcome of the random number generator; |
| | ? 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_circuits_axiom:}} |
| | ? **''check_circuits_axiom([[.:common#Array |Array]]<[[.:common#Set |Set]]> C)''** |
| | :: Check if a given list of sets satisfies the axioms to be the circuits of a matroid. |
| | ? Parameters: |
| | :: ''[[.:common#Array |Array]]<[[.:common#Set |Set]]>'' ''C'': a list of would-be circuits of a matroid |
| | ? Options: |
| | : |
| | :: ''[[.:common#Bool |Bool]]'' ''verbose'': print a proof if the given sets do not form the set of circuits 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<j. |
| | ? Returns: |
| | :''[[.:common#Int |Int]]'' |
| | |
| | |
| | ---- |
| | {{anchor:is_modular_cut:}} |
| | ? **''is_modular_cut([[.:matroid:Matroid |Matroid]] M, [[.:common#Array |Array]]<[[.:common#Set |Set]]> 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]]'' |
| | |
| | |
| | ---- |
| |