next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: ideal(Matroid)

ideal(Matroid) -- Stanley-Reisner (circuit) ideal of matroid



The independent sets of a matroid M form a simplicial complex (i.e., are downward closed), called the independence complex of M. Via the Stanley-Reisner correspondence, the independence complex of M corresponds uniquely to a squarefree monomial ideal, which is the output of this method.

The minimal generators of the ideal correspond to minimal non-faces of the simplicial complex. As the faces of the independence complex are precisely the independent sets, the minimal non-faces are exactly the minimal dependent sets, i.e. the circuits of M.

The facets of the simplicial complex correspond to bases of M, and thus also to irreducible components of the ideal of M; which are in bijection with the minimal generators of the Alexander dual ideal via taking complements.

Internally, the ideal of the matroid is a fundamental complete invariant, and is heavily used in many algorithms in this package. Accordingly, once the ideal of a matroid is computed, it is cached in the CacheTable of the matroid, which speeds up any algorithm which requires the ideal as part of the input.

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

o1 = a matroid of rank 2 on 4 elements

o1 : Matroid
i2 : circuits M

o2 = {set {1, 2}, set {3}}

o2 : List
i3 : ideal M

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

o3 : MonomialIdeal of QQ[x ..x ]
                          0   3
i4 : J = dual ideal M

o4 = monomialIdeal (x x , x x )
                     1 3   2 3

o4 : MonomialIdeal of QQ[x ..x ]
                          0   3
i5 : J_*/indices

o5 = {{1, 3}, {2, 3}}

o5 : List
i6 : bases M

o6 = {set {0, 1}, set {0, 2}}

o6 : List

See also