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.

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

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 q-analogues. In both of the mentioned results, the symmetric group is clearly present and we will focus our attention to this group first.

Continue reading
Tagged , , | Leave a comment

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 \Omega = \{a,b,c,d,e\}, then a natural incidence geometry on this ground set has as elements all subsets of \Omega and containment as the incidence relation. The type of an element is the size of the subset. Then the set \{ \{a\},\{a,d,e\}\} is a flag of type \{1,3\} in this geometry, just as \{\{b,c\},\{b,c,d\},\{a,b,c,d\}\} is one of type \{2,3,4\}.

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 \Omega. We could investigate the flags of type \{2\}, which boils down to the Johnson scheme J(5,2), where all possible relations between two flags of type \{2\} are R_i = \{(\omega_1,\omega_2) | \omega_1 \cap \omega_2 = i\}, i = 0,1,2. 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 \mathbb{F}_q^n. When considering only k-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 q-Johnson scheme J_q(n,k), as it is a q-analog. Again, when we want to consider flags of subspaces, things quickly get more complicated.

In general, the symmetry of the algebras J(n,k) and J_q(n,k) 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 [n] = \{1,\dots,n\}. The remarkable strength of building theory is that it allows the exact same result to be transferred to flags of subspaces in \mathbb{F}_q^n!

The result for flags of subsets of [n] = \{1,\dots,n\} states that the association scheme (or adjacency algebra) is commutative only for flags of size one, hence only for the Johnson scheme J(n,k), for some 1 \leq k \leq n. 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 Sym(n), n \geq 3 generated by the adjacent transpositions S =  \{s_i = (i,i+1), 1 \leq i \leq n-1\}. It can be checked that the relations between the generators are s_i^2 = 1, s_is_{i+1}s_i = s_{i+1}s_is_{i+1} for 1 \leq i \leq n-2 and s_is_j = s_js_i if |i-j| > 1 . Moreover, it turns out that this is presentation for Sym(n). We can now reconstruct the association scheme J(n,k) as the association scheme with relations the orbitals (orbits on pairs) of Sym(n) on the k-subsets of [n]. In fact, there is quite some redundancy there, as we do not need the full group Sym(n), but can restrict ourselves to the stabilizer of a single k-subset. One can easily see that for the k-subset \{1,\dots,k\}, the stabilizer is the subgroup generated by S \backslash \{s_k\}. Now this subgroup is a Young subgroup Sym(k) \times Sym(n-k).

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 [n] (a set of non-negative integers summing to n). In the example above, this is the composition \{k,n-k\}. The commutativity of the association scheme is encoded in the induction of the trivial character \mathrm{ind}^{Sym(n)}_H(1_H) of the Young subgroup H to Sym(n). It is commutative if and only if this character is multiplicity-free, i.e. every irreducible character of Sym(n) appears with multiplicity 0 or 1 in the decomposition. Here comes the kicker: the irreducible representation of Sym(n) are parametrized by partitions (compositions with the parts ordered in non-decreasing way) of [n], and the multiplicities of \mathrm{ind}^{Sym(n)}_H(1_H) 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 \lambda = \{\lambda_1,\dots,\lambda_k\} of [n], i.e. ordered such that \lambda_1 \geq \dots \geq \lambda_k, you can picture its Young tableau, a collection of n left-aligned boxes with \lambda_1 in the first row, \lambda_2 in the second row and so on. Now given another composition \mu = \{\mu_1,\dots,\mu_l\} you want to fill in the boxes of Young tableau above with \mu_1 times the number 1, \mu_2 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 K_{\lambda \mu}.

Since \mathrm{ind}^{Sym(n)}_H(1_H) = \sum_{\lambda} K_{\lambda \mu}\chi_{\lambda}, where \chi_\lambda is the irreducible character corresponding to the partition \lambda and H is a Young subgroup corresponding to the composition \mu, we need to find out for which \mu there exists \lambda such that K_{\lambda \mu} > 1. When \mu has only two parts, it is easy to see that this can never occur. However, when \mu has at least three parts, it is a nice exercise to see that there is always at least one composition \lambda such that K_{\lambda \mu} > 1.

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.

Posted in Geen categorie | Tagged , | 1 Comment

Finite Geometry and Friends 2019, the wrap-up

Last week our summer school in Brussels came to an end. I was very happy with the outcome: over 40 participants from 15 countries, a wonderful set of lectures and some refreshing contributed talks. And unless everyone lied to my face, I have the feeling that the participants had a good time as well.

For those of you that could not make it: the lecture notes and slides of the contributed talks will be posted online in the near future. Aida, Nico, Francesco and Geertrui are making the last corrections, removing some typo’s and perhaps adding some lines. We hope to put everything online after the summer (as even lecturers also deserve vacation), so a little patience will be required.

Finally, big thanks to my supervisor Jan De Beule, for wanting to go along the idea of our very own summer school in Brussels, and of course thanks to the aforementioned lecturers as well, as the effort they put into the notes and presentations was very clear.

See you in a few years at another summer school hopefully!


Posted in Geen categorie | Tagged | Leave a comment

Multiplicative tilings in finite vector spaces

Some time ago, I came across an article due to Iosevich, Lai and Mayeli titled Tight wavelet frame sets in finite vector spaces. I’m not exactly sure why the suggestion system of ScienceDirect thought I might like this article from Applied and Computational Harmonic Analysis, but I was intrigued. For one, because Ingrid Daubechies, the person commonly accredited with the development of wavelets for applications, is an alumnus of Vrije Universiteit Brussel, where I am currently at. Secondly, finite vector spaces is something I am familiar with, so why not take a look?

It turned out that there was a particular problem in the paper posed as an open question on the very last page:

Question #1. Does there exist tight frame wavelet sets when q \equiv 1 \pmod{4}?”

I managed to solve this question, and I will record it here, mainly for my own convenience. The what and why of tight frame wavelet sets is not very important, the most important aspect is the fact that someone from a finite geometrical background can contribute to problems in harmonic analysis. We have more in common than we think!

Going through the paper, it turns out that to solve this problem, all one needs is a multiplicative tiling (X,A) of \mathbb{F}_q^2, i.e. a set of q-1 non-zero vectors X \subseteq \mathbb{F}_q^2 and a set of q+1 automorphisms A \subseteq \mathrm{GL}(\mathbb{F}_2^q) such that every non-zero vector in \mathbb{F}_q^2 can be uniquely written as \phi(x), x \in X, \phi \in A. This is a ‘multiplicative’ analogue of translational tilings which consists of two sets of vectors X,Y such that every vector in \mathbb{F}_q^2 can be uniquely written as x+y, x \in X, y \in Y.

When q \equiv 3 \pmod{4} the authors took X to be a set of representatives of the circles defined by x^2+y^2=r, r \neq 0, which are the orbits of \mathbb{F}_q^2 under a group of rotations (which can be written down explicitly). The problem with q \equiv 1 \pmod{4} is that the circle with radius zero consists of more points than just the origin, as -1 is a square!

This problem with squares and non-squares appearing in computations over finite fields is very common and working around it often uses a solid geometrical background. In fact, the obstacle here can be circumvented by considering ellipses defined by x^2-ny^2=r instead, where n is a non-square in \mathbb{F}_q. One can do the computations and see that after some adaptions, everything works out just fine. However, there is an even more elegant approach to this construction, which is the one we will show.

Instead of considering \mathbb{F}_q^2, we can consider the isomorphic vector space \mathbb{F}_{q^2}. We will make the isomorphism explicit by constructing the field extension \mathbb{F}_{q^2} as \mathbb{F}_q[X]/(X^2-n) (where n is the same non-square as before). In this way, if i \in \mathbb{F}_{q^2} such that i^2=n, we can identify every element (a,b) \in \mathbb{F}_q^2 with a+bi \in \mathbb{F}_{q^2}. In this bigger field, we can consider the standard norm function N: \mathbb{F}_{q^2} \rightarrow \mathbb{F}_q, N(a+bi) = (a+bi)(a+bi)^q = a^2-nb^2.

Now take X to be a set of q-1 points, one from each of the norm curves N(x)=r, r \neq 0, and A the set of q+1 points with norm 1 (which is in fact a subgroup). Then it is immediately checked that (X,A) is a multiplicative tiling set, and these computations are reduced to one-line proofs, as opposed to the work that is necessary when working in \mathbb{F}_q^2 (which takes 2 pages in the aforementioned paper). Finally, adapting this multiplicative tiling into a tight wavelet frame set works exactly the same as in the paper, which completely answers their question.

Posted in Geen categorie | Tagged , | Leave a comment

The return of the polarity graph

Every now and then, I seem to circle back to a tantalizing question in graph theory: the independence number of the polarity graph. Let’s recall this graph, which is defined in terms of projective planes and their polarities: let \pi be a finite projective plane of order q (not necessarily a prime power!) and \perp a polarity. Then the polarity graphs has the points of \pi as vertices and two distinct vertices x and y are adjacent iff x \in y^\perp. By definition this is indeed an undirected, loopless graph, but depending on \pi and \perp, this graph can behave very differently. The most-discussed polarity graph is probably the one where \perp has the least possible number of absolute points, i.e. points incident with their image under \perp. This minimum is q+1, by a classical result due to Baer.

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

Proofs and papers in the 21st century

It’s strange how mathematics has evolved over the last few centuries, but the way research mathematics is presented hasn’t changed in a meaningful way. Sure, since the advent of internet, it is easier and faster to propagate your work to the mathematical community, but the form in which this happens seems quite archaic, considering the tools available nowadays. What I mean is the following: since the 15th-16th century, people were able to spread their ideas to an audience broader than ever before, due to the invention of printing. This practice of putting your mathematical research into print has carried all the way to today, with the only difference that printed journals are nowadays also available online. Although the opportunities offered by the online medium are enormous, it seems to me that no meaningful changes have been made since the transition from paper to screen. One of the few features is that you are now able to quickly click-through to references and citations using hyperlinks (which is a feature that actually could use improvement in my opinion, see later). Other than that, the linear structure of text on paper (read from top to bottom) has been preserved, as is the lack of interactivity.

Although I realize that many mathematicians like to complain that there is no need to change what works (I also prefer blackboards to smartboards for teaching purposes, I admit), I would like to propose a thought experiment on how research mathematics is presented and how it could be improved. One of the first links you will stumble upon in a quick Google search is Leslie Lamport‘s “How to write a 21st century proof” (pdf). In this note, Leslie proposes a new style of proofs, which admittedly, seems a bit extreme the first time you come across it. However, extreme does not necessarily imply bad or useless. Let me give you some motivation why change is not always bad. As Leslie puts it himself in “How to write a proof”, an earlier version of the aforementioned essay:

Mathematical notation has improved over the past few centuries. In the
seventeenth century, a mathematician might have written

There do not exist four positive integers, the last being greater than two, such that the sum of the first two, each raised to the power of the fourth, equals the third raised to that same power.

How much easier it is to read the modern version

There do not exist positive integers x, y, z, and n, with n > 2, such that x^n+y^n=z^n.

Surely, he has a point. The added value of using notation and symbols to shorten the language in which you want to convey your mathematical idea cannot be understated. It is this same evolution of natural language to a more structured language that Leslie (and I) would like to see in proofs. I will refer to his Section 2 for an explicit example of how he proves things nowadays.

Personally, my frustration with the current limitations of static pdfs arose while reading a paper, and having to scroll all the way down for the nth time to check a reference, only to scroll all the way up. I’m sure this has to be a familiar feeling for other people. It made me reflect on the shortcomings of the current state, and try to think of some improvements, so here’s two improvements which should be feasible in the near future.

References on hover

The first suggestion is related to my own frustration. It is already possible to click through on references in recent articles, however, wouldn’t it be nice to have a little pop up box appear when hovering over an article in text. In the last few years, YouTube introduced a similar concept for their videos, allowing you to hover the mouse over the timeline at the bottom of a video and see a preview of what will be shown at that specific time. It should not be that hard to replicate a similar ‘textbox-on-hover’ when hovering over a reference, no?


I started thinking more about the way a paper is presented in a pdf and came across the idea of hypertext, or what is apparently called accordions. A Google search revealed that Leslie Lamport had had this idea when I was still in diapers. I will show a rough sketch of a similar example to demonstrate the merit of the idea. It gives the opportunity for quick first readings, skip things you already know or understand but also delve into proof steps that might be unclear. You can write for several audiences (e.g. students and more advanced researchers) at the same time while still catering to their respective needs (e.g. students might need more explanations or motivations on why and how certain things are done). However, there is also a certain drawback to this method. It forces authors to more concise and precise, which is not necessarily a bad thing, but surely there’s a lot more work involved. Secondly, opinions on the depth of detail that should be given are inevitably going to differ so clear guidelines on just how much should be explained might not be feasible. It might improve a lot of texts, but new technology will not suddenly solve the problem of badly-written papers as this is a classical PEBCAK problem.

Without further ado, let me demonstrate the simple example which I recently needed in my own research. The implementation is very rough and also doesn’t allow for LaTeX typesetting, so I’ll have to ask to use your imagination a little. Ideally, there would also be some form of hierarchy as described in Leslie’s paper, but again my limitations with HTML prevent me to show this. In short, we want to prove that a certain group acts transitively on a set of points in the affine plane \mathrm{AG}(2,q), q an odd prime power, which could be an exercise in an undergraduate course.

Posted in Geen categorie | Tagged , | Leave a comment

G2R2: the aftermovie

Wow. As I was interviewed before camera, I figured that there would be some footage afterwards, but the quality of this clip is much more than I expected. All credit goes to the Novosibirsk State University and their wonderful team. It deserves to be shared, so here it is, starring yours truly!


Posted in Geen categorie | Tagged , | Leave a comment

G2R2: week 2

Onto the second week.

The first week consisted of six days of classes and conferences talks, for which we were rewarded with one free day, including a visit to the local zoo. Here, you have the opportunity to see a liger (lion-tiger hybrid) and supposedly, a liliger has also been born here! Although it sounds intriguing, the actual animal resembled Garfield more than anything, being just a big, fat cat. Maybe they overfeed, maybe genetics are at play, who knows.

liger at novosibirsk zoo

The liger at Novosibirsk Zoo

In any case, our brains got some well-deserved rest, which was needed for the upcoming classes.

Continue reading

Posted in Geen categorie | Tagged , | Leave a comment

G2R2: week 1

Well, I severely overestimated the available time I would have the last few weeks to write a recap. I’ll do it anyway, but not so fresh from memory. Since both weeks contained a lot of material, I will split it in two posts.

The first week had lectures from Roman Nedela and Sasha Mednykh, who replaced a sick Gareth Jones. Personally, these lectures were an added bonus on top of the lectures of the second week, which were my real goal, as they lie much closer to my field of research. But, one can always pick up interesting ideas from another domain, so of we went.

Continue reading

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