[[application: matroid]]

# 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: common
uses: graph, polytope, topaz, tropical

## Objects

- ###
  Matroid

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

  #### Properties of Matroid

  - BASES: common::Array<Set<Int>>

    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.

  - CIRCUITS: common::Array<Set<Int>>

    Circuits, i.e., minimal dependent sets.

  - COCIRCUITS: common::Array<Set<Int>>

    Cocircuits (or bonds) of the matroid, i.e., minimal sets intersecting every basis.

  - LABELS: common::Array<String>

    Unique names assigned to the elements of the matroid.

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

  - NON_BASES: common::Array<Set<Int>>

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

  - N_BASES: common::Int

    The number of BASES.

  - N_CIRCUITS: common::Int

    The number of CIRCUITS.

  - N_COCIRCUITS: common::Int

    The number of COCIRCUITS.

  - N_ELEMENTS: common::Int

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

  - POINTS: common::Matrix<Rational>

    If the matroid is realizable over the rationals, this property contains (homogeneous) coordinates for some realization. Specifying coordinates is one way to define a matroid.

  - POLYTOPE: polytope::Polytope<Rational>

    Polytope whose vertices are the characteristic vectors of the bases.

  - RANK: common::Int

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

## User Functions

- ###
  Others

- matroid_test (bases)

  Tests whether the given bases do actually form the bases of a matroid.

  ##### Parameters

  Array<Set<Int>> | bases |

  ##### Options

  Bool | print | if set to true the output tells which condition fails; default value is 0

- tropical_matroid_polytope (m, v) → tropical::TropicalPolytope

  Produce the tropical matroid polytope from a matroid m. Each vertex corresponds to a basis of the matroid, the non-bases coordinates get value 0, the bases coordinates gets value v, default is -1.

  ##### Parameters

  Matroid | m |
  Rational | v | value for the bases

  ##### Returns

  tropical::TropicalPolytope |

- ###
  Producing a new matroid from other.

- contraction (m, element) → Matroid

  The matroid obtained from a matroid m by contraction of element .

  ##### Parameters

  Matroid | m |
  Int | element | index of element to be contracted

  ##### Returns

  Matroid |

- ###
  Producing a new matroid from others

- deletion (m, element) → Matroid

  The matroid obtained from a matroid m by deletion of element .

  ##### Parameters

  Matroid | m |
  Int | element | index of element to be deleted

  ##### Returns

  Matroid |

- dual (m) → Matroid

  Produces the dual of a given matroid m.

  ##### Parameters

  Matroid | m |

  ##### Returns

  Matroid |

- ###
  Producing from scratch

- matroid_from_graph (g) → Matroid

  Creates a graphical matroid from a graph g.

  ##### Parameters

  graph::Graph | g |

  ##### Returns

  Matroid |

- matroid_from_matroid_polytope (p) → Matroid

  Creates a matroid from the corresponding matroid polytope p.

  ##### Parameters

  polytope::Polytope | p |

  ##### Returns

  Matroid |

- uniform_matroid (r, n) → Matroid

  Creates the uniform matroid of rank r with n elements.

  ##### Parameters

  Int | r |
  Int | n |

  ##### Returns

  Matroid |