BigObject Matroid

from application matroid

A matroid on the set {0,…,n-1}. Here n is the same as N_ELEMENTS.

Permutations:

BasesPerm:

permuting the BASES

HyperplanePerm:

UNDOCUMENTED

More complex properties of the matroid.

---

AUTOMORPHISM_GROUP

The automorphism group of the matroid, operating on the ground set.

Type:

Group

Example:

Any two points in the fano plane may be exchanged, i.e. the group action on the groundset is transitive.

 > print fano_matroid()->AUTOMORPHISM_GROUP->PERMUTATION_ACTION->ORBITS;
 {0 1 2 3 4 5 6}

---

BETA_INVARIANT

The coefficient of x of the TUTTE_POLYNOMIAL.

Type:

Integer

Example:

The following computes the beta invariant of the fano matroid.

 > print fano_matroid()->BETA_INVARIANT;
 3

---

CATENARY_G_INVARIANT

This is an equivalent characterization of the G_INVARIANT given by Bonin and Kung ([Bonin, Kung: The G-invariant and catenary data of a matroid (2015)]). It lives in the free abelian group over all (n,r)-compositions (where n = N_ELEMENTS and r = RANK). Those are sequences (a0,…,ar) with a0 >= 0, a_j > 0 for j > 0 and sum a_i = n For each maximal chain of flats F0,…,Fr = E of M, the corresponding composition is a0 = |F0| and a_i = |Fi \ Fi-1| for i > 0. For a composition a, let v(M,a) be the number of maximal chains of flats with composition a. Then G(M) := sum_a v(M,a) * a, where the sum runs over all compositions a.

Type:

Map<Vector<Int>,Integer>

Example:

The folowing computes the catenary g invariant of the fano matroid.

 > print fano_matroid()->CATENARY_G_INVARIANT;
 {(<0 1 2 4> 21)}

---

CONNECTED

Whether the matroid is connected

Type:

Bool

Example:

The fano matroid is connected.

 > print fano_matroid()->CONNECTED;
 true

---

CONNECTED_COMPONENTS

The connected components

Type:

Array<Set<Int>>

Example:

Every edge of a star graph is a connected component in the sense of matroids (↔ 2-connected component in graphs).

 > print matroid_from_graph(graph::complete_bipartite(1,5))->CONNECTED_COMPONENTS;
 {0}
 {1}
 {2}
 {3}
 {4}

---

F_VECTOR

The f-vector of a matroid

Type:

Vector<Integer>

Example:

The following computes the f-vector of the Fano Matroid.

 > print fano_matroid()->F_VECTOR;
 7 21 28

---

G_INVARIANT

The G-invariant of the matroid (see [Derksen: Symmetric and quasi-symmetric functions associated to polymatroids, J. Algebr. Comb. 30 (2009), 43-86]) We use the formulation by Bonin and Kung in [Bonin, Kung: The G-invariant and catenary data of a matroid (2015)]: The G-invariant is an element of the free abelian group over all (n,r)-sequences (where n = N_ELEMENTS and r = RANK), i.e. 0/1-sequences (r_1,…,r_n), where exactly r entries are 1. We identify each such sequence with its support, i.e. the set of entries equal to 1, so the G-invariant can be represented as a map which takes an r-set to the coefficient of the corresponding (n,r)-sequence. The formal definition goes as follows: For each permutation p on n, we define a sequence r(p) = (r_1,…,r_n) by r_1 = rank({p(1)}) and r_j = rank( {p(1),…,p(j)}) - rank( {p(1),…,p(j-1)}). Then G(M) := sum_p r(p), where the sum runs over all permutations p.

Type:

Map<Set<Int>,Integer>

Example:

The folowing computes the G-invariant of the fano matroid.

 > print fano_matroid()->G_INVARIANT;
 {({0 1 2} 4032) ({0 1 3} 1008)}

---

H_VECTOR

The h-vector of a matroid

Type:

Vector<Integer>

Example:

The following computes the h-vector of the Fano Matroid.

 > print fano_matroid()->H_VECTOR;
 1 4 10 13

---

IDENTICALLY_SELF_DUAL

Whether the matroid is equal to its dual. Note that this does not check for isomorphy, if you want to check whether the matroid is isomorphic to its dual, ask for SELF_DUAL.

Type:

Bool

Example:

The Vámos matroid is not identically self dual.

 > print vamos_matroid()->IDENTICALLY_SELF_DUAL;
 false

---

LAMINAR

Whether the matroid is laminar. This is the case if and only if for any two circuits C1,C2 with non-empty intersection, their closures are comparable (i.e. one contains the other) see also [Fife, Oxley: Laminar matroids. arXiv: 1606.08354]

Type:

Bool

Example:

The fano matroid is not laminar. Any two lines in the fano plane correspond to circuits which are also flats. Neither line is a subset of the other.

 > print fano_matroid()->LAMINAR;
 false

---

LOOPS

Loops are one element dependent sets, i.e. they correspond to elements which are not included in any basis.

Type:

Set<Int>

Example:

All elements in the uniform matroid of rank 0 are loops.

 > print uniform_matroid(0,4)->LOOPS;
 {0 1 2 3}

---

MAXIMAL_TRANSVERSAL_PRESENTATION

If the matroid is transversal, this is the unique maximal presentation. I.e. the set system consists of RANK many sets and none of the sets can be increased without changing the matroid.

Type:

IncidenceMatrix<NonSymmetric>

Example:

The uniform matroid of rank 2 on 4 elements has a transversal representation.

 > print uniform_matroid(2,4)->MAXIMAL_TRANSVERSAL_PRESENTATION;
 {0 1 2 3}
 {0 1 2 3}

---

NESTED

Whether the matroid is nested, i.e., its LATTICE_OF_CYCLIC_FLATS forms a chain.

Type:

Bool

Example:

All uniform matroids are nested.

 > print uniform_matroid(2,4)->NESTED;
 true

---

N_CONNECTED_COMPONENTS

The number of CONNECTED_COMPONENTS

Type:

Int

Example:

Every edge of a star graph is a connected component in the sense of matroids (↔ 2-connected component in graphs).

 > print matroid_from_graph(graph::complete_bipartite(1,5))->N_CONNECTED_COMPONENTS;
 5

---

PAVING

Whether the matroid is paving, i.e. every circuit is at least as large as the matroid's rank.

Type:

Bool

Example:

All uniform matroids are paving.

 > print uniform_matroid(2,4)->PAVING;
 true

---

POLYTOPE

Polytope whose vertices are the characteristic vectors of the bases.

Type:

Polytope<Rational>

Example:

The polytope of the uniform matroid of rank 1 on 4 elements is the standard 3-simplex.

 > print uniform_matroid(1,4)->POLYTOPE->VERTICES;
 1 1 0 0 0
 1 0 1 0 0
 1 0 0 1 0
 1 0 0 0 1

---

REVLEX_BASIS_ENCODING

A string listing the bases in revlex order. A '*' means the basis is present, a '0' that it is absent

Type:

String

Example:

The uniform matroid contains all bases of the same order. The Fano Matroid only contains some of the bases.

 > print uniform_matroid(2,4)->REVLEX_BASIS_ENCODING;
 ******

 > print fano_matroid()->REVLEX_BASIS_ENCODING;
 ***0***0***0*****0**0*******0****0*

---

SELF_DUAL

Whether the matroid is isomorphic to its dual If you want to check whether it is actually equal (not just isomorphic), ask for IDENTICALLY_SELF_DUAL.

Type:

Bool

Example:

The Vámos matroid is self dual.

 > print vamos_matroid()->SELF_DUAL;
 true

---

SERIES_PARALLEL

Whether the matroid is series-parallel

Type:

Bool

Example:

Every cycle graph is series parallel.

 > print matroid_from_graph(graph::cycle_graph(5))->SERIES_PARALLEL;
 true

---

SIMPLE

Whether the matroid is simple.

Type:

Bool

Example:

The Fano Matroid is simple.

 > print fano_matroid()->SIMPLE;
 true

---

SPARSE_PAVING

Whether the matroid is sparse paving, i.e., both the matroid and its dual are paving.

Type:

Bool

Example:

The Fano Matroid is sparse paving.

 > print fano_matroid()->SPARSE_PAVING;
 true

---

SPLIT

Whether all SPLIT_FLACETS in the matroid are compatible.

Type:

Bool

---

SPLIT_FLACETS

The flats that correspond to split facets of the matroid POLYTOPE. The facets are either hypersimplex facets or splits

Type:

Array<Array<Set<Int>>>

---

TRANSVERSAL

Whether the m atroid is transversal, i.e., has a transversal presentation.

Type:

Bool

Example:

The uniform matroid of rank 2 on 4 elements is transversal.

 > print uniform_matroid(2,4)->TRANSVERSAL;
 true

---

TUTTE_POLYNOMIAL

The Tutte polynomial of a matroid. It is a polynomial in the two variables x and y, which are chosen such that the tutte polynomial of a single coloop is x and the tutte polynomial of a single loop is y.

Type:

Polynomial<Rational,Int>

Example:

The following computes the tutte polynomial of the fano matroid.

 > print fano_matroid()->TUTTE_POLYNOMIAL;
 x_0^3 + 4*x_0^2 + 7*x_0*x_1 + 3*x_0 + x_1^4 + 3*x_1^3 + 6*x_1^2 + 3*x_1

---

UNIFORM

Whether the matroid is a uniform matroid.

Type:

Bool

Example:

 > print uniform_matroid(2,4)->UNIFORM;
 true

---

These are properties that form (part of) an axiom system defining a matroid. Most of these can be used to create a matroid.

---

BASES

Subsets of the ground set which form the bases of the matroid. Note that if you want to define a matroid via its bases, you should also specify N_ELEMENTS, because we allow matroids with loops.

Type:

Array<Set<Int>>

Example:

polymake does not automatically check if the sets given actually form the bases of a matroid.

 > $B = new Array<Set>([[0,1],[0,2],[1,2]]);
 > print check_basis_exchange_axiom($B);
 true

 > $M = new Matroid(BASES=>$B, N_ELEMENTS=>3);
 > print $M->RANK;
 2

---

CIRCUITS

Circuits, i.e., minimally dependent sets.

Type:

Array<Set<Int>>

Example:

The four circuits of the matroid U(2,4).

 > print uniform_matroid(2,4)->CIRCUITS;
 {0 1 2}
 {0 1 3}
 {0 2 3}
 {1 2 3}

Example:

Matroids can be defined in terms of their circuits.

 > $M = new Matroid(CIRCUITS=>[[0,1,2,3]], N_ELEMENTS=>4);
 > print $M->BASES;
 {0 1 2}
 {0 1 3}
 {0 2 3}
 {1 2 3}

---

LATTICE_OF_CYCLIC_FLATS

The lattice of cyclic flats of the matroid. A flat is a cyclic flat, if and only if it is a union of circuits. Their ranks can also be read off of this property using nodes_of_dim(..)

Type:

Lattice<BasicDecoration,Sequential>

Example:

The nontrivial cyclic flats of the complete graph K5 correspond to complete subgraphs on three or four vertices.

 > $g = graph::complete(5);
 > $m = matroid_from_graph($g);
 > $m->LATTICE_OF_CYCLIC_FLATS->VISUAL;

---

LATTICE_OF_FLATS

The lattice of flats. This is a graph with all closed sets as nodes and inclusion relations as edges.

Type:

Lattice<BasicDecoration,Sequential>

Example:

The fano matroid's lattice of flats corresponds to the point-line incidence graph of the fano plane plus a top and bottom node.

 > $l = fano_matroid()->LATTICE_OF_FLATS;
 > $l->VISUAL;

---

MATROID_HYPERPLANES

Hyperplanes, i.e., flats of rank RANK-1.

Type:

Array<Set<Int>>

Example:

The fano matroid's hyperplanes correspond to the lines of the fano plane.

 > print fano_matroid()->MATROID_HYPERPLANES;
 {3 5 6}
 {2 4 6}
 {1 4 5}
 {1 2 3}
 {0 3 4}
 {0 2 5}
 {0 1 6}

Example:

Matroids can be defined in terms of their hyperplanes.

 > $M = new Matroid(MATROID_HYPERPLANES=>[[0],[1],[2],[3]], N_ELEMENTS=>4);
 > print $M->BASES;
 {0 1}
 {0 2}
 {0 3}
 {1 2}
 {1 3}
 {2 3}

---

NON_BASES

All subsets of the ground sets with cardinality RANK that are not BASES.

Type:

Array<Set<Int>>

Example:

Some matroids are more efficiently characterized by listing the non-bases.

 > $M = new Matroid(RANK=>2, N_ELEMENTS=>4, NON_BASES=>[]);

---

properties related to duality and dual properties.

---

DUAL

The dual matroid.

Type:

Matroid

---

These are properties of a matroid that count something.

---

N_AUTOMORPHISMS

The order of the AUTOMORPHISM_GROUP of the matroid.

Type:

Int

Example:

The automorphism group of the Fano matroid is SL(3,2) of order 168.

 > print fano_matroid()->N_AUTOMORPHISMS;
 168

---

N_BASES

The number of BASES.

Type:

Int

Example:

The bases of the Fano matroid correspond to the 28 nonlinear triples of points in the projective plane over GF2.

 > print fano_matroid()->N_BASES;
 28

---

N_CIRCUITS

The number of CIRCUITS.

Type:

Int

Example:

The circuits of the Fano matroid correspond to the seven lines in the the projective plane over GF2 and their complements.

 > print fano_matroid()->N_CIRCUITS;
 14

---

N_CYCLIC_FLATS

The number of cyclic flats, i.e. the number of nodes in LATTICE_OF_CYCLIC_FLATS.

Type:

Int

Example:

In the uniform matroid U(2,4) only the empty set and the entire set of all elements form cyclic flats.

 > print uniform_matroid(2,4)->N_CYCLIC_FLATS;
 2

---

N_ELEMENTS

Size of the ground set. The ground set itself always consists of the first integers starting with zero.

Type:

Int

Example:

The elements of the Fano matroid correspond to the seven points of the projective plane over GF2.

 > print fano_matroid()->N_ELEMENTS;
 7

---

N_FLATS

The number of flats, i.e. the number of nodes in LATTICE_OF_FLATS.

Type:

Int

Example:

The uniform matroid U(2,4) has six flats.

 > print uniform_matroid(2,4)->N_FLATS;
 6

---

N_LOOPS

The number of LOOPS.

Type:

Int

Example:

The uniform matroids do not have any loops.

 > print uniform_matroid(2,4)->N_LOOPS;
 0

---

N_MATROID_HYPERPLANES

The number of MATROID_HYPERPLANES

Type:

Int

Example:

Every one of the four elements of the uniform matroid U(2,4) yields a hyperplane.

 > print uniform_matroid(2,4)->N_MATROID_HYPERPLANES;
 4

---

RANK

Rank of the matroid, i.e., number of elements in each basis.

Type:

Int

Example:

The non-Fano matroid is realizable over any field, unless the chracteristic is 2.

 > print non_fano_matroid()->RANK;
 3

---

These are properties that can be used to define a matroid, but do not actually constitute an axiom system.

---

TRANSVERSAL_PRESENTATION

A transversal matroid can be defined via a multiset of subsets of the ground set (0,…,n-1) (i.e., N_ELEMENTS needs to be specified). The nodes of one parititon correspond to the subsets in the multiset. These nodes are adjacent to the elements specified inside their corresponding sets. Its bases are the maximal matchings of the bipartite incidence graph.

Type:

Array<Set<Int>>

Example:

A transveral presentation of the uniform matroid of rank 2 on 4 elements corresponds to a complete bipartite graph with partitions of size 2 and 4.

 > $m = new Matroid(N_ELEMENTS=>4, TRANSVERSAL_PRESENTATION=>[[0,1,2,3],[0,1,2,3]]);
 > print $m->RANK;
 2

 > print $m->UNIFORM;
 true

---

Functions related to the realizability over certain fields.

---

BINARY

Whether or not the matroid is representable over GF(2).

Type:

Bool

Example:

The uniform matroid of rank 2 on 4 elements is not binary.

 > print uniform_matroid(2,4)->BINARY;
 false

---

BINARY_VECTORS

If the matroid is realizable over the field GF(2) with two elements, this property may contain coordinates for some realization.

Type:

Matrix<Int,NonSymmetric>

Example:

The fano matroid is representable over GF(2). Its cannonical representation are the 7 nonzero vectors in the 3 dimensional vector space over GF(2).

 > print fano_matroid()->BINARY_VECTORS();
 1 1 1
 0 0 1
 0 1 0
 0 1 1
 1 0 0
 1 0 1
 1 1 0

---

REGULAR

Whether the matroid is representable over every field, that is the repesentation is unimodular. NOTE: the property my be 'undef' when polymake is unable to decide whether the matroid is regular.

Type:

Bool

Example:

The fano matroid is not representable over GF(3), hence it is not regular.

 > print fano_matroid()->REGULAR;
 false

---

TERNARY

Whether the matroid is representable over GF(3). NOTE: the property my be 'undef' when polymake is unable to decide whether the matroid is ternary.

Type:

Bool

Example:

The Vámos matroid is not representable over any field, so it is not ternary.

 > print vamos_matroid()->TERNARY;
 false

---

TERNARY_VECTORS

If the matroid is realizable over the field GF(3) with three elements, this property may contain coordinates for some realization.

Type:

Matrix<Int,NonSymmetric>

Example:

The matroid obtained from PG(2,3) is ternary. Its cannonical representation are the 13 points in PG(2,3).

 > print pg23_matroid()->TERNARY_VECTORS;
 1 0 0
 0 1 0
 1 1 0
 0 0 1
 1 -1 1
 1 -1 -1
 1 0 -1
 1 1 1
 0 1 -1
 1 0 1
 1 1 -1
 0 1 1
 1 -1 0

---

VECTORS

If the matroid is realizable over the rationals, this property contains coordinates for some realization. Specifying (rational) coordinates is one way to define a matroid. See also BINARY_VECTORS and TERNARY_VECTORS for realization over GF(2) and GF(3).

Type:

Matrix<Rational,NonSymmetric>

Example:

Every graphic matroid is realizable.

 > $g = graph::complete(4);
 > $m = matroid_from_graph($g);
 > print $m->VECTORS;
 1 0 0
 0 1 0
 1 1 0
 0 0 1
 1 0 1
 0 1 -1

---

Special purpose properties.

---

LABELS

Unique names assigned to the elements of the matroid. For a matroid built from scratch, you should create this property by yourself. the labels may be assigned for you in a meaningful way. If you build the matroid with a construction client, (e.g. matroid_from_graph) the labels may be assigned for you in a meaningful way.

Type:

Array<String>

Example:

The labels of a graphic matroid are the edges.

 > print matroid_from_graph(graph::cycle_graph(4))->LABELS;
 {1 0} {2 1} {3 0} {3 2}

---

More complex properties of the matroid.

---

COTRANSVERSAL

Whether the dual of the matroid is transversal, i.e. same as TRANSVERSAL

---

STRICT_GAMMOID

Alias for COTRANSVERSAL

---

is_isomorphic_to(Matroid M)

Parameters:

Matroid M

Returns:

Bool

---

These are methods that form (part of) an axiom system defining a matroid. Most of these can be used to create a matroid.

---

COCIRCUITS

---

COLOOPS

---

rank()

calculate the rank of a set with respect to a given matroid

Returns:

Int

---

These are methods of a matroid that count something.

---

N_COCIRCUITS

---

N_COLOOPS

---