Macaulay2 » Documentation
Packages » Matroids :: Matroid
next | previous | forward | backward | up | index | toc

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.0674269s (cpu); 0.0673014s (thread); 0s (gc)

o10 = true
 
i11 : time fVector R10
 -- used 0.127527s (cpu); 0.0814487s (thread); 0s (gc)

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.00061712s (cpu); 0.000299358s (thread); 0s (gc)

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.

The source of this document is in Matroids/doc-Matroids.m2:127:0.