documentation:master:matroid

Differences

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

Link to this comparison view

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.
 +    :: <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:​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<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]]''​
 +
 +
 +----
  
  • documentation/master/matroid.txt
  • Last modified: 2020/01/27 05:39
  • (external edit)