extension -- of a matroid relative to a flat or modular cut

Synopsis

• Usage:

  extension(M, L),

  extension(M, F),

  extension M

• Inputs:
  • M, a matroid
  • L, a list, a list of flats or hyperplanes of the matroid forming a modular cut/linear subclass
  • F, a set, a flat of the matroid
• Optional inputs:
  • CheckWellDefined => ..., default value false, check whether the list is a modular cut or linear subclass
  • EntryMode => ..., default value "modular cut", use a modular cut or linear subclass
• Outputs:
  • a matroid, a single-element extension of the given matroid

Description

This function is provided by the package Matroids.

A matroid N is a (single-element) extension of a matroid M if M can be obtained from N by deleting a single element e. Every extension N of M is uniquely determined by a modular cut of flats of M whose closure in N contains e.

Given a modular cut K of M, we can construct the corresponding extension.

i1 : M = uniformMatroid(4, 5);

i2 : K = modularCut(M, {{0,1,2}, {2,3,4}})

o2 = {set {4, 2, 3}, set {0, 1, 2}, set {0, 1, 2, 3, 4}}

o2 : List

i3 : isModularCut(M, K)

o3 = true

i4 : N = extension(M, K)

o4 = a "matroid" of rank 4 on 6 elements

o4 : Matroid

Every flat F of the matroid M determines a principal modular cut consisting of all flats containing F. The independent sets of the free extension N come in two types: They are either independent sets of M or sets containing e that, after deleting e, become independent sets of M whose closure in M does not contain F. We can construct the extension corresponding to this modular cut as follows.

i5 : F = set{0, 1, 3}

o5 = set {0, 1, 3}

o5 : Set

i6 : N = extension(M, F)

o6 = a "matroid" of rank 4 on 6 elements

o6 : Matroid

i7 : bases N

o7 = {set {0, 1, 2, 3}, set {0, 1, 2, 4}, set {0, 1, 3, 4}, set {0, 2, 3, 4},
     ------------------------------------------------------------------------
     set {1, 2, 3, 4}, set {2, 3, 4, 5}, set {1, 3, 4, 5}, set {0, 3, 4, 5},
     ------------------------------------------------------------------------
     set {1, 2, 4, 5}, set {0, 2, 4, 5}, set {0, 1, 4, 5}, set {1, 2, 3, 5},
     ------------------------------------------------------------------------
     set {0, 2, 3, 5}, set {0, 1, 2, 5}}

o7 : List

When no modular cut or flat is specified, the free extension of M is constructed. This is the extension corresponding to the modular cut that contains the ground set of M as its only flat. For a uniform matroid U_{r,n}, the free extension is just U_{r,n+1}.

i8 : N = extension M

o8 = a "matroid" of rank 4 on 6 elements

o8 : Matroid

i9 : quickIsomorphismTest(N, uniformMatroid(4, 6))

o9 = true

See also

• coextension -- the free coextension of a matroid
• elementaryQuotient -- associated to a modular cut or linear subclass
• modularCut -- associated to an elementary quotient or linear subclass