next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: matroid

matroid -- constructs a matroid

Synopsis

Description

The default representation of a matroid in this package is by its ground set and list of bases.

i1 : M = matroid({a,b,c,d}, {{a,b},{a,c}})

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

o1 : Matroid
i2 : peek M

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

One can create a matroid by specifying its circuits or nonbases instead, using the option EntryMode. Regardless of the value of EntryMode, the bases are automatically computed in the process of creation.

i3 : M = matroid({a,b,c,d},{}, EntryMode => "nonbases") -- defaults to uniform matroid of full rank

o3 = a "matroid" of rank 4 on 4 elements

o3 : Matroid
i4 : peek M

o4 = Matroid{bases => {set {0, 1, 2, 3}}  }
             cache => CacheTable{...2...}
             groundSet => set {0, 1, 2, 3}
             rank => 4
i5 : N = matroid({a,b,c,d}, {{b,c}}, EntryMode => "circuits")

o5 = a "matroid" of rank 3 on 4 elements

o5 : Matroid
i6 : peek N

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

If no ground set is provided, the ground set is taken to be the (sorted) union of the bases/nonbases/circuits.

i7 : M = matroid {{a,b},{a,c}}

o7 = a "matroid" of rank 2 on 3 elements

o7 : Matroid
i8 : peek M

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

If a matrix is provided, then the realizable matroid on the columns of the matrix is returned. The ground set consists of columns of the matrix, and independence is determined by the method rank (which allows flexibility over general rings understood by M2).

i9 : M = matroid random(ZZ^3, ZZ^5)

o9 = a "matroid" of rank 3 on 5 elements

o9 : Matroid
i10 : peek M

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

If a graph is provided, then the graphic matroid is returned. The ground set consists of edges in the graph, and circuits are precisely the (minimal) cycles in the graph.

i11 : M = matroid completeGraph 3

o11 = a "matroid" of rank 2 on 3 elements

o11 : Matroid
i12 : peek M

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

One can use the optional arguments Loops and ParallelEdges to specify loops and parallel edges for the graph, respectively (as the Graphs package does not currently provide functionality for loops or parallel edges). These options are intended only for use with graphic matroids. ParallelEdges should be given as a list of edges (which are two-element sets of the form set$\{i,j\}$ where i, j are vertices in G), and Loops should be given as a list of vertices where the loops are based.

i13 : M = matroid(completeGraph 3, ParallelEdges => {set{0,1},set{0,1},set{1,2}}, Loops => {0,2})

o13 = a "matroid" of rank 2 on 8 elements

o13 : Matroid
i14 : peek M

o14 = Matroid{bases => {set {4, 5}, set {3, 5}, set {1, 5}, set {0, 5}, set {2, 4}, set {1, 4}, set {2, 3}, set {1, 3}, set {1, 2}, set {0, 2}, set {0, 1}}}
              cache => CacheTable{...5...}
              groundSet => set {0, 1, 2, 3, 4, 5, 6, 7}
              rank => 2
i15 : circuits M

o15 = {set {0, 1, 2}, set {1, 2, 3}, set {0, 3}, set {1, 2, 4}, set {3, 4},
      -----------------------------------------------------------------------
      set {0, 4}, set {0, 1, 5}, set {1, 3, 5}, set {1, 4, 5}, set {2, 5},
      -----------------------------------------------------------------------
      set {6}, set {7}}

o15 : List

If a squarefree monomial ideal is provided, corresponding to a simplicial complex $\Delta$ via the Stanley-Reisner correspondence, then the matroid with independence complex $\Delta$ is returned. The ground set consists of the variables in the ring of the ideal.

i16 : R = QQ[x_0..x_4]

o16 = R

o16 : PolynomialRing
i17 : I = monomialIdeal (x_0*x_1*x_3,x_1*x_2*x_4,x_0*x_2*x_3*x_4)

o17 = monomialIdeal (x x x , x x x , x x x x )
                      0 1 3   1 2 4   0 2 3 4

o17 : MonomialIdeal of R
i18 : M = matroid I

o18 = a "matroid" of rank 3 on 5 elements

o18 : Matroid
i19 : peek M

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

Caveat

This function does not check if (E,B) defines a matroid - see isWellDefined.

The bases are not stored as sets of elements of M - rather, the indices (with respect to the ground set) are stored instead. For more, see groundSet.

See also

Ways to use matroid :

For the programmer

The object matroid is a method function with options.