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

flats -- flats of a matroid

Synopsis

Description

A flat, or closed subset, of a matroid is a subset A of the ground set which equals its closure. The set of flats, partially ordered by inclusion, forms a lattice, called the lattice of flats. This is an important invariant of the matroid: one can recover the matroid from the lattice of flats, and for simple matroids (i.e. matroids whose circuits all have size >= 3), the isomorphism type of the lattice is already a complete invariant.

If a target rank r is provided, then this method computes closures of independent sets of size r. This may be slower than simply computing all flats, and then selecting those of rank r.

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

o1 = a matroid of rank 2 on 4 elements

o1 : Matroid
i2 : flats(M, 1)

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

o2 : List
i3 : netList flats M

     +----------------+
o3 = |set {3}         |
     +----------------+
     |set {0, 3}      |
     +----------------+
     |set {1, 2, 3}   |
     +----------------+
     |set {0, 1, 2, 3}|
     +----------------+

If no target rank is provided, this method computes flats by iteratively intersecting hyperplanes of M: every flat of corank k (i.e. of rank = rank M - k) can be expressed as an intersection of k hyperplanes (cf. Oxley, Prop. 1.7.8). Thus if hyperplanes of M have been precomputed, then this function is typically much faster.

i4 : M = matroid completeGraph 7

o4 = a matroid of rank 6 on 21 elements

o4 : Matroid
i5 : time #hyperplanes M
     ‐‐ used 4.98437 seconds

o5 = 63
i6 : time #flats M
     ‐‐ used 0.515625 seconds

o6 = 877

See also

Ways to use flats :

For the programmer

The object flats is a method function.