Macaulay2 » Documentation
Packages » Matroids :: flats
next | previous | forward | backward | up | index | toc

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 returns the list of all rank r flats of M.

If a target corank r is provided along with the mode "corank", then this method computes all intersections of r distinct hyperplanes. This is guaranteed to contain all flats of rank = rank M - r (cf. Oxley, Prop. 1.7.8), and may be useful if the lattice of flats is large, and only the upper portion is required (such as in the Scum theorem).

i1 : M = uniformMatroid(4, 6)

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

o1 : Matroid
 
i2 : netList flats M

     +----------------------+
o2 = |set {}                |
     +----------------------+
     |set {5}               |
     +----------------------+
     |set {4}               |
     +----------------------+
     |set {3}               |
     +----------------------+
     |set {2}               |
     +----------------------+
     |set {1}               |
     +----------------------+
     |set {0}               |
     +----------------------+
     |set {4, 5}            |
     +----------------------+
     |set {3, 5}            |
     +----------------------+
     |set {3, 4}            |
     +----------------------+
     |set {2, 5}            |
     +----------------------+
     |set {2, 4}            |
     +----------------------+
     |set {1, 5}            |
     +----------------------+
     |set {1, 4}            |
     +----------------------+
     |set {0, 5}            |
     +----------------------+
     |set {0, 4}            |
     +----------------------+
     |set {2, 3}            |
     +----------------------+
     |set {1, 3}            |
     +----------------------+
     |set {0, 3}            |
     +----------------------+
     |set {1, 2}            |
     +----------------------+
     |set {0, 2}            |
     +----------------------+
     |set {0, 1}            |
     +----------------------+
     |set {3, 4, 5}         |
     +----------------------+
     |set {2, 4, 5}         |
     +----------------------+
     |set {1, 4, 5}         |
     +----------------------+
     |set {0, 4, 5}         |
     +----------------------+
     |set {2, 3, 5}         |
     +----------------------+
     |set {1, 3, 5}         |
     +----------------------+
     |set {0, 3, 5}         |
     +----------------------+
     |set {1, 2, 5}         |
     +----------------------+
     |set {0, 2, 5}         |
     +----------------------+
     |set {0, 1, 5}         |
     +----------------------+
     |set {2, 3, 4}         |
     +----------------------+
     |set {1, 3, 4}         |
     +----------------------+
     |set {0, 3, 4}         |
     +----------------------+
     |set {1, 2, 4}         |
     +----------------------+
     |set {0, 2, 4}         |
     +----------------------+
     |set {0, 1, 4}         |
     +----------------------+
     |set {1, 2, 3}         |
     +----------------------+
     |set {0, 2, 3}         |
     +----------------------+
     |set {0, 1, 3}         |
     +----------------------+
     |set {0, 1, 2}         |
     +----------------------+
     |set {0, 1, 2, 3, 4, 5}|
     +----------------------+
 
i3 : flats(M, 1)

o3 = {set {5}, set {4}, set {3}, set {2}, set {1}, set {0}}

o3 : List
 
i4 : flats(M, 2, "corank")

o4 = {set {3, 4, 5}, set {4, 5}, set {3, 5}, set {5}, set {3, 4}, set {4},
     ------------------------------------------------------------------------
     set {3}, set {}, set {2, 4, 5}, set {2, 5}, set {2, 4}, set {2}, set {1,
     ------------------------------------------------------------------------
     4, 5}, set {1, 5}, set {1, 4}, set {1}, set {0, 4, 5}, set {0, 5}, set
     ------------------------------------------------------------------------
     {0, 4}, set {0}, set {2, 3, 5}, set {2, 3}, set {1, 3, 5}, set {1, 3},
     ------------------------------------------------------------------------
     set {0, 3, 5}, set {0, 3}, set {1, 2, 5}, set {1, 2}, set {0, 2, 5}, set
     ------------------------------------------------------------------------
     {0, 2}, set {0, 1, 5}, set {0, 1}, set {2, 3, 4}, set {1, 3, 4}, set {0,
     ------------------------------------------------------------------------
     3, 4}, set {1, 2, 4}, set {0, 2, 4}, set {0, 1, 4}, set {1, 2, 3}, set
     ------------------------------------------------------------------------
     {0, 2, 3}, set {0, 1, 3}, set {0, 1, 2}}

o4 : List

In general, this method computes flats by iteratively intersecting hyperplanes of M. 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.