A sensational Ramsey breakthrough by Domagoj Bradač

Posted on 28 May 2026 by Sam Mattheus

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 r(s,t) > t^{s-2} 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 r(4,t), and inspired recent progress on r(3,t). 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 (p,H) in \mathrm{PG}(n,q) (i.e. p \notin H), order them, and then make two antiflags (p_i,H_i) and (p_j,H_j) adjacent if i < j and p_i \in H_j. It is not too hard to check that this graph is K_{n+2}-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 k hyperplanes could in principle have codimension 1, much bigger than the wishful k), 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 H_s 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 s \geq 5, given that our construction for r(4,t) 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 q = 2, 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!

Posted in Geen categorie | Tagged , , | Leave a comment

More non-opposite flags in finite spherical buildings

Posted on 26 May 2025 by Sam Mattheus

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 B on the arXiv. This work is a natural successor of earlier results by Philipp, Klaus and Jesse Lansdown for type A (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 B 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 A could be readily extended to type B, 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:

Continue reading →
Posted in Geen categorie | Tagged , | Leave a comment

Containers, containers, containers

Posted on 9 April 2024 by Sam Mattheus

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.

Continue reading →
Posted in Geen categorie | Tagged , | Leave a comment

The asymptotics of r(4,t)

Posted on 7 June 2023 by Sam Mattheus

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 r(4,t). In short, we show that r(4,t) = \Omega(t^3/\log^4t), which is just a \log^2t factor shy from the upper bound r(4,t) = O (t^3/\log^2t) proved by Ajtai, Komlós and Szemerédi in 1980. Erdős [1] conjectured that up to logarithmic factors, t^3 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 K_4-free process and obtained r(4,t) = \widetilde{\Omega}(t^{5/2}), 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.

Continue reading →
Posted in extremal graph theory | 2 Comments

Old wine in new bottles

Posted on 23 February 2023 by Sam Mattheus

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 n (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 K_3-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 (n,d,\lambda)-graphs) triangle-free graphs of density \Theta(n^{-1/3}), 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 Q(4,q), q 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 SL(2,q), 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 K_s-free graphs based on the observation that no s+1 vectors can be pairwise orthogonal in an s-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 K_{s-1} subgraphs. When the field size q is odd, one can pick projective points \langle x \rangle depending on whether its evaluation b(x,x) is square or non-square. When q 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 q is odd.

It is unfortunate to realize that Francesco and I extended Parsons’ result to q 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 t of the Turán number of K_{2,t}. His construction relies on a clever ‘folding’ of the polarity graph which was known to be sharp for t = 2. 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 q and t. For example, the construction only works for all t when q 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 K_{2,t}-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?

Posted in extremal graph theory | Tagged , , | 1 Comment

Keeping busy

Posted on 5 August 2022 by Sam Mattheus

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.

Posted in Geen categorie | Tagged , , , | Leave a comment

Plans for the post-PhD life

Posted on 20 July 2022 by Sam Mattheus

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!

Posted in Geen categorie | 5 Comments

Three short announcements

Posted on 23 May 2022 by Sam Mattheus

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
Posted in Geen categorie | Leave a comment

Quotient matrices and bases of eigenspaces

Posted on 8 December 2021 by Sam Mattheus

A major research interest of mine is the investigation of EKR problems in different settings. This type of results is named after the well-known seminal result by Erdős, Ko and Rado on uniform set systems.

Theorem Let n > 2k and S be a set of k-sets of an n-element ground set such that no two are disjoint. Then |S| \leq {n-1 \choose k-1} and the only examples attaining equality are the point-pencils (i.e. all k-sets through a fixed point).

There are plenty of similar theorems in different contexts, where the “no two disjoint” property is replaced by an appropriate notion of “no two far apart”. An almost unreasonably successful technique in this setting (there’s a whole book about it!) is to rephrase the problem in terms of finding the largest coclique in a certain graph and applying the ratio bound. Very often, this will already provide a sharp upper bound.

Theorem (the ratio bound, often attributed to Hoffman and Delsarte).
Let G be a d-regular graph on n vertices and \lambda be the smallest eigenvalue of its adjacency matrix. Then

|S| \leq \dfrac{n}{1-d/\lambda}.

If equality is attained, then the characteristic vector of S lies in E_d \oplus E_\lambda, where E_x denotes the eigenspace corresponding to the eigenvalue x (of the adjacency matrix of G).

For example: in the setting of the original EKR result, we construct a graph with vertex set all k-sets of the n-set, making two k-sets adjacent whenever they are disjoint. This graph is commonly known as the Kneser graph. It is a regular graph on {n \choose k} vertices of valency {n-k \choose k}. One can show that the smallest eigenvalue is -{n-k-1 \choose k-1} (we will not prove this). After a small computation, one immediately deduces the bound in the EKR theorem.

After obtaining an upper bound, the next step would be to classify the maximal examples, which is made possible by the extra information the ratio bound provides. In order to classify maximal examples, it thus makes sense to search for a good description of these eigenspaces.

Sam Adriaensen, my colleague at VUB, told me about a nice technique he used (in work in progress) to find a basis for these eigenspaces. Incidentally, this same technique in a paper by Fallat, Meagher and Shirazi, which he apparently was unaware of! Most likely the idea was already known even earlier, but as it was new to me, I decided to record it here.

The main idea is to use the notion of quotient matrices. This object is already explained in detail in the preprint by Fallat, Meagher and Shirazi mentioned before, but let’s recall its main properties. Suppose you have d-regular graph G with vertex set \Omega. Consider a partition \Omega = \Omega_1 \sqcup \dots \sqcup \Omega_k such that every induced subgraph on \Omega_i \sqcup \Omega_j, i \neq j is a biregular graph and the induced subgraph on every \Omega_i is regular. Such a partition is called an equitable partitition.
Equitable partitions are easily found: consider the partition in orbits by any subgroup of the automorphism group of G.

Definition The quotient matrix of the equitable partition \Omega = \bigsqcup_i \Omega_i is the k \times k matrix Q, where Q_{ij} is the number of neighbours in \Omega_j a vertex in \Omega_i has.

The key fact is that the eigenvalues of Q are also eigenvalues of the adjacency matrix of G which follows from the fact that eigenvectors can be “blown up”: if v is an eigenvector of Q with eigenvalue \lambda, then define the vector \tilde{v} by setting \tilde{v}_\omega = v_i, whenever \omega \in \Omega_i. This vector will also be an eigenvector of the adjacency matrix of G (this is a matter of computation).

In the example of the Kneser graph, we can partition its vertex set depending on whether the corresponding k-set contains a fixed element form the n-set or not. The quotient matrix has the form

\begin{pmatrix} 0 & {n-k \choose k} \\ {n-k-1 \choose k-1} & {n-k \choose k}-{n-k-1 \choose k-1} \end{pmatrix}.

The eigenvalues of Q are d={n-k \choose k}, and \lambda = -{n-k-1 \choose k-1}, which we recall is the smallest eigenvalue! Their multiplicities as eigenvalues of G are 1 and n-1 (a fact which we will again not prove). Here comes the essence of the technique: since Q is invertible, the vector (1,0) is in its rowspace and is hence a lineair combination of eigenvectors corresponding to d and \lambda. Since we can “blow up” these vectors, this means that the characteristic vector of the family S of all sets through the fixed point is also a vector that lies E_d \oplus E_\lambda!

Varying the point, we find a set of n vectors in E = E_d \oplus E_\lambda, and it is not too hard to show that they are in fact linearly independent and hence form a basis of E. In other words, (the characteristic vectors of) the point-pencils are a basis of this space. From here on out, it is again not too difficult (see the Godsil-Meagher book p.123 for the details) to show that there are no other maximal intersecting families in this eigenspace, from which the classification follows.

The crux of the argument is a neat little observation, yet non-trivial facts result from it. I have been able to apply the idea of using quotient matrices in order to find eigenvectors of large matrices myself recently in a slightly different way, with the same motivation. The situation is a bit trickier, so it remains to be seen whether we will fully succeed. Hopefully I will be able to share this soon!

Posted in Geen categorie | Tagged , , | 1 Comment

New clique-free pseudorandom graphs

Posted on 12 May 2021 by Sam Mattheus

It’s been a while since my last post, which appeared just one month before the addition of the newest member to the Mattheus family. I leave it in the middle whether that is just a coincidence or actually the cause of the hiatus.

In any case, today I wanted to discuss my latest contribution on the arXiv titled A clique-free pseudorandom subgraph of the pseudo polarity graph, together with Francesco Pavese. It is not my first article in this direction with Francesco (and hopefully not the last!). In fact, a few years back when we investigated triangle-free subgraphs of polarity graphs here and here, and discussed on this blog here, we briefly considered whether the higher-dimensional generalisation was of any interest. Painfully unaware of the relevance to pseudorandom graphs and Ramsey theory, we concluded that “no, it isn’t that interesting, no point in generalising for the sake of generalisation”. Only to find out a few years later that this would have been a major improvement to the theory of clique-free pseudorandom graphs as shown by by Anurag Bishnoi, Valentina Pepe and Ferdinand Ihringer. C’est la vie.

Continue reading →
Posted in Geen categorie | Tagged , , | 2 Comments