Skip to content

A matroid / geometry problem and conjecture

May 15, 2013

Rather than let this blog die off due to lack of posts, I thought I’d write about a small but annoying problem that I’ve been thinking about recently, but without success, and a natural conjecture that has arisen from it.

[Note: On some browsers there appears to be a sizing problem with the images WordPress uses for LaTeX formulas, and they appear ten times the right size. If this happens, reloading the webpage seems to fix it]

The problem arose in the context of binary matroids, but because a binary matroid is really just a set of points in a binary vector space, it can be phrased entirely as a linear algebra problem.

So let {M} be a set of non-zero vectors in the vector space {V = GF(2)^r} such that {M} spans {V} and, for reasons to be clarified later, no vector in {M} is independent of the others. In matroid terminology, this just says that {M} is a simple binary matroid of rank {r} with no coloops.

Then define a  basis of {M} to be a linearly independent subset of {M} of rank {r} (in other words, just a basis of {V} and a circuit of {M} to be a minimally dependent set of vectors, i.e. a set of vectors that is linearly dependent but any proper subset of which is linearly independent.

As an example, take {M = PG(2,2)} (a.k.a the Fano plane) — this means to take all the non-zero vectors in {GF(2)^3}. This has 28 bases (7 choices for a first vector {v}, 6 for a second vector {w} and then 4 for the third vector which cannot be {v}, {w} or {v+w} , then all divided by 6 because this counts each basis {6} times). It has 7 circuits of size 3 (each being of the form {v}, {w}, {v+w}) and 7 circuits of size 4, being the complements of the circuits of size 3, for a total of 14 circuits.

Letting {b(M)}, {c(M)} denote the numbers of bases and circuits of {M} respectively, the question is about the ratio of these two numbers. More precisely,

Determine a lower bound, in terms of the rank {r}, for the ratio {\frac{b(M)}{c(M)}}?

Many years ago, James Oxley (the author of Matroid Theory, the definitive reference tome on matroid theory) proved that

\displaystyle b(M) > \tfrac{6}{19} (r+1) c(M),

but the proof is rather fiddly and the constant {6/19} is an artefact of the proof, rather than significant. In the paper, James mentioned that the referee had suggested that perhaps

\displaystyle b(M) \geq \tfrac{1}{2} (r+1) c(M)

was the proper bound. In one sense this would be best possible because, as described above, the Fano plane has {b(M) = 28}, {c(M) = 14} and {r=3} and so meets the bound.

We can easily determine by computer the exact possibilities for small rank — there are only 1372 pairwise inequivalent subsets of {GF(2)^5} of rank at most 5 (here “pairwise inequivalent” means that no element of the group {GL(5,2)} maps one to the other). Using the inbuilt commands of the new sage-matroids package it is only a few commands to compute the numbers of bases and circuits and then plot the resulting ratios.

basecount

The plot shows the ratio of {b(M)/c(M)} against the size of the subset, with red for the ones of rank 4 and blue for the ones of rank 5. The pattern is clear – the lowest ratio is obtained when every possible vector is included in the set — in other words, when {M = PG(r-1,2)}, the full projective geometry of rank {r}. Therefore I propose the following conjecture:

If {M} is a simple binary matroid of rank {r} with no coloops then

\displaystyle b(M) / c(M) \geq b(PG(r-1,2))/c(PG(r-1,2))

with equality if and only if {M = PG(r-1,2)}.

What about rank 6? Well, there are about 480 million binary matroids of rank 6 and the computation of the bases and circuits is sufficiently time consuming that it can’t just be done in an idle moment. So the data for rank 6 will have to wait.

The numbers of bases and circuits for {PG(r-1,2)} is known, and if we define {\alpha_r} by {b(PG(r-1,2)) = \alpha_r (r+1) c(PG(r-1,2))} then {\alpha_r \rightarrow 1} as {r \rightarrow \infty}. Thus every statement of the form {b(M) \geq \alpha (r+1) c(M)} for any fixed {\alpha} (necessarily {\alpha < 1}) is weaker than this conjecture.

So, how to prove such a conjecture? Ideally it would be the case that adding an element to the set reduced the ratio, and that does indeed seem to be the case as long as the matroid reaches a certain critical size. But how to identify this critical size and deal with the smaller cases remains unclear to me, though any ideas would be more than welcomed!

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: