|G| <= (qr - 1)/(q - 1),
which is the number of points in an r-1-dimensional projective geometry of order q if such exists. Furthermore, the upper bound is attained only by projective geometries. "Splitting" means that G is the union of two disjoint proper flats.
The conjecture has been proved for ranks r <= 5. The hypothesis that G is nonsplitting is superfluous in rank 3 and can be replaced by connectedness in rank 4. It is necessary in higher ranks, as examples like the following show: let G be the direct sum of n m-point lines, with n > 2, truncated down one rank so r = 2n - 1. If m is chosen properly, G satisfies the cocircuit bound but not the point bound.
This problem was proposed by Joe Bonin. firstname.lastname@example.org
Given a matroid and a number r, you want to find the size of a largest flat with rank r.
The natural decision form of this question is: Max r-Flat Lower Bound
Given n, is the maximum size of an r-flat >= n?
I assume an "oracle" is available to decide whether a given point is a member of a given flat. In the vector case such an oracle is elementary. (I think of the flat as specified by a basis.)
The decision problem is obviously in NP, since given an r-flat with at least n points it is easy to verify that it is an r-flat and has at least n points. Thus the question is whether it is NP-complete. It certainly would seem to be. I haven't given this enough thought to know whether or not it is easy to prove NP-completeness. Possibly a known NP-complete problem is a special case.
This problem was raised by Vasily G. Shabat.
Covering And Packing by Flats
Kahn and Kung say a matroid "splits" if it is the disjoint union of two proper flats. (See Bonin's Problem above.) This suggests two problems that seem pretty interesting although, as far as I know, useless and difficult.Flat Packing
The flat packing number p(M) of a matroid M is the smallest number of proper flats (that is, we may use any flat except the whole point set) that are pairwise disjoint and whose union is the whole point set. What is p(M)?
The flat covering number c(M) is the smallest number of proper flats that cover all the points. What is c(M)?
In both problems the natural decision question is the upper-bound form:
Given n, is p(M), or c(M), <= n?
This is clearly in NP, assuming an oracle like that mentioned in the Maximum r-Flat problem.
I proposed these questions inspired by the examples that force the assumption of G's not splitting in Bonin's problem above. email@example.com
Best Viewed With Any Browser
Last modified 2000 Mar 4
Created 8 June 1998.
Matroids home page.