Points And Lines

It is no secret that cool combinatorial and geometrical constructions can take their time before revealing their usefulness in extremal graph theory. In this post I will collect a few, some of which might be not as well-known.

Just over the last few years, we’ve had bilinear forms over finite fields being used over and over and over and over again, the first one in particular being a breakthrough result. The properties that were necessary for their applications have been known for a very long time. The hardest part is figuring out that this is the right object to consider. The geometry associated to these forms, called polar spaces, is tied to the study of classical groups. It is probably fair to say that they owe their very existence to group theory. This theory, in the language of buildings, has been developed by Jacques Tits (Belgian-born!) in the 60s and 70s of the previous century. In other words, it’s been around for a while.

In the first two applications, we are mainly using that in the collinearity graphs of polar spaces of rank (see the recent book by Brouwer and Van Maldeghem for definitions), complete subgraphs are easily found: they must be subsets of cliques corresponding to generators. Since generators are of relatively small dimension (only half of the full space), this means that there aren’t too many cliques of a certain large size which is the foundation for the first application. Combine this with the eventown theorem, which was the modification that Yuval Wigderson gave, and you find a graph with logarithmically small coclique number and a small amount of large cliques. One can then imagine destroying these cliques by coloring vertices with multiple colors so that none remain monochromatic, et voilà, new lower bounds for multicolor Ramsey numbers. Admittedly, it takes the right technique (i.e. random homomorphisms) to actually execute this idea, but the essence of the idea is very neat and not too difficult to explain to a layman.

In the second application, the observation from the previous paragraph implies that all -subgraphs in a rank 2 polar space consist of 3 collinear points. It’s not hard to then make a triangle-free graph out of its collinearity graph: remove edges to transform every maximal clique in a complete bipartite graph. Doing it randomly preserves the ‘random-like’ properties of the original graph, which in this case is stated in terms of jumbledness (see the paper for a definition). This only works for rank 2 though, as maximal cliques, being lines, intersect in at most a point. Once the rank increases, we no longer have this independence of colorings which is crucial for the analysis of the random process.
The point is that we know where the cliques are situated in the graph, and this allows us to modify it in a controlled way. It must be added that Kopparty was actually the first one (to my knowledge) to use polar spaces of rank 2, also known as generalized quadrangles, to construct pseudorandom (in the sense of -graphs) triangle-free graphs of density , but interestingly, he uses an atypical generalized quadrangle, in the sense that it does not belong to a classical family of polar spaces. It can also be done in the classical case, in particular I have an unpublished construction for , odd. Unfortunately, it does not seem like this construction generalizes either and the reason is that this one depends on a one-of-a-kind description in terms of , which seems to not extend to higher ranks.

Moving on the the third and fourth application. The roots of these constructions can be traced back to Alon and Krivelevich who constructed -free graphs based on the observation that no vectors can be pairwise orthogonal in an -dimensional vector space. Orthogonality in the setting of vector spaces over finite fields is defined by bilinear forms as usual, but one needs to take care to remove the self-orthogonal vectors, or rather one-dimensional spaces which projectively are points. The improvements given above use the fact that one can talk roughly half of the projective points to also avoid any subgraphs. When the field size is odd, one can pick projective points depending on whether its evaluation is square or non-square. When is even, the roles of squares and non-squares is replaced by trace one and zero elements.
The bottom line is that these graphs were again known for a while, the paper by Bishnoi, Ihringer and Pepe mentions sources dating back to 1990 and even 1971. For the three-dimensional case, these graphs were also already known to Parsons in 1975, who studied their properties and automorphism groups when is odd.

It is unfortunate to realize that Francesco and I extended Parsons’ result to even in 2018 and briefly considered to find similar results in higher dimensions. We dismissed the idea at the time, since we figured there wouldn’t be much interest or motivation to do so. Only to see those exact graphs pop up years later as a breakthrough in extremal graph theory. Oh well..

Anyway, the final example I want to show is one that really drives the distinction between finite geometers and extremal graph theorists home. In 1996, Füredi published a paper which showed the correct dependence on of the Turán number of . His construction relies on a clever ‘folding’ of the polarity graph which was known to be sharp for . However, the same idea was already known to Mathon in 1987 (extending his own results from 1975), who obtained distance-regular graphs in this way. This class of graphs is highly regular with respect to the usual graph metric. However, Mathon’s construction is only distance-regular for certain choices of and . For example, the construction only works for all when is a power of 2. However, this would not suffice to prove Füredi’s result since the graph sizes in the family would not be dense enough in the integers. If one drops the restrictions, the regularity breaks but the edge density and -freeness remains! It is remarkable that this construction has been overlooked, especially since the title of the paper contains the words ‘Ramsey numbers’.

The choice between regularity and asymptotically optimal properties in this last example seems to be the defining chasm between these two worlds and cultures. In the geometers’ defense, I suppose it does make more sense to describe an object and the properties it does have, instead of figuring out which ones it does not.
Finally, it’s quite curious how consistent the 20 year gap is between discovery in finite geometry and application in extremal graph theory. Even more so, most objects discussed above were found in the 70s and really have found their way to the spotlight in the 90s. Maybe it’s time to revisit some papers from the early 2000s? Or do we have to wait 50 years more before we find say, new generalized polygons?