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

  •  

    More complex properties of the matroid.

    •  
      check_transversality (M) → List

      Checks whether a matroid is transversal. If so, returns one possible transversal presentation

      Parameters
      MatroidM
      Returns
      List
      (Bool, Array<Set<Int> >) First a bool indicating whether M is transversal If this is true, the second entry is a transversal presentation

      Example:
      • Computes whether the uniform matroid of rank 3 on 4 elements is transversal.> @a = check_transversality(uniform_matroid(3,4));> print $a[0]; true> print $a[1]; {0 1 2 3} {0 1 2 3} {0 1 2 3}
    •  
      is_nested_matroid (M) → Bool

      Checks whether a matroid is nested, i.e. its lattice of cyclic flats is a chain.

      Parameters
      MatroidM
      Returns
      Bool
      Whether M is nested.
  •  

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

    •  
      _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 (B) → Bool

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

      Parameters
      Array<Set>B
      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
      Bool
      are the given sets the bases of a matroid?
    •  
      check_flat_axiom (F) → Bool

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

      Parameters
      Array<Set>F
      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
      Bool
      are the given sets the flats of a matroid?
    •  
      check_hyperplane_axiom (H) → Bool

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

      Parameters
      Array<Set>H
      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
      Bool
      are the given sets the hyperplanes of a matroid?
    •  
      check_valuated_basis_axioms (bases, valuation) → Bool

      Takes a list of sets and a vector of valuations and checks if they fulfill the valuated basis axioms

      Parameters
      Array<Set<Int> >bases
      Vector<TropicalNumber<Addition,Scalar> >valuation
      Options
      Boolverbose
      . Whether the function should output when some axiom is not fulfilled. False by default.
      Returns
      Bool
      . Whether this is a basis valuation
    •  
      check_valuated_circuit_axioms (M) → Bool

      Takes a matrix of TropicalNumbers and checks if the rows fulfill the valuated circuit axioms

      Parameters
      Matrix<TropicalNumber<Addition,Scalar> >M
      Options
      Boolverbose
      . Whether the function should output when some axiom is not fulfilled. False by default.
      Returns
      Bool
      . Whether the matrix is a circuit valuation
    •  
      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, S) → Matroid

      The matroid obtained from a matroid m by contraction of set S .

      Parameters
      Matroidm
      Set<Int>S
      indices of elements to be contracted
      Options
      Array<String>computed_properties
      This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
      Returns
      Matroid

      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.> $u = uniform_matroid(2,3);> $d = contraction( $u, (new Set([0,1])), computed_properties=>[qw(CIRCUITS VECTORS)]);> print join(",",$d->list_properties()); N_ELEMENTS,CIRCUITS,VECTORS> $d2 = contraction($u, new Set([0,1]));> print join(",",$d2->list_properties()); N_ELEMENTS,BASES
    •  
      contraction (m, x) → Matroid

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

      Parameters
      Matroidm
      Intx
      index of element to be contracted
      Options
      Array<String>computed_properties
      This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
      Returns
      Matroid
    •  
      deletion (m, S) → Matroid

      The matroid obtained from a matroid m by deletion of set S .

      Parameters
      Matroidm
      Set<Int>S
      indices of elements to be deleted
      Options
      Array<String>computed_properties
      This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
      Returns
      Matroid

      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.> $u = uniform_matroid(2,3);> $d = deletion( $u, (new Set([0,1])), computed_properties=>[qw(CIRCUITS VECTORS)]);> print join(",",$d->list_properties()); N_ELEMENTS,CIRCUITS,VECTORS> $d2 = deletion($u, new Set([0,1]));> print join(",",$d2->list_properties()); N_ELEMENTS,BASES
    •  
      deletion (m, x) → Matroid

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

      Parameters
      Matroidm
      Intx
      index of element to be deleted
      Options
      Array<String>computed_properties
      This is a list of property names. Allowed are BASES, CIRCUITS and VECTORS. If given, only these properties will be computed from their counterparts in m. If none is given, the default is BASES
      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. 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 its BASES.

      Parameters
      Matroidm
      Returns
      Matroid
    •  
      dual (M) → ValuatedMatroid<Addition,Scalar>

      Computes the dual of a valuated matroid.

      Parameters
      ValuatedMatroid<Addition,Scalar>M
      A valuated matroid
      Returns
      ValuatedMatroid<Addition,Scalar>
      The dual valuated matroid.
    •  
      free_extension (M) → Matroid

      Computes the free extension of a matroid, i.e. the principal_extension, with F the full ground set.

      Parameters
      MatroidM
      A matroid
      Returns
      Matroid
      The free extension of M
    •  
      higgs_lift (M) → Matroid

      Computes the Higgs lift of a matroid, i.e. the principal_lift with respect to the full ground set.

      Parameters
      MatroidM
      A matroid.
      Returns
      Matroid
      The Higgs lift L_E(M)
    •  
      intersection (M) → Matroid

      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
      MatroidM
      A list of matroids, defined on the same ground set.
      Returns
      Matroid
      The intersection of all matroids in M
    •  
      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(1,2) with basepoint e

      Parameters
      Matroidm
      Inte
      Returns
      Matroid
    •  
      principal_extension (M, F) → Matroid

      Computes the principal extension of a matroid with respect to a flat.

      Parameters
      MatroidM
      A matroid
      Set<Int>F
      A set F, which is a flat of M
      Returns
      Matroid
      The principal extension M +_F n. If M is a matroid on 0 .. n-1, then the principal extension has ground set 0 .. n. Its bases are the bases of M, plus the sets B-q+n, where B is a basis of M and q is in B and F.
    •  
      principal_lift (M, F) → Matroid

      Computes the principal lift of a matroid with respect to a flat F

      Parameters
      MatroidM
      A matroid
      Set<Int>F
      A set F, which is a flat of M
      Returns
      Matroid
      The principal lift L_F(M) = T_F(M*)*, where T_F is the principal_truncation and * denotes the dualizing operator
    •  
      principal_truncation (M, F) → Matroid

      Computes the principal truncation of a matroid with respect to a flat.

      Parameters
      MatroidM
      A matroid
      Set<Int>F
      A set F, which is a flat of M
      Returns
      Matroid
      The truncation T_F(M), i.e. the matroid whose bases are all sets B-p, where B is a basis of M and p is in F and B.
    •  
      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(1,2) with basepoint e

      Parameters
      Matroidm
      Inte
      Returns
      Matroid
    •  
      trivial_valuation <Addition> (M) → ValuatedMatroid<Addition,Scalar>

      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 Max
      Parameters
      MatroidM
      A matroid
      Returns
      ValuatedMatroid<Addition,Scalar>
      The matroid with a trivial valuation
    •  
      truncation (M) → Matroid

      Computes the truncation of M, i.e. the principal_truncation, with F the full ground set

      Parameters
      MatroidM
      A matroid
      Returns
      Matroid
      The truncation T(M)
    •  
      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
    •  
      union (M) → Matroid

      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
      MatroidM
      A list of matroids, defined on the same ground set.
      Returns
      Matroid
      The union of all matroids in M
  •  

    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. Representable over a field of characteristic two.

      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.

      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
    •  
      special_matroid (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
      Strings
      The name of the matroid
      Possible values:
      'ag23'
      Configuration of the 9 points in the affine plane AG(2,3).
      'ag32'
      Configuration of all points in the affine 3-space AG(3,2) or the binary affine cube.
      'ag32_prime'
      The unique relaxation of ag32_matroid.
      'fano'
      The Fano matroid
      'f8'
      A minimal non-representable matroid. Also non-algebraic.
      'j'
      An excluded minor for some properties (see [Oxley:matroid theory (2nd ed.) page 650]). Not binary. Algebraic over all fields.
      'l8'
      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.
      'n1'
      An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
      'n2'
      An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
      'o7'
      The complement of the rank-3 whirl in PG(2,3). Non binary. Algebraic over all fields.
      'p7'
      The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.
      'p8'
      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.
      'non_p8'
      Obtained from p8_matroid by relaxing its only pair of disjoint circuit-hyperplanes.
      'pappus'
      The Pappus matroid
      'non_pappus'
      The non-Pappus matroid
      'pg23'
      Configuration of the 13 points in the projective plane PG(2,3).
      'q3_gf3_star'
      The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.
      'q8'
      A minimal non-representable matroid. An excluded minor for fields that are not of characteristic 2 or have 3 elements. Non-algebraic.
      'r8'
      The real affine cube.
      'r9a'
      Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
      'r9b'
      Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
      'r10'
      A regular matroid that's not graphical nor cographical. Algebraic over all fields.
      't8'
      Representable if and only if the field has characteristic 3. An excluded minor for fields that are not of characteristic 2 or 3.
      'vamos'
      The Vamos matroid
      'non_vamos'
      The non-Vamos matroid
      'wheel4'
      The 4-wheel
      'non_fano'
      The non-Fano 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