Today, my supervisor Prof. Bart De Bruyn got the acceptance email from the editor of Annals of Combinatorics for our joint paper “On semi-finite hexagons of order containing a subhexagon” which we had submitted in July 2014. Both the referee reports were very positive and encouraging. This was my first ever research paper and I am naturally quite happy with it. In this post I would try to give a summary of the results and the main techniques used in an easily accessible way. A preprint of the paper can be found here and slides of a talk I gave on my work can be found here.
An important type of point-line geometries (think of them as hypergraphs where vertices are called points and the edges are called lines if that helps) is the class of generalized polygons introduced by Jacques Tits in 1959. One of the main reasons for their study was that they have connections with some interesting objects like finite groups of Lie type and Moore graphs. The graph theory connection is much easier to explain and I would stick to that. For every point-line geometry (or a hypergraph) we have an associated bipartite graph, called the incidence graph, which is formed by taking the points and lines as vertices, and joining a point to a line if the is incident with (or contained in) .
A generalized -gon is a point-line geometry whose incidence graph has diameter and the maximum possible girth, .
The smallest case gives us the complete bipartite graph, i.e., every point is connected to every line, while for we get what is more common known as a projective plane. A generalized polygon is said to be thick if every vertex in its incidence graph has degree at least . It can be shown that all other generalized polygons can be derived from the thick ones, so they are the only ones worth studying.
In 1964 Walter Feit and Graham Higman showed that besides the trivial examples for and the projective planes for , thick generalized -gons can only exist for equal to or , the so called quadrangles, hexagons and octagons. This narrows down the search for these objects to only three cases! There were examples known for all of these but even after 60 years we don’t know if we have all of them. Many new generalized quadrangles were discovered in past 60 years but for hexagons and octagons all we have are the examples originally given by Tits.
Tits asked an interesting (and important) question about the generalized polygons. Can these structures be semi-finite? That is, can we have a generalized -gon where the number of lines through each point is infinite while the number of points on each line is finite? This turned out to be an extremely challenging problem. The only progress that had been made was that semi-finite generalized quadrangles cannot exist when every line has exactly points on it for a fixed , and , proved by Peter Cameron (1981), Andries Brouwer/Bill Kantor (1990) and Gregory Cherlin (2005), respectively. Peter Cameron has briefly mentioned this problem in his blog post The field with one element.
In this paper, we have made a small contribution towards the solution of this important open problem in finite geometry. We prove that a semi-finite generalized hexagon with three points on each line cannot exist, under the condition that it contains a (finite) subhexagon of order (a generalized polygon is said to have order if it has points on each line and lines through each point). Generalized hexagons of order are well known and some easy constructions of them can be found here. Note that this is the first such result for generalized hexagons.
The basic idea is to study the (completely classified) generalized hexagons of order and then to arrive at a contradiction if we assume that a semi-finite generalized hexagon contains them. Of course, there are many properties of these hexagons that could be studied but we focussed on only those properties that are related to embedding one generalized polygon into another. A general theory of such embeddings was developed by Bart in his paper on Polygonal Valuations, which was the starting point of our work. Computing these so called valuations of a given generalized polygon tells us a lot about every other (possibly infinite) generalized polygon that would contain as a (full) subgeometry. The theory has been quite successful for characterising known geometries and sometimes finding new ones!
In our paper we use a more “loose” definition of valuations, which lets us prove an even stronger result of classifying all near hexagons that contain these subhexagons. The near polygons are even more general than generalized polygons, in the sense that every generalized -gon (which by the result of Feit and Higman can be assumed to have or ) is a near -gon (something I have not defined in this post).
Another important thing I would like to mention is that using computers in computing the valuations (and some other things) made our life much easier. And in fact, it would be a bit foolish to do these computations by hand. The algorithmic part for our research has been quite interesting and after some time I found out that I could use the Dancing Links algorithm by the famous computer scientist/mathematician Donald Knuth to do these computations for geometries with more than two points on each line. These computations and some ideas from the paper on polygonal valuations by Bart have recently lead to more results on semi-finite generalized hexagons which we are hoping to publish soon.