Available versions of this document: latest release, release 4.13, release 4.12, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master
Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2
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:
uses:
Objects
Matroid
:
A matroid on the set {0,…,n-1}. Here n is the same asN_ELEMENTS
.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.
-
check_transversality(Matroid M)
Checks whether a matroid is transversal. If so, returns one possible transversal presentation
-
is_nested_matroid(Matroid M)
Checks whether a matroid is nested, i.e. its lattice of cyclic flats is a chain.
- Parameters:
Matroid
M
- Returns:
Combinatorics
Combinatorial functions.
-
_4ti2Circuits(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:
Matrix
A
: Matrix containing the points as rows.- Returns:
Producing a matroid from matroids
These functions construct a new Matroid
from other objects of the same type.
-
contraction(Matroid m, Set<Int> S)
The matroid obtained from a matroid m by contraction of set S .
- Parameters:
Matroid
m
- Options:
- Returns:
- 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.
-
contraction(Matroid m, Int x)
The matroid obtained from a matroid m by contraction of element x .
-
deletion(Matroid m, Set<Int> S)
The matroid obtained from a matroid m by deletion of set S .
- Parameters:
Matroid
m
- Options:
- Returns:
- 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.
-
deletion(Matroid m, Int x)
The matroid obtained from a matroid m by deletion of element x .
-
dual(Matroid m)
Produces the dual of a given matroid m. Not quite the same as calling m→
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 itsBASES
.- Parameters:
Matroid
m
: “- Returns:
-
dual(ValuatedMatroid<Addition,Scalar> M)
Computes the dual of a valuated matroid.
- Parameters:
ValuatedMatroid<Addition,Scalar>
M
: A valuated matroid- Returns:
ValuatedMatroid<Addition,Scalar>
-
free_extension(Matroid M)
Computes the free extension of a matroid, i.e. the
principal_extension
, with F the full ground set.- Parameters:
Matroid
M
: A matroid- Returns:
-
higgs_lift(Matroid M)
Computes the Higgs lift of a matroid, i.e. the
principal_lift
with respect to the full ground set.- Parameters:
Matroid
M
: A matroid.- Returns:
-
intersection(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
M
: A list of matroids, defined on the same ground set.- Returns:
-
lex_extension(Matroid M, Array<Set> C)
Calculate the lexicographic extension of a matroid in a modular cut
-
parallel_extension(Matroid m_1, Int e_1, Matroid m_2, Int e_2)
The parallel extension of matroids m1 and m2 with basepoints e1 and e2
-
parallel_extension(Matroid m, Int e)
The parallel extension of a matroid m and uniform(1,2) with basepoint e
-
principal_extension(Matroid M, Set<Int> F)
Computes the principal extension of a matroid with respect to a flat.
- Parameters:
Matroid
M
: A matroid- Returns:
-
principal_lift(Matroid M, Set<Int> F)
Computes the principal lift of a matroid with respect to a flat F
- Parameters:
Matroid
M
: A matroid- Returns:
-
principal_truncation(Matroid M, Set<Int> F)
Computes the principal truncation of a matroid with respect to a flat.
- Parameters:
Matroid
M
: A matroid- Returns:
-
series_extension(Matroid m_1, Int e_1, Matroid m_2, Int e_2)
The series extension of matroids m1 and m2 with basepoints e1 and e2
-
series_extension(Matroid m, Int e)
The series extension of a matroid m and uniform(1,2) with basepoint e
-
trivial_valuation<Addition, Scalar>(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 MaxScalar
: Coordinate type to use, default isRational
- Parameters:
Matroid
M
: A matroid- Returns:
ValuatedMatroid<Addition,Scalar>
-
truncation(Matroid M)
Computes the truncation of M, i.e. the
principal_truncation
, with F the full ground set- Parameters:
Matroid
M
: A matroid- Returns:
-
two_sum(Matroid m_1, Int e_1, Matroid m_2, Int e_2)
The 2-sum of matroids m1 and m2 with basepoints e1 and e2
-
union(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
M
: A list of matroids, defined on the same ground set.- Returns:
Producing a matroid from other objects
These functions construct a new Matroid
from other objects.
-
matroid_from_characteristic_vector(Vector<Integer> v, Int r, Int n)
Creates the matroid with a given characteristic plueckervector of rank r and a ground set of n elements.
-
matroid_from_cyclic_flats(Array<Set<Int>> F, Array<Set<Int>> R, Int N)
Computes the face lattice of the given sets by inclusion.
- Parameters:
Int
N
: number of elements- Returns:
-
matroid_from_graph(Graph g)
Creates a graphical matroid from a graph g.
- Parameters:
Graph
g
- Returns:
-
matroid_from_matroid_polytope(Polytope p)
Creates a matroid from the corresponding matroid polytope p.
- Parameters:
Polytope
p
- Returns:
-
positroid_from_decorated_permutation(Array<Int> perm, Set<Int> loops)
Producing a positroid from a decorated permutation
- Parameters:
- Returns:
Producing a matroid from scratch
With these clients you can create special examples of matroids belonging to parameterized families.
-
ag23_matroid()
Configuration of the 9 points in the affine plane AG(2,3).
- Returns:
-
ag32_matroid()
Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube.
- Returns:
-
ag32_prime_matroid()
The unique relaxation of
ag32_matroid
.- Returns:
-
f8_matroid()
A minimal non-representable matroid. Non-algebraic.
- Returns:
-
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:
-
j_matroid()
An excluded minor for some properties (see [Oxley:matroid theory (2nd ed.) page 650]). Non binary. Algebraic over all fields.
- Returns:
-
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:
-
n1_matroid()
An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
- Returns:
-
n2_matroid()
An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
- Returns:
-
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:
-
non_p8_matroid()
Obtained from
p8_matroid
by relaxing its only pair of disjoint circuit-hyperplanes.- Returns:
-
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:
-
non_vamos_matroid()
A matroid related to the Vamos matroid (see [Oxley:matroid theory (2nd ed.) page 72])
- Returns:
-
o7_matroid()
The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields.
- Returns:
-
p7_matroid()
The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.
- Returns:
-
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:
-
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:
-
pg23_matroid()
Configuration of the 13 points in the projective plane PG(2,3).
- Returns:
-
projective_plane(Integer p)
Creates the projective plane matroid of rank 3 with p^2+p+1 elements, where p is a prime.
- Parameters:
Integer
p
- Returns:
-
q3_gf3_star_matroid()
The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.
- Returns:
-
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:
-
r10_matroid()
A regular matroid that's not graphical nor cographical. Algebraic over all fields.
- Returns:
-
r8_matroid()
The real affine cube.
- Returns:
-
r9a_matroid()
Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
- Returns:
-
r9b_matroid()
Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
- Returns:
-
special_matroid(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:
String
s
: The name of the 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:
-
vamos_matroid()
A minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.
- Returns:
-
wheel4_matroid()
The rank-4 wheel.
- Returns:
Other
Special purpose functions.
-
bases_from_revlex_encoding(String encoding, Int r, 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:
String
encoding
: the revlex encoding of the list of bases of the matroidInt
r
: the rank of the matroidInt
n
: the number of elements of the matroid- Options:
Bool
dual
: whether to construct the dual matroid insteadBool
check_basis_exchange_axiom
: whether to perform the check of the axiom after construction- Returns:
-
bases_to_revlex_encoding(Array<Set> bases, Int r, 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'.
-
check_basis_exchange_axiom(Array<Set> B)
Check if a given list of sets satisfies the axioms to be the bases of a matroid.
- Parameters:
- Options:
Bool
verbose
: print a proof if the given sets do not form the set of bases of a matroid- Returns:
-
check_circuits_axiom(Array<Set> C)
Check if a given list of sets satisfies the axioms to be the circuits of a matroid.
- Parameters:
- Options:
Bool
verbose
: print a proof if the given sets do not form the set of circuits of a matroid- Returns:
-
check_flat_axiom(Array<Set> F)
Check if a given list of sets satisfies the axioms to be the flats of a matroid.
- Parameters:
- Options:
Bool
verbose
: print a proof if the given sets do not form the set of flats of a matroid- Returns:
-
check_hyperplane_axiom(Array<Set> H)
Check if a given list of sets satisfies the axioms to be the hyperplanes of a matroid.
- Parameters:
- Options:
Bool
verbose
: print a proof if the given sets do not form the set of hyperplanes of a matroid- Returns:
-
check_valuated_basis_axioms(Array<Set<Int>> bases, Vector<TropicalNumber<Addition,Scalar>> valuation)
Takes a list of sets and a vector of valuations and checks if they fulfill the valuated basis axioms
- Parameters:
Vector<TropicalNumber<Addition,Scalar>>
valuation
- Options:
Bool
verbose
: . Whether the function should output when some axiom is not fulfilled. False by default.- Returns:
-
check_valuated_circuit_axioms(Matrix<TropicalNumber<Addition,Scalar>> M)
Takes a matrix of TropicalNumbers and checks if the rows fulfill the valuated circuit axioms
- Parameters:
Matrix<TropicalNumber<Addition,Scalar>>
M
- Options:
Bool
verbose
: . Whether the function should output when some axiom is not fulfilled. False by default.- Returns:
-
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:
-
is_modular_cut(Matroid M, Array<Set> C)
Check if a subset of the lattice of flats of a matroid is a modular cut
-
matroid_plueckervector(Matroid m)
Creates the characteristic- and the rank-plueckervector of a matroid.
- Parameters:
Matroid
m
- Returns: