THE COCYCLE LATTICE OF BINARY MATROIDS

We study the lattice (grid) generated by the incidence vectors of cocycles of a binary matroid and its dual lattice. We characterize those binary matroids for which the obvious characterization yields a polynomial time algorithm to check whether a matroid has this property, and also to construct a basis in the cocycle lattice. For the general case, we prove that every denominator in the dual lattice is a power of 2, and derive upper and lower bounds for the largest exponent. © 1993 Academic Press, Inc.