Some Problems in Matroid Theory

Compiled by Thomas Zaslavsky

Sources

• Oxley's book has an entire chapter of open problems. (Some may have been solved by now.)
• Joseph P.S. Kung has written two articles called ``surveys'' that are replete with new results and open problems:
  • ``Extremal matroid theory'', in: Neil Robertson and Paul Seymour, eds., Graph Structure Theory, pp. 21-61. Contemporary Mathematics, Vol. 147. American Mathematical Society, Providence, R.I., 1993.
  • ``Critical problems'', in: Joseph E. Bonin, James G. Oxley, and Brigitte Servatius, eds., Matroid Theory, pp. 1-127. Contemporary Mathematics, Vol. 197. American Mathematical Society, Providence, R.I., 1996.

Some Problems I've Found Interesting

• Bonin's Projective Bound

  Suppose a simple matroid G of rank r that does not split has no more than q^r-1 points in each cocircuit.
  Conjecture:

  |G| <= (q^r - 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. jbonin@gwis2.circ.gwu.edu

  Maximum r-Flat

  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)?

  Flat Covering

  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. zaslav@math.binghamton.edu

  ---

  Best Viewed With Any Browser

  Last modified 2000 Mar 4
  Created 8 June 1998.

  Matroids home page.
  E-mail: zaslav@math.binghamton.edu