# flats -- flats of a matroid

## Synopsis

• Usage:
flats(M, r)
flats M
• Inputs:
• M, ,
• r, an integer, the target rank (optional)
• 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 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