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, graph
uses: group, ideal, polytope, topaz

Objects

User Functions

  •  

    These functions capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

    •  
      internal_activity () → Int

      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
      Int
    •  
      _4ti2Circuits (A) → Matrix

      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
      MatrixA
      Matrix containing the points as rows.
      Returns
      Matrix
  •  

    Special purpose functions.

    •  
      bases_from_revlex_encoding (encoding, r, n) → Array<Set>

      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
      Stringencoding
      the revlex encoding of the list of bases of the matroid
      Intr
      the rank of the matroid
      Intn
      the number of elements of the matroid
      Options
      Booldual
      whether to construct the dual matroid instead
      Boolcheck_basis_exchange_axiom
      whether to perform the check of the axiom after construction
      Returns
      Array<Set>
    •  
      bases_to_revlex_encoding (bases, r, n) → String

      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
      Array<Set>bases
      the list of bases of the matroid
      Intr
      the rank of the matroid
      Intn
      the number of elements of the matroid
      Returns
      String
    •  
      check_basis_exchange_axiom (a) → Int

      Check if a given list of sets satisfies the axioms to be the bases of a matroid.

      Parameters
      Array<Set>a
      list of would-be bases of a matroid
      Options
      Boolverbose
      print a proof if the given sets do not form the set of bases of a matroid
      Returns
      Int
      is_matroid are the given sets the bases of a matroid?
    •  
      is_modular_cut (M, C) → Bool

      Check if a subset of the lattice of flats of a matroid is a modular cut

      Parameters
      MatroidM
      the matroid
      Array<Set>C
      a list of flats to check if they form a modular cut in M
      Returns
      Bool
    •  
      lex_extension (M, C) → Matroid

      Calculate the lexicographic extension of a matroid in a modular cut

      Parameters
      MatroidM
      the original matroid to be extended
      Array<Set>C
      a list of flats that form a modular cut in M
      Options
      check_modular_cutwhether
      to check if C in fact is a modular cut; default 1
      Returns
      Matroid
    •  
      matroid_plueckervector (m) → ListReturn

      Creates the characteristic- and the rank-plueckervector of a matroid.

      Parameters
      Matroidm
      Returns
      ListReturn
      (Vector<Integer>, Vector<Integer>)
  •  

    These functions construct a new Matroid from other objects of the same type.

    •  
      contraction (m, element) → Matroid

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

      Parameters
      Matroidm
      Intelement
      index of element to be contracted
      Returns
      Matroid
    •  
      deletion (m, element) → Matroid

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

      Parameters
      Matroidm
      Intelement
      index of element to be deleted
      Returns
      Matroid
    •  
      direct_sum (m_1, m_2) → Matroid

      The direct sum of matroids m1 and m2

      Parameters
      Matroidm_1
      Matroidm_2
      Returns
      Matroid
    •  
      dual (m) → Matroid

      Produces the dual of a given matroid m.

      Parameters
      Matroidm
      Returns
      Matroid
    •  
      parallel_extension (m_1, e_1, m_2, e_2) → Matroid

      The parallel extension of matroids m1 and m2 with basepoints e1 and e2

      Parameters
      Matroidm_1
      inte_1
      Matroidm_2
      inte_2
      Returns
      Matroid
    •  
      parallel_extension (m, e) → Matroid

      The parallel extension of a matroid m and uniform(2,4) with basepoint e

      Parameters
      Matroidm
      inte
      Returns
      Matroid
    •  
      series_extension (m_1, e_1, m_2, e_2) → Matroid

      The series extension of matroids m1 and m2 with basepoints e1 and e2

      Parameters
      Matroidm_1
      inte_1
      Matroidm_2
      inte_2
      Returns
      Matroid
    •  
      series_extension (m, e) → Matroid

      The series extension of a matroid m and uniform(2,4) with basepoint e

      Parameters
      Matroidm
      inte
      Returns
      Matroid
    •  
      two_sum (m_1, e_1, m_2, e_2) → Matroid

      The 2-sum of matroids m1 and m2 with basepoints e1 and e2

      Parameters
      Matroidm_1
      inte_1
      Matroidm_2
      inte_2
      Returns
      Matroid
  •  

    These functions construct a new Matroid from other objects.

  •  

    With these clients you can create special examples of matroids belonging to parameterized families.