relaxation -- relaxation of matroid

Synopsis

Usage:

relaxation(M, S)

relaxation M
Inputs:
- M, a matroid,
- S, a set, of indices, or a list of elements in M, which is a circuit-hyperplane of M
Optional inputs:
- CheckWellDefined => ..., default value false, an optional argument
Outputs:
- a matroid, the relaxation of M by S

Description

Let M = (E, B) be a matroid with bases B. If there is a subset S of E that is both a circuit and a hyperplane of M, then the set $B \cup \{S\}$ is the set of bases of a matroid on E, called the relaxation of M by S.

If no set S is provided, then this function will take S to be a random circuit-hyperplane (the first in lexicographic order). If no circuit-hyperplanes exist, then an error is produced.

Many interesting matroids arise as relaxations of other matroids: e.g. the non-Fano matroid is a relaxation of the Fano matroid, and the non-Pappus matroid is a relaxation of the Pappus matroid.

i1 : P = specificMatroid "pappus"

o1 = a "matroid" of rank 3 on 9 elements

o1 : Matroid

i2 : NP = specificMatroid "nonpappus"

o2 = a "matroid" of rank 3 on 9 elements

o2 : Matroid

i3 : NP == relaxation(P, set{6,7,8})

o3 = true

Ways to use relaxation:

relaxation(Matroid)
relaxation(Matroid,List)
relaxation(Matroid,Set)

For the programmer

The object relaxation is a method function with options.