Matroids, Cyclic Flats, and Polyhedra

Matroids have a wide variety of distinct, cryptomorphic axiom systems that are capable of defining them. A common feature of these is that they are able to be efficiently tested, certifying whether a given input complies with such an axiom system in polynomial time. Joseph Bonin and Anna de Mier, rediscovering a theorem first proved by Julie Sims, developed an axiom system for matroids in terms of their cyclic flats and the ranks of those cyclic flats. As with other matroid axiom systems, this is able to be tested in polynomial time. Distinct, non-isomorphic matroids may each have the same lattice of cyclic flats, and so matroids cannot be defined solely in terms of their cyclic flats. We do not have a clean characterisation of families of sets that are cyclic flats of matroids. However, it may be possible to tell in polynomial time whether there is any matroid that has a given lattice of subsets as its cyclic flats. We use Bonin and de Mier’s cyclic flat axioms to reduce the problem to a linear program, and show that determining whether a given lattice is the lattice of cyclic flats of any matroid corresponds to finding integral points in the solution space of this program, these points representing the possible ranks that may be assigned to the cyclic flats. We distinguish several classes of lattice for which solutions may be efficiently found, based upon the nature of the matrix of coefficients of the linear program, and of the polyhedron it defines, and then identify families of lattice that belong to those classes. We define operations and transformations on lattices of sets by examining matroid operations, and examine how these operations affect membership in the aforementioned classes. We conjecture that it is always possible to determine, in polynomial time, whether a given collection of subsets makes up the lattice of cyclic flats of any matroid.