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{...2...}
             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{...3...}
             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{...4...}
             groundSet => set {0, 1, 2, 3}
             rank => 3

If no ground set is provided, the ground set is taken to be the union of the basis/nonbasis/circuit elements.

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{...2...}
             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 (to allow flexibility over general rings).

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{...2...}
              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{...4...}
              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. These options are intended only for use with graphic matroids (since the Graphs package does not provide functionality for loops or parallel edges). 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{...4...}
              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 Δ via the Stanley-Reisner correspondence, then the matroid with independence complex Δ 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{...3...}
              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 subsets of the ground set - 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.