flats -- flats of a matroid

Synopsis

• Usage:
flats M
flats(M, r)
flats(M, r, s)
• Inputs:
• M, ,
• r, an integer, a target (co)rank (optional)
• s, , either "rank" or "corank"
• Outputs:

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