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

Quotient matrices and bases of eigenspaces

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 and be a set of -sets of an -element ground set such that no two are disjoint. Then and the only examples attaining equality are the point-pencils (i.e. all -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 be a -regular graph on vertices and be the smallest eigenvalue of its adjacency matrix. Then

.

If equality is attained, then the characteristic vector of lies in , where denotes the eigenspace corresponding to the eigenvalue (of the adjacency matrix of ).

For example: in the setting of the original EKR result, we construct a graph with vertex set all -sets of the -set, making two -sets adjacent whenever they are disjoint. This graph is commonly known as the Kneser graph. It is a regular graph on vertices of valency . One can show that the smallest eigenvalue is (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 -regular graph with vertex set . Consider a partition such that every induced subgraph on , is a biregular graph and the induced subgraph on every 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 .

Definition The quotient matrix of the equitable partition is the matrix , where is the number of neighbours in a vertex in has.

The key fact is that the eigenvalues of are also eigenvalues of the adjacency matrix of which follows from the fact that eigenvectors can be “blown up”: if is an eigenvector of with eigenvalue , then define the vector by setting , whenever . This vector will also be an eigenvector of the adjacency matrix of (this is a matter of computation).

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

.

The eigenvalues of are , and , which we recall is the smallest eigenvalue! Their multiplicities as eigenvalues of are and (a fact which we will again not prove). Here comes the essence of the technique: since is invertible, the vector is in its rowspace and is hence a lineair combination of eigenvectors corresponding to and . Since we can “blow up” these vectors, this means that the characteristic vector of the family of all sets through the fixed point is also a vector that lies !

Varying the point, we find a set of vectors in , and it is not too hard to show that they are in fact linearly independent and hence form a basis of . 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!

New clique-free pseudorandom graphs

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.

Observations on Schubert varieties and EKR sets

I want to write down some observations I came across while working on the paper I also mentioned in the previous post. It is well known that Erdős-Ko-Rado problems in different context have a rich structure by which one can prove interesting results. My observations seem to point to yet another domain where this richness appears as well. Perhaps this is just a posteriori, meaning that since the maximal EKR families are most of the time very structured, it is no surprise that one can describe them in many nice ways. But it might just so happen that these different points of view could lead to different proofs of the same result. Clearly the latter is interesting as it could serve as a stepping-stone for similar EKR-problems that are still open. I don’t know which situation we are in, and I should emphasize that the further we go in this post, the less I know about the topics I discuss. In fact, it almost seems odd that I have not yet encountered some of these concepts in other papers, or I might have been looking in the wrong direction.

I will be talking mostly about the classical EKR results for subsets and permutations (which I will recall later on), and shortly discuss some -analogues. In both of the mentioned results, the symmetric group is clearly present and we will focus our attention to this group first.

Flags and non-commutative association schemes

Over the past few months, I have been working on some project regarding flags in finite geometries with Jan De Beule and Klaus Metsch. A preprint on this should appear in the near future. In any case, there is plenty of material that does not quite fit into what we did, but seemed interesting nonetheless. Therefore, I’ll post it here.

First of all, we need to recall the definition of a flag in an incidence geometry and its type. There are exact definitions of ‘flag’, ‘incidence geometry’, and ‘type’, but since we consider rather natural geometries, I will not bother to state them. Instead, it suffices to know that a flag is a set of elements in the incidence geometry that are pairwise incident. An example illuminates this best.

Example. Consider the the set , then a natural incidence geometry on this ground set has as elements all subsets of and containment as the incidence relation. The type of an element is the size of the subset. Then the set is a flag of type in this geometry, just as is one of type .

The easiest flags to handle are those of of size one and a lot is known when we are dealing with flags of size one. In the previous example these are just the subsets of . We could investigate the flags of type , which boils down to the Johnson scheme , where all possible relations between two flags of type are . A symmetric and commutative algebra appears when we consider the vector space spanned by the adjacency matrices of these relations, which is called an association scheme.

In our case, we are interested in subspaces of . When considering only -dimensional subspaces, the natural relations depend on the dimension of the intersection of two such spaces. The algebra one derives from this is again symmetric and commutative is often called the -Johnson scheme , as it is a -analog. Again, when we want to consider flags of subspaces, things quickly get more complicated.

In general, the symmetry of the algebras and is easy to see, since the relations on flags of size one themselves are symmetric. Since an algebra of symmetric matrices is commutative, the latter also follows. When we consider larger flags however, symmetry is immediately gone. One can wonder what remains of the commutativity.

In the two cases we mention, this problem is in fact solved (in disguise) by Godsil and Meagher. When we consider not just flags in vector spaces, but also flags in polar and parapolar spaces and other geometries, building theory pops up, and this has been handled by Abramenko, Parkinson and Van Maldeghem, with different methods.

Buildings, or what I understand of it, are a very natural framework to investigate flags in classical incidence geometries. Although we restrict ourselves to spherical irreducible buildings, this class is already rich enough to obtain the results we are interested in. We will focus on the commutativity of the association scheme on flags of subsets of . The remarkable strength of building theory is that it allows the exact same result to be transferred to flags of subspaces in !

The result for flags of subsets of states that the association scheme (or adjacency algebra) is commutative only for flags of size one, hence only for the Johnson scheme , for some . In the article by Godsil and Meagher, this is proven using some character theory. We will sketch a purely combinatorial proof here, based on the combinatorics of compositions and partitions.

Consider the symmetric group generated by the adjacent transpositions . It can be checked that the relations between the generators are , for and if . Moreover, it turns out that this is presentation for . We can now reconstruct the association scheme as the association scheme with relations the orbitals (orbits on pairs) of on the -subsets of . In fact, there is quite some redundancy there, as we do not need the full group , but can restrict ourselves to the stabilizer of a single -subset. One can easily see that for the -subset , the stabilizer is the subgroup generated by . Now this subgroup is a Young subgroup .

This construction holds for the association scheme of flags of any type. For each flag there is a corresponding Young subgroup, and every Young subgroup corresponds to a composition of (a set of non-negative integers summing to ). In the example above, this is the composition . The commutativity of the association scheme is encoded in the induction of the trivial character of the Young subgroup to . It is commutative if and only if this character is multiplicity-free, i.e. every irreducible character of appears with multiplicity 0 or 1 in the decomposition. Here comes the kicker: the irreducible representation of are parametrized by partitions (compositions with the parts ordered in non-decreasing way) of , and the multiplicities of can be computed in a purely combinatorial way depending on these two compositions!

These coefficients are called Kostka numbers, and for our purpose it suffices to know whether they are larger than 1 or not. This becomes rather easy if you know how to compute them combinatorially: given a partition of , i.e. ordered such that , you can picture its Young tableau, a collection of left-aligned boxes with in the first row, in the second row and so on. Now given another composition you want to fill in the boxes of Young tableau above with times the number 1, times the number 2 and so on, in such a way that the rows are non-decreasing and the columns strictly increasing. The number of ways you can do this is the Kostka number .

Since , where is the irreducible character corresponding to the partition and is a Young subgroup corresponding to the composition , we need to find out for which there exists such that . When has only two parts, it is easy to see that this can never occur. However, when has at least three parts, it is a nice exercise to see that there is always at least one composition such that .

The conclusion is that for flags of subsets or subspaces, we never find a commutative association scheme, except for flags of size one. This means that a lot of tools of commutative association schemes will not work anymore for more general flags other techniques are needed to overcome this difficulty.