Skip to content

The Klein Correspondence II

October 10, 2013

This is a continuation of my last post on this subject. As Gordon remarked in one of his posts, you may need to refresh your browser if some of the embedded gifs do not appear as they should.

Dualities and isomorphisms of classical groups

Four of the five families of classical generalised quadrangles come in dual pairs: (i) Q(4,q) and W(3,q); (ii) H(3,q^2) and Q^-(5,q). Both can be demonstrated by the Klein correspondence. Recall from the last post that the Klein correspondence maps a line of \mathsf{PG}(3,q) represented as the row space of

M_{u,v}:=\begin{bmatrix}u_0&u_1&u_2&u_3\\v_0&v_1&v_2&v_3\end{bmatrix}

to the point (p_{01}:p_{02}:p_{03}:p_{12}:p_{31}:p_{23}) where

p_{ij}=\begin{vmatrix}u_i&u_j\\v_i&v_j\end{vmatrix}.

Now consider the symplectic generalised quadrangle W(3,q) defined by the bilinear alternating form

B(x,y):=x_0y_1 - x_1y_0 + x_2y_3 - x_3y_2.

A totally isotropic line M_{u,v} must then satisfy

0 = B(u,v) = p_{01} + p_{23} .

Therefore, the lines of W(3,q) are mapped to points of Q^+(5,q) lying in the hyperplane \pi:X_0+X_5=0. Now the quadratic form defining Q^+(5,q) is Q(x)=x_0x_5+x_1x_4+x_2x_3 and \pi is the tangent hyperplane at the projective point (1:0:0:0:0:1), which does not lie in the quadric. Hence the hyperplane \pi is non-degenerate and so we see that W(3,q) maps to points of Q(4,q). That this mapping is bijective follows from noting that the number of lines of W(3,q) is equal to the number of points of Q(4,q) (namely, (q+1)(q^2+1)).

Hence \mathsf{P\Gamma Sp}(4,q)\cong \mathsf{P\Gamma O}(5,q).

Now we will consider a more difficult situation which reveals that the generalised quadrangles H(3,q^2) and Q^-(5,q) are also formally dual to one another. Read more…

News Update

October 9, 2013

It’s been a long time since we posted anything here, but things have kept on happening, so I thought I’d just give a sketchy update.

One of the reasons behind the hiatus in blog posts is that there’s now only two months to go before we host 37ACCMCC, the annual Australasian Combinatorial Conference, here in Perth. I’m the director of the organising committee and it’s quite a juggling act trying to keep on top of everything. It’s a bit of a guessing game too, because we have to book things like the conference dinner and excursion, but with most people registering at the last minute, we have no real idea of numbers! Now I know what it’s like to be on the receiving end, I’m going to register early for all future conferences!

We have a poster now though, which you can see here (or as a PDF here); you can probably recognise the nice building from our blog’s banner image.

accmcc

Read more…

Regular graphs, triangles and MathOverflow

August 2, 2013

I’ve just uploaded a paper “Quartic graphs with every edge in a triangle” to the arxiv — joint with Florian Pfender — that characterises the quartic graphs with the property that every edge lies in a triangle.

Although this property doesn’t seem all that strong at first sight, it is actually very restrictive when the graph is regular of low enough degree. We end up with an exact characterisation saying that a 4-regular graph with every edge in a triangle is either:

  • a squared n-cycle, or
  • the line graph of a cubic (multi) graph, or
  • obtained from these by replacing triangles by copies of K_{1,1,3}.

Exact structural characterisations of natural classes of graphs are appealing, and this contains a nice mixture of a thin infinite family, a general construction and an operation under which the class is closed.

However, this paper would actually never have seen the light of day if it had not been for MathOverflow, the gamified question-and-answer website for research-level maths questions.

Read more…

Vale Laci Kovács

July 28, 2013

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.

A plug/reminder

July 23, 2013

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.

For more information, please go to the conference webpage.

Definitive coffee

July 13, 2013

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.

A Las Vergnas Conjecture

June 30, 2013

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.

Follow

Get every new post delivered to your Inbox.

Join 38 other followers