Lectures on lower bounds for off-diagonal Ramsey numbers

This week I was in Shenzhen, China to work with Ferdinand Ihringer and give a 6-hour lecture series for graduate students on the recent developments in off-diagonal Ramsey numbers. While the lower bounds by Ajtai-Komlós-Szemerédi have been around for a while, the last few years have seem immense leaps in our understanding of good matching construction, culminating in Bradač’ proof a few months back.

These constructions were exactly the content of the course, starting with the Mubayi-Verstraete paper introducing the idea of using explicit starting graphs, to our result, and finally concluding with the recent construction of Domagoj. The idea was mostly to show how the same ideas appeared in slightly different guises throughout these three results, and also to describe (mostly for my own benefit) Domagoj’s construction in more geometrical language.

These lectures were obviously not a comprehensive overview of everything we as mathematicians have discovered about off-diagonal Ramsey numbers. Notable omissions include proofs of the upper bounds and the recent lower bound developments for . Nevertheless, I think there is a nice story to be told about how, despite virtually no progress for decades, our understanding developed in a rapid fashion once we had the right ideas.

The lecture notes are available here.

Job advertisement: 3y postdoc at UWA

To all researchers on the job market interested in Ramsey theory and/or finite geometry, we are advertising a 3 year postdoctoral Research Associate position at the University of Western Australia, working with the team of John Bamberg (UWA), Anurag Bishnoi (TU Delft), and yours truly.

To apply and find more information, go to

https://external.jobs.uwa.edu.au/en/job/523511/postdoctoral-research-associate-pure-mathematics

Deadline for applications is July 22nd, 2026. 

A sensational Ramsey breakthrough by Domagoj Bradač

UPDATE 17/06: Today, an updated version appeared, in which the exponent was sharpened to . Truly great stuff. After 70 years we finally have the correct exponent, which was already bravely conjectured by Erdős in 1947. I would imagine he would be very happy to see this result, and that random graphs alone are in fact not the answer!
As for the mathematics: the reason we can get from to is (in hindsight) remarkably easy: instead of doing antiflags, do flags instead! This was already known to produce triangle-free graphs for by Kostochka, Pudlák, and Rödl, but somehow it flew under the radar that going to higher dimensions might be a good idea to produce -free graphs. The definition is a bit more delicate now, since we define flags to be incident if they induce a (taking the order of the flags into account) in the point-hyperplane incidence graph of , i.e., we impose cross-incidence one way, and forbid the cross-incidence the other way. This makes the analysis of the count of independent sets a bit trickier, but Domagoj manages to overcome that too. As for the proof that these graphs are -free, it’s a similar rank argument as before, but the paper provides a nice “proof by tilting your head” in Figure 1. Another congrats to Domagoj!

Another addition to the list of big news in Ramsey theory over the last few years was posted online today on the arXiv by Domagoj Bradač. He used an almost deceivingly simple construction to, among many other nice things, prove near optimal lower bounds for off-diagonal Ramsey numbers. The main idea follows a recent trend of considering a base graph (usually geometric or algebraic), count the independent sets, and sample. This very idea was first laid out for pseudorandom graphs by Dhruv and Jacques, and has since been used by Jacques and myself for the case of , and inspired recent progress on . Domagoj himself describes these sources of inspiration himself in the paper, so I will spare you the details here.

The base graph he uses is incredibly easy to describe: consider antiflags in (i.e. ), order them, and then make two antiflags and adjacent if and . It is not too hard to check that this graph is -free, since if we build a clique vertex-by-vertex, every new addition reduces the possible space for the next choice of point. The fact that the dimension actually drops down by 1 with every addition is usually a big pain to achieve with geometrical constructions (i.e. the intersection of hyperplanes could in principle have codimension , much bigger than the wishful ), but is here neatly achieved by the usage of antiflags. The way I understand it, is that this graph is essentially a decoupling of points and hyperplanes implicit in the Alon-Krivelevich polarity graph, thus squaring its order and achieving much better asymptotics.

It goes without saying that I have been looking for such a construction for a while. In fact, I have pages filled with drawings of the graph denoted by on my desk! Yet I never thought about using this graph, so props to Domagoj. At various points in the last few years I even doubted whether we would be able to prove an improvement over the probabilistic method at all, uniformly for all , given that our construction for depends on such a particular algebraic curve with unique properties. I am happy to see this doubt proven wrong, and geometry once again coming to the rescue.

The race is now on to find the last tiny improvement and close the gap between lower and upper bounds (at least up to polylogarithmic factors). I did not see an obvious way to improve the construction. The decoupling for example seems to destroy any hopes of using an idea á la Bishnoi-Ihringer-Pepe to drop the clique number down by 1, but perhaps we are not looking at it the right way.

Finally, similar to previous breakthroughs, one can leverage this graph to obtain better bounds for various closely related problems, like Erdős-Rogers, multicolor Ramsey, and so on. What I find especially nice is that by setting , one can even improve lower bounds in the close-to-diagonal regime. One can hope that one day, we will improve diagonal Ramsey with more geometry and algebra.

For details on all this: go check out the paper and congrats to Domagoj!

More non-opposite flags in finite spherical buildings

Last week, Jan De Beule, Philipp Heering, Klaus Metsch and I posted the results of our investigations into maximum sets of non-opposite flags (henceforth referred to as MSNF for brevity) in finite spherical buildings of type on the arXiv. This work is a natural successor of earlier results by Philipp, Klaus and Jesse Lansdown for type (see later).
In previous posts (1, 2, and 3) we highlighted some of the combinatorics and the algebra that goes into this beautiful theory and so the story continues.

Our main result states that MSNF in type in the majority of cases must be blow-ups from ‘trivial’ sets of collinear points or intersecting generators. I was quite optimistic at the start of this project that the techniques from Philipp and Klaus’ earlier work on type could be readily extended to type , even stating to Philipp at some point in June last year ‘it could be done over the summer’. Turns out it wasn’t so easy after all.
Before we dive into the details of the current paper, let me give an overview of the series of developments on this line of investigation:

Containers, containers, containers

It’s been a while since I managed to wrap up some projects (moving continents and getting more kids sure does take some time!), but the last few weeks I managed to get some work done. First, the paper with Ishay Haviv, Aleksa Milojević and Yuval Wigderson appeared, and today one with Geertrui Van de Voorde did.

Both of them are essentially applications of the container method to combinatorial problems. I first learned about this method while at UCSD, and indeed, it has been instrumental in the Ramsey result with Jacques (whose published version is now available). Admittedly, my understanding was still rather poor, so I decided to study a bit more last winter. I’ll share some of my newly-gained understanding in the course of summarizing both of these two results.

The asymptotics of r(4,t)

Update: Quanta Magazine posted an article about our result as well.

Jacques Verstraete and I posted a preprint on the arXiv today on the off-diagonal Ramsey number . In short, we show that , which is just a factor shy from the upper bound proved by Ajtai, Komlós and Szemerédi in 1980. Erdős [1] conjectured that up to logarithmic factors, is the order of growth:

We thus confirm this conjecture. The previous best lower bound was due to Bohman and Keevash who studied the random -free process and obtained , where the tilde hides logarithmic factors. It is not clear whether our methods can be pushed further to obtain asymptotically sharp bounds. In any case, that’s not what I want to speculate about, but rather sketch the proof of our result. It’s in my very biased opinion a nice combination of ideas that existed in the literature before, but have each been slightly sharpened for our particular application. So without further ado, here are the four main steps with some explanation and the elevator pitch for each.

Old wine in new bottles

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?

Keeping busy

A lot has happened the last few months, but among those things, research was rather low on the list. So instead of the usual research-related post, I’ll give a quick update on what has kept me busy instead.

Since the 25th of May, I am officially Doctor Mattheus upon completing my PhD titled Finite geometry and friends: tilings in abelian groups and combinatorics in spherical buildings. I’ll admit that I have been selecting the ‘Dr.’ instead of the ‘Mr.’ option when booking flights lately. Let’s just hope there will be no medical in-flight emergencies.

The title of course refers to the summer school that we organized at VUB a few years back and gives an idea of the content. I decided against including all of the results I obtained over the last few years. Even though one can certainly find some recurring themes, compiling all of them in a single document would have been too much of a mixed bag. Instead I tried to tell a somewhat coherent story about two lines of research which are mentioned in the title of the thesis.
The first one deals with tilings in abelian groups and mostly serves as some sort of survey. The function of this first part is not to just list my results, but to explain how results from recent years connect to decades-old conjectures. The hope is that this incites some new research into these beautiful open problems. I’d like to say that a solution seems within reach, but I might be terribly wrong of course.
The second part deals with combinatorics in spherical buildings, which I have been talking about before (here, here and also later in this post). This part mostly coincides with our paper (arXiv link), which has been recently published in JCTA. There is some new work-in-progress at the very end, hopefully I can wrap this up soon enough.

It might’ve been a wiser idea to take some well-earned vacation afterwards, but instead I went to Combinatorics 2022, which could be seen as a vacation of some sorts I guess. It was great to finally have an in-person conference again. It was made quite clear again that virtual meetings cannot provide the same experience. Nevertheless, the Student Symposium in Combinatorics, which I attended virtually that week, tried its very best to overcome some of those limitations. I had the pleasure and the opportunity to give a plenary talk there, for which I have to thank the organizers once again. The talk was recorded and can be found here.

Finally, two weeks after I gave a talk in the Waterloo Combinatorics seminar. I talked about our EKR results in spherical buildings. I spoke about this topic a few times in virtual seminars, but I pride myself in the fact that no two talks are identical and are tailored to the audience. This one was recorded as well and can be found here.

All of this took up quite of my time the last few months. There is another part which was concerned with post-PhD life, but that topic deserved its own post.

Plans for the post-PhD life

Or as it is better known, the postdoc life. There was a serious part of me that considered quitting academia after the PhD, but in the end, I decided I want to try and stay anyway. There is course quite a rift between wanting to do a postdoc and getting a postdoc position. That’s why in late 2021 I was mostly spending my time writing grants. The amount of time that went into this would’ve been a pretty terrible waste if it were not the case that all of my applications were successful. Unexpectedly so, since getting all of them would have a probability of around 5% if they were independent events, which they luckily aren’t. So here’s how I got there.

After a long process of figuring out the postdoc possibilities with my wife, we got to the conclusion that a postdoc abroad where she and the kids would join me would be feasible under two conditions:

1) it is just for one year (she could take a one-year break from her job, but not longer);
2) in an English-speaking country (makes meeting people quite a bit easier).

I’d say that this was quite a reasonable compromise. There’s no point in her moving with me if I were to go the UK, so my options were mostly limited to the US, Canada, Australia and New-Zealand. Unfortunately, the one-year postdoc options in these countries are rather limited if non-existent.

Luckily, I found two funding opportunities via my colleague Sam Adriaensen. They are handed out by the Fulbright commission and BAEF. Both of them have one-year grants aimed at postdoctoral researchers which were going the US. The former is not just restricted to Belgium and can be found all over the world. The latter stands for the Belgian American Educational Foundation, so you can guess there is no equivalent in other places.

I would highly recommend you to give it a look if you are looking for opportunities abroad. If you wish to go the US, you can apply at any level of education (Ba / Ma / PhD / postdoc / ..). A caveat: you’ll have to compete not just with other mathematicians, but with lawyers, journalists, biologists, etc. The application procedure is hence quite distinct from others you may have participated in, as you’ll have to convince a jury of non-mathematically inclined people. Luckily (or unfortunately, depending on your view), your education or research plans are not their only main concern. They are equally, if not more, interested in how Belgian-American relations will be improved by you going there. Quid pro quo…

In any case, I managed to obtain both of them, which means that I will be going to the US for one year, together with my wife and kids. To be precise, I will be joining Jacques Verstraete‘s research group at University of California, San Diego. Everyone that has been to San Diego tells me it is a fantastic place, so I’m looking forward to confirm this sentiment. There are some fantastic mathematicians at UCSD and I will no doubt learn a lot in this year.

At UCSD, I’ll be doing some extremal combinatorics, using my background in finite geometry. This is a direction I have been interested in since my master thesis and which I have been getting back into recently. As some sort of preparation, I spent a week in Lancaster where I have been attending the 29th British Combinatorial Conference. The conclusion is that there are still plenty of lower bounds in extremal combinatorics that could be improved using constructions from finite geometry!

For now, there are a lot of administrative and logistical hoops that I have to jump through, but I hope to be up-and-running by the middle of October. I will keep you posted whatever interesting things I come across on US soil!

Three short announcements

Three notable events in the very near future:

• On May 25 we will be hosting the second edition of the Dutch-Belgian Colloquium in Combinatorics at VUB. Aiming to give young researchers a platform, which was sorely lacking due to COVID, we are glad to have several talks on a variety of topics.
  The event will be a hybrid one, as is fashionable nowadays. For more information, including registration (which is free!), schedule and book of abstracts I refer you to the website https://dutchbelgiandiscretemathseminar.weebly.com/.
  
• The very same day I will be defending my PhD thesis titled Finite Geometry and Friends: tilings in abelian groups and combinatorics in spherical publicly. You can find the flyer below. This will also be a hybrid event, so shoot me a message if you want to follow along online. In a few weeks, I will also make the thesis available online for those who lack night-time reading material.
  
• Lastly I will be giving a plenary talk at the Student Symposium in Combinatorics on pseudorandom graphs and finite geometry. The talk will be aimed at students (hence the conference’s namesake). I’m honored by the invitation for what I believe to be a great initiative. There’s a lot of catching-up to do for young mathematicians in these post-covid times. Or should I say inbetween two winters of exponentially growing infection numbers? Nevertheless, check out the website if you’re interested. There’s speakers from all domains of combinatorics, so you are guaranteed to learn something new, either new faces or new mathematics!

flyer-phd-eng-sam-mattheusDownload