matroid -- constructs a matroid

Synopsis

Usage:

M = matroid(E, B)

M = matroid(E, C, EntryMode => "circuits")

M = matroid(E, N, r)

M = matroid(B)

M = matroid(A)

M = matroid(G)

M = matroid(I)
Inputs:
- E, a list, a ground set
- n, an integer, the size of the ground set
- B, a list, a list of bases
- C, a list, a list of circuits
- N, a list, a list of non-spanning circuits
- r, an integer, the target rank
- A, a matrix, whose column vectors form the ground set
- G, a graph, whose edges form the ground set
- I, an ideal, a squarefree monomial ideal defining the independence complex
Optional inputs:
- EntryMode => ..., default value "bases", select method of specifying matroid
- Loops => ..., default value {}
- ParallelEdges => ..., default value {}
Outputs:
- M, a matroid,

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 an integer n is the first argument, the ground set is taken to be {0, ..., n-1}.

The non-spanning circuits, together with the target rank, may also be specified.

i9 : matroid(toList(0..<8), {{0,1,2,3},{2,3,4,5},{0,1,6,7},{4,5,6,7}}, 4) == swirl 4

o9 = true

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).

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

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

o10 : Matroid

i11 : peek M

o11 = Matroid{bases => {set {0, 1, 2}, set {0, 1, 3}, set {0, 2, 3}, set {1, 2, 3}, set {4, 0, 1}, set {4, 0, 2}, set {4, 1, 2}, set {4, 0, 3}, set {4, 1, 3}, set {4, 2, 3}}}
              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.

i12 : M = matroid completeGraph 3

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

o12 : Matroid

i13 : peek M

o13 = 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.

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

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

o14 : Matroid

i15 : peek M

o15 = Matroid{bases => {set {4, 5}, set {5, 3}, set {5, 1}, set {0, 5}, set {4, 2}, set {4, 1}, 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

i16 : circuits M

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

o16 : 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.

i17 : R = QQ[x_0..x_4]

o17 = R

o17 : PolynomialRing

i18 : I = monomialIdeal (x_0*x_1*x_3,x_1*x_2*x_4,x_0*x_2*x_3*x_4)

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

o18 : MonomialIdeal of R

i19 : M = matroid I

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

o19 : Matroid

i20 : peek M

o20 = Matroid{bases => {set {4, 2, 3}, set {4, 1, 3}, set {4, 0, 3}, set {4, 0, 2}, set {4, 0, 1}, 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.

Ways to use matroid:

matroid(Graph)
matroid(Ideal)
matroid(List)
matroid(List,List)
matroid(List,List,ZZ)
matroid(List,MonomialIdeal)
matroid(Matrix)
matroid(ZZ,List)

For the programmer

The object matroid is a method function with options.