Many of us just received the sudden news of the passing of Laci Kovács, who spent amost of his career at the Australian National University and retired around 2001. Laci was a student of Bernhard Neumann and supervised 18 graduate students.

My own personal interaction with Laci started in my honours year. I was lucky enough to have solved a problem in combinatorial group theory and I sent a draft of a paper to a dozen or so group theorists. Laci and I exchanged emails and I looked into the possibility of persuing a PhD with him, but what discouraged me from going to ANU was his plans to take long service leave, and possible retirement. Plus, I was also in contact with Cheryl Praeger who was effectively luring me to the west, and that’s what I eventually ended up doing. Laci ended up being one of my PhD examiners and took great interest in my work. He came to Perth at least a couple of times during my PhD and first postdoc, and we had long enjoyable discussions in my office, on politics (one of Laci’s pet subjects) and mathematics.

Laci was one of the integral members of the golden era of group theory at ANU, and he will be sorely missed by the GT-community.

Just a quick reminder that the annual “Australasian Conference on Combinatorial Mathematics and Combinatorial Computing” (ACCMCC) will be in Perth this December, and registration is open.

It’s a good idea to get in early in getting accommodation at St George’s College (across the road from UWA), which you must book yourself. The early-bird registration is available until 11th November.

Yesterday, after lunch, Gordon, Luke Morgan, and I decided to grab a coffee from a local establishment:
Me: “We’ll have two long blacks and one short black please”.
Cashier: “Do you want milk in your long black?”

… Then we had this uncomfortable Louis Theroux moment where I looked at her blankly for a longer than normal amount of time.

Me: “If I did, then it wouldn’t be a long black then”.

I guess I’m used to enforcing the clarity of a definition.

I’m in France at the moment, having spent the last week at a workshop on matroid computation at Henry Crapo’s house in the tiny village of La Vacquerie et Saint Martin de Castries, but now I’ve moved on to Paris for a week.

I had been intending to drop in to see Michel Las Vergnas, but it seems that I somehow missed the sad news that he died in January. Although I only met him once, a few years go in Barcelona, we had frequently communicated about an exasperating conjecture of his.

A quick bit of background: start with the vertex-edge incidence matrix of the graph, such that the column corresponding to the edge ${e=vw}$ has exactly two non-zero entries, both equal to one, in rows ${v}$ and ${w}$. Viewed as a matrix over ${GF(2)}$, the row space and null space of this matrix are called the cocycle space ${C}$ and the cycle space ${C^\perp}$ of the graph. The non-zero vectors in ${C}$, called the cocycles, are the (characteristic vectors of the) cut-sets of the graph, while the non-zero vectors in ${C^\perp}$, called the cycles, are the subgraphs in which every vertex has even degree. (Notice that this notion of cycle is considerably broader than the usual graph-theoretic notion.) A set of edges that is simultaneously a cycle and a cocycle is called a bicycle, and the bicycle space is the vector space ${C \cap C^\perp}$. (A coding theorist would call this the hull of the linear code ${C}$.)

If ${T(x,y)}$ is the Tutte polynomial of the graph, then it is well known that

$\displaystyle T(-1,-1) = \pm \ 2^{d(C\cap C^\perp)}$

where ${d(C\cap C^\perp)}$ is the dimension of the bicycle space.

Among many other things, Las Vergnas was interested in a variety of evaluations of the Tutte polynomial along the diagonal where ${y=x}$, and so he considered the polynomial ${D(x) = T(x,x)}$ and (for reasons unknown to me) its derivates ${D'}$, ${D''}$, ${D'''}$, etc. all evaluated at the point ${x=-1}$. While he could not find an interpretation for ${D'(-1)}$, ${D''(-1)}$, ${\ldots}$ he noticed that the sequence of values generated appeared to be divisible by unexpectedly high powers of ${2}$, with each differentiation reducing the exponent of ${2}$ by at most one. So he made the following conjecture:

If ${G}$ is a graph with bicycle dimension ${d}$, and ${D(x) = T(x,x)}$ is its diagonal Tutte polynomial, then  ${2^{d-k} \mid D^{(k)}(-1)}$ for all ${k < d}$.

For example, for the graph ${K_6}$, we have

$\displaystyle D(x) = x^{10}+5 x^9+15 x^8+41 x^7+88 x^6+172 x^5+300 x^4+390 x^3+236 x^2+48 x$

and so ${D(-1) = -16}$, ${D'(-1) = 80}$, ${D''(-1) = -220}$, ${D'''(-1) = 270}$, which are indeed divisible by ${16}$, ${8}$, ${4}$ and ${2}$ respectively.

However a quick computer search revealed that as it stands, the conjecture is false — the graph ${K_8}$ is a counterexample. But I was slightly intrigued by now, so I searched a bit harder and noticed that no matter how hard I tried, I could not find any planar graphs that did not have the property of the conjecture. So I emailed Michel and we revised the conjecture to

If ${G}$ is a planar graph with bicycle dimension ${d}$, and ${D(x) = T(x,x)}$ is its diagonal Tutte polynomial, then  ${2^{d-k} \mid D^{(k)}(-1)}$ for all ${k < d}$.

And that’s basically where it stands. Although it is not a particularly important statement in itself, if it is true, then surely there must be some more combinatorial information to be wrung from the Tutte polynomial if only we knew how to look at it in the right way!

In fact, I think that planar graphs is not the precisely correct class to be working with, but rather some class that includes planar graphs; something perhaps like $\Delta Y$ graphs.

One of the central and important concepts in projective geometry is the beautiful connection between 3-dimensional projective space and the Klein quadric. As is indicated by the title, this correspondence between these two geometries was named after the German mathematician Felix Klein, who studied it in his dissertation Über die Transformation der allgemeinen Gleichung des zweiten Grades zwischen Linien-Koordinaten auf eine kanonische Form (1868). The Klein Correspondence can be used to give geometric understanding for certain isomorphisms of low rank classical groups, and we will give an example of some of these in a follow-up post. In geometry, the Klein Correspondence can sometimes illuminate an obscure object in projective 3-space, for the Klein quadric is naturally embedded in a 5-dimensional projective space where there is an added richness to the geometry, and one has available other ways to distinguish certain configurations. For example, if you were to learn about linear complexes in 3-dimensional projective space, you might find one class known as the “parabolic congruences” as a somewhat messy object of pencils of lines centered on the points of a common line. However, under the Klein Correspondence, a parabolic congruence becomes a quadratic cone: one of the first 3-dimensional geometric objects we first encountered in school mathematics. Notice that I have not specified the field we are working over; it won’t matter!

The day started badly. I woke at 3am to a sick and miserable one-year-old, I got stuck in a traffic jam on the way to work, and by lunchtime I was feeling down about the usual whackacademic innuendo. But at 3pm, Eric Swartz knocked on my door. Eric has stunningly proved an outstanding conjecture on generalised quadrangles which I’ll report on when I have his blessing.

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