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

  •  

    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?
    •  
      check_flat_axiom (a) → Int

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

      Parameters
      Array<Set>a
      list of would-be flats of a matroid
      Options
      Boolverbose
      print a proof if the given sets do not form the set of flats of a matroid
      Returns
      Int
      are_flats are the given sets the flats of a matroid?
    •  
      check_hyperplane_axiom (a) → Int

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

      Parameters
      Array<Set>a
      list of would-be hyperplanes of a matroid
      Options
      Boolverbose
      print a proof if the given sets do not form the set of hyperplanes of a matroid
      Returns
      Int
      are_hyperplanes are the given sets the hyperplanes of a matroid?
    •  
      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
    •  
      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
      Options
      Boolverbose
      print diagnostic message in case C is not a modular cut; default is true
      Returns
      Bool
    •  
      matroid_plueckervector (m) → List

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

      Parameters
      Matroidm
      Returns
      List
      (Vector<Integer>, Vector<Integer>)
    •  
      minimal_base (matroid, weights) → Set

      Calculates a minimal weight basis.

      Parameters
      Matroidmatroid
      Vectorweights
      for the elements of the matroid
      Returns
      Set
      minimal weight basis
  •  

    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
    •  
      free_extension (M) → Matroid

      Calculate the free extension of a matroid

      Parameters
      MatroidM
      the original matroid to be extended
      Returns
      Matroid
    •  
      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
      Boolcheck_modular_cut
      whether to check if C in fact is a modular cut; default is true
      Boolverbose
      print diagnostic message in case C is not a modular cut; default is true
      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.

    •  
      ag23_matroid () → Matroid

      Configuration of the 9 points in the affine plane AG(2,3).

      Returns
      Matroid
    •  
      ag32_matroid () → Matroid

      Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube.

      Returns
      Matroid
    •  
      ag32_prime_matroid () → Matroid

      The unique relaxation of ag32_matroid.

      Returns
      Matroid
    •  
      f8_matroid () → Matroid

      A minimal non-representable matroid. Non-algebraic.

      Returns
      Matroid
    •  
      fano_matroid () → Matroid

      Creates the Fano plane matroid of rank 3 with 7 elements.

      Contained in extension bundled:group.
      Returns
      Matroid
    •  
      j_matroid () → Matroid

      An excluded minor for some properties (see [Oxley:matroid theory (2nd ed.) page 650]). Non binary. Algebraic over all fields.

      Returns
      Matroid
    •  
      l8_matroid () → 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
    •  
      n1_matroid () → Matroid

      An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

      Returns
      Matroid
    •  
      n2_matroid () → Matroid

      An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

      Returns
      Matroid
    •  
      non_fano_matroid () → Matroid

      The embedding into the reals of the seven points that define the Fano matroid. Representable if and only if the field has not characteristic 2.

      Returns
      Matroid
    •  
      non_p8_matroid () → Matroid

      Obtained from p8_matroid by relaxing its only pair of disjoint circuit-hyperplanes.

      Returns
      Matroid
    •  
      non_pappus_matroid () → 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
    •  
      non_vamos_matroid () → Matroid

      A matroid related to the Vamos matroid (see [Oxley:matroid theory (2nd ed.) page 72])

      Returns
      Matroid
    •  
      o7_matroid () → Matroid

      The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields.

      Returns
      Matroid
    •  
      p7_matroid () → Matroid

      The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.

      Returns
      Matroid
    •  
      p8_matroid () → 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
    •  
      pappus_matroid () → 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
    •  
      pg23_matroid () → Matroid

      Configuration of the 13 points in the projective plane PG(2,3).

      Returns
      Matroid
    •  
      projective_plane (p) → Matroid

      Creates the projective plane matroid of rank 3 with p**2+p+1 elements, where p is a prime.

      Contained in extension bundled:group.
      Parameters
      Integerp
      Returns
      Matroid
    •  
      q3_gf3_star_matroid () → Matroid

      The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.

      Returns
      Matroid
    •  
      q8_matroid () → 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
    •  
      r10_matroid () → Matroid

      A regular matroid that's not graphical nor cographical. Algebraic over all fields.

      Returns
      Matroid
    •  
      r8_matroid () → Matroid

      The real affine cube.

      Returns
      Matroid
    •  
      r9a_matroid () → Matroid

      Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

      Returns
      Matroid
    •  
      r9b_matroid () → Matroid

      Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

      Returns
      Matroid
    •  
      t8_matroid () → 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
    •  
      uniform_matroid (r, n) → Matroid

      Creates the uniform matroid of rank r with n elements.

      Parameters
      Intr
      Intn
      Returns
      Matroid
    •  
      vamos_matroid () → Matroid

      A minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.

      Returns
      Matroid
    •  
      wheel4_matroid () → Matroid

      The rank-4 wheel.

      Returns
      Matroid