Matroid -- the class of all matroids

Description

To see how to specify a matroid, see matroid.

In this package, the ground set of the matroid is always (internally) assumed to be a set of the form $\{0, ..., n-1\}$. This means that although the actual elements of the ground set can be arbitrary, all subsets of the ground set are specified by their indices, i.e. as a subset of $\{0, ..., n-1\}$ (this includes bases, circuits, flats, loops, etc.).

For convenience, the user can specify a subset of the ground set either by indices (which are integers between 0 and n-1), or as actual elements. If indices are used, they should be given as a Set, and if elements are used, they should be given as a List.

One can use the function indicesOf to convert elements of the ground set to their indices. Conversely, use subscripts to obtain the elements from their indices.

A recommended way to circumvent this distinction between indices and elements is to make the elements of M equal to integers from 0 to n-1, in which case an element is equal to its index in M.groundSet.

For more on this package-wide convention, see groundSet.

i1 : U24 = uniformMatroid(2, 4)

o1 = a "matroid" of rank 2 on 4 elements

o1 : Matroid

i2 : U24 == dual U24

o2 = true

i3 : ideal U24

o3 = monomialIdeal (x x x , x x x , x x x , x x x )
                     0 1 2   0 1 3   0 2 3   1 2 3

o3 : MonomialIdeal of QQ[x ..x ]
                          0   3

i4 : peek U24

o4 = Matroid{bases => {set {0, 1}, set {0, 2}, set {1, 2}, set {0, 3}, set {1, 3}, set {2, 3}}}
             cache => CacheTable{...3...}
             groundSet => set {0, 1, 2, 3}
             rank => 2

i5 : tuttePolynomial U24

      2    2
o5 = x  + y  + 2x + 2y

o5 : ZZ[x..y]

i6 : N = U24 / {0}

o6 = a "matroid" of rank 1 on 3 elements

o6 : Matroid

i7 : areIsomorphic(N, uniformMatroid(1, 3))

o7 = true

Many computations performed in this package are cached in order to speed up subsequent calculations (as well as avoiding redundancy). These include the circuits, flats, ideal, rank function, and Tutte polynomial of a matroid, and are stored in the CacheTable of the matroid. Since the cache is a MutableHashTable, the user can also manually cache data (e.g. if it has been computed in a previous session), which can greatly speed up computation.

i8 : R10 = specificMatroid "R10"

o8 = a "matroid" of rank 5 on 10 elements

o8 : Matroid

i9 : keys R10.cache

o9 = {groundSet, rankFunction, storedRepresentation}

o9 : List

i10 : time isWellDefined R10
     -- used 0.0385313 seconds

o10 = true

i11 : time fVector R10
     -- used 0.0356264 seconds

o11 = HashTable{0 => 1 }
                1 => 10
                2 => 45
                3 => 75
                4 => 30
                5 => 1

o11 : HashTable

i12 : keys R10.cache

o12 = {hyperplanes, flatsRelationsTable, rankFunction, ideal, ranks, flats,
      -----------------------------------------------------------------------
      groundSet, dual, storedRepresentation}

o12 : List

i13 : time fVector R10
     -- used 0.00014954 seconds

o13 = HashTable{0 => 1 }
                1 => 10
                2 => 45
                3 => 75
                4 => 30
                5 => 1

o13 : HashTable

Functions and methods returning a matroid :

affineGeometry(ZZ,ZZ) -- see affineGeometry -- affine geometry of rank n+1 over F_p
coextension(Matroid) -- see coextension -- the free coextension of a matroid
contraction(Matroid,List) -- see contraction -- contraction of subset of matroid
contraction(Matroid,Set) -- see contraction -- contraction of subset of matroid
deletion(Matroid,List) -- see deletion -- deletion of subset of matroid
deletion(Matroid,Set) -- see deletion -- deletion of subset of matroid
dual(Matroid) -- dual matroid
elementaryQuotient(Matroid,List) -- see elementaryQuotient -- associated to a modular cut or linear subclass
extension(Matroid) -- see extension -- of a matroid relative to a flat or modular cut
extension(Matroid,List) -- see extension -- of a matroid relative to a flat or modular cut
extension(Matroid,Set) -- see extension -- of a matroid relative to a flat or modular cut
matroid(Graph) -- see matroid -- constructs a matroid
matroid(Ideal) -- see matroid -- constructs a matroid
matroid(List) -- see matroid -- constructs a matroid
matroid(List,List) -- see matroid -- constructs a matroid
matroid(List,List,ZZ) -- see matroid -- constructs a matroid
matroid(List,MonomialIdeal) -- see matroid -- constructs a matroid
matroid(Matrix) -- see matroid -- constructs a matroid
matroid(ZZ,List) -- see matroid -- constructs a matroid
minor(Matroid,List,List) -- see minor -- minor of matroid
minor(Matroid,Set,Set) -- see minor -- minor of matroid
parallelConnection(Matroid,Matroid) -- see parallelConnection -- parallel connection of two matroids
projectiveGeometry(ZZ,ZZ) -- see projectiveGeometry -- projective geometry of dimension n over F_p
relabel(Matroid) -- see relabel -- relabel a matroid
relabel(Matroid,HashTable) -- see relabel -- relabel a matroid
relabel(Matroid,List) -- see relabel -- relabel a matroid
relaxation(Matroid) -- see relaxation -- relaxation of matroid
relaxation(Matroid,List) -- see relaxation -- relaxation of matroid
relaxation(Matroid,Set) -- see relaxation -- relaxation of matroid
restriction(Matroid,List) -- see restriction -- restriction to subset of matroid
restriction(Matroid,Set) -- see restriction -- restriction to subset of matroid
seriesConnection(Matroid,Matroid) -- see seriesConnection -- series connection of two matroids
setRepresentation(Matroid,Matrix) -- see setRepresentation -- stores user-defined representation
simpleMatroid(Matroid) -- see simpleMatroid -- simple matroid associated to a matroid
specificMatroid(String) -- see specificMatroid -- creates built-in matroid
specificMatroid(Symbol) -- see specificMatroid -- creates built-in matroid
binarySpike(ZZ) -- see spike -- spike matroid
spike(ZZ) -- see spike -- spike matroid
spike(ZZ,List) -- see spike -- spike matroid
sum2(Matroid,Matroid) -- see sum2 -- 2-sum of matroids
swirl(ZZ) -- see swirl -- swirl matroid
thetaMatroid(ZZ) -- see thetaMatroid -- theta matroid
fromSageMatroid(String) -- see toSageMatroid -- Sage format for matroid
uniformMatroid(ZZ,ZZ) -- see uniformMatroid -- uniform matroid
wheel(ZZ) -- see wheel -- wheels/whirls
whirl(ZZ) -- see wheel -- wheels/whirls

Methods that use a matroid :

allMinors(Matroid,Matroid) -- see allMinors -- returns all minors of one matroid in another
areIsomorphic(Matroid,Matroid) -- whether two matroids are isomorphic
bases(Matroid) -- see bases -- bases of matroid
basisIndicatorMatrix(Matroid) -- see basisIndicatorMatrix -- matrix of basis polytope
characteristicPolynomial(Matroid) -- computes characteristic polynomial of a matroid
circuits(Matroid) -- see circuits -- circuits of matroid
closure(Matroid,List) -- see closure -- closure of a subset of a matroid
closure(Matroid,Set) -- see closure -- closure of a subset of a matroid
cogeneratorChowRing(Matroid) -- see cogeneratorChowRing -- cogenerator of the Chow ring of a matroid
coloops(Matroid) -- see coloops -- coloops of matroid
components(Matroid) -- connected components of matroid
Matroid / List -- see contraction -- contraction of subset of matroid
Matroid / Set -- see contraction -- contraction of subset of matroid
Matroid \ List -- see deletion -- deletion of subset of matroid
Matroid \ Set -- see deletion -- deletion of subset of matroid
flats(Matroid) -- see flats -- flats of a matroid
flats(Matroid,ZZ) -- see flats -- flats of a matroid
flats(Matroid,ZZ,String) -- see flats -- flats of a matroid
fundamentalCircuit(Matroid,List,Thing) -- see fundamentalCircuit -- fundamental circuit of independent set
fundamentalCircuit(Matroid,Set,ZZ) -- see fundamentalCircuit -- fundamental circuit of independent set
fVector(Matroid) -- f-vector of a matroid
getIsos(Matroid,Matroid) -- see getIsos -- all isomorphisms between two matroids
getRepresentation(Matroid) -- see getRepresentation -- retrieves stored representation
getSeparation(Matroid,ZZ) -- see getSeparation -- finds a k-separation of a matroid
groundSet(Matroid) -- see groundSet -- (internal) ground set
hasMinor(Matroid,Matroid) -- see hasMinor -- whether a matroid has a given minor
hyperplanes(Matroid) -- see hyperplanes -- hyperplanes of a matroid
ideal(Matroid) -- Stanley-Reisner (circuit) ideal of matroid
idealChowRing(Matroid) -- see idealChowRing -- the defining ideal of the Chow ring
idealOrlikSolomonAlgebra(Matroid) (missing documentation)
independenceComplex(Matroid) -- independence complex of matroid
independentSets(Matroid) -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
independentSets(Matroid,List) -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
independentSets(Matroid,Set) -- see independentSets(Matroid,ZZ) -- independent subsets of a matroid
independentSets(Matroid,ZZ) -- independent subsets of a matroid
indicesOf(Matroid,List) -- see indicesOf -- indices of a sublist
is3Connected(Matroid) -- see is3Connected -- whether a matroid is 3-connected
isBinary(Matroid) -- see isBinary -- whether a matroid is representable over F_2
isConnected(Matroid) -- whether a matroid is connected
isDependent(Matroid,List) -- see isDependent -- whether a subset is dependent
isDependent(Matroid,Set) -- see isDependent -- whether a subset is dependent
isElementaryQuotient(Matroid,Matroid) -- see isElementaryQuotient -- whether a matroid is an elementary quotient of another matroid
isLinearSubclass(Matroid,List) -- see isLinearSubclass -- whether a list of hyperplanes of a matroid is a linear subclass
isModularCut(Matroid,List) -- see isModularCut -- whether a list of flats of a matroid is a modular cut
isomorphism(Matroid,Matroid) -- computes an isomorphism between isomorphic matroids
isPositivelyOrientable(Matroid) -- see isPositivelyOrientable -- whether a matroid is positively orientable
isPositivelyOriented(Matroid) -- see isPositivelyOriented -- whether a matroid is positively oriented
isQuotient(Matroid,Matroid) -- see isQuotient -- whether a matroid is a quotient of another matroid
isSimple(Matroid) -- whether a matroid is simple
isWellDefined(Matroid) -- whether the input is a well-defined matroid
latticeOfFlats(Matroid) -- see latticeOfFlats -- lattice of flats of a matroid
linearSubclass(Matroid,List) -- see linearSubclass -- associated to an elementary quotient or modular cut
linearSubclass(Matroid,Matroid) -- see linearSubclass -- associated to an elementary quotient or modular cut
loops(Matroid) -- see loops -- loops of matroid
Matroid + Matroid -- union of matroids
Matroid ++ Matroid -- direct sum of matroids
Matroid == Matroid -- whether two matroids are equal
Matroid _ List -- elements of matroid
Matroid _ Set -- see Matroid _ List -- elements of matroid
Matroid _ ZZ -- see Matroid _ List -- elements of matroid
Matroid _* -- see Matroid _ List -- elements of matroid
maxWeightBasis(Matroid,List) -- see maxWeightBasis -- maximum weight basis using greedy algorithm
modularCut(Matroid,List) -- see modularCut -- associated to an elementary quotient or linear subclass
modularCut(Matroid,Matroid) -- see modularCut -- associated to an elementary quotient or linear subclass
nonbases(Matroid) -- see nonbases -- nonbases of matroid
positiveOrientation(Matroid) -- see positiveOrientation -- a positive orientation of a matroid
quickIsomorphismTest(Matroid,Matroid) -- see quickIsomorphismTest -- quick checks for isomorphism between matroids
rank(Matroid) -- rank of a matroid
rank(Matroid,List) -- see rank(Matroid,Set) -- rank of a subset of a matroid
rank(Matroid,Set) -- rank of a subset of a matroid
Matroid | List -- see restriction -- restriction to subset of matroid
Matroid | Set -- see restriction -- restriction to subset of matroid
saveMatroid(Matroid) -- see saveMatroid -- save matroid to file
saveMatroid(Matroid,String) -- see saveMatroid -- save matroid to file
searchRepresentation(Matroid,GaloisField) -- see searchRepresentation -- search for a representation of a matroid over a finite field
toSageMatroid(Matroid) -- see toSageMatroid -- Sage format for matroid
truncate(Matroid) -- see truncate(Set,Matroid) -- the truncation of a matroid with respect to a flat
truncate(Set,Matroid) -- the truncation of a matroid with respect to a flat
truncate(ZZ,Matroid) -- the truncation of a matroid with respect to a flat
tutteEvaluate(Matroid,Thing,Thing) -- see tutteEvaluate -- evaluate Tutte polynomial
tuttePolynomial(Matroid) -- Tutte polynomial of a matroid
tuttePolynomial(Matroid,Ring) -- see tuttePolynomial(Matroid) -- Tutte polynomial of a matroid

For the programmer

The object Matroid is a type, with ancestor classes HashTable < Thing.