## 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!

## 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.

The liger at Novosibirsk Zoo

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

## 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.

## G2R2: first week

So classes have started, leaving very little time for other things. Especially since the lectures are interwoven with conference talks, keeping us busy from 10am to 10pm. Anyway, a quick write-up from the cultural program of the first week.

## Summer conferences in 2018

This year, I was fortunate enough to attend several conferences again. I haven’t written about them, secretly hoping someone else would, but this hope seems to be in vain.

Combinatorics 2018 was great fun, in lovely former casino in Arco, near the Garda lake in Italy. I gave a presentation about some work in progress (still need to work out more details before I post anything about it here), and got some great response. I haven’t had much time implement the suggestions, but it’s definitely high on the to do list. Then I went to Budapest, for Building Bridges II, a conference in honor of László Lovász’ 70th birthday. So far, I have only seen Gil Kalai’s blog post describing some of the presentations. There were some great talks to be found here, among those of Noga Alon, Lex Schrijver, Laci Babai and others. Good news for the people who couldn’t make it: almost all lectures were recorded and can be viewed on the website! It seems however that Babai’s talk is not among those, a shame, as I found it to be one of the highlights of the first day.

One regret is that this last conference took place in the same week as the Symmetry vs Regularity conference in Pilsen. Unlike Laci Babai, who could attend two different conferences in a single week, I had to make a choice. The Dutch saying “choosing is losing” definitely applied here. Probably, the topics in this conference lie closer to my research interests, but I stuck with the other conference for other reasons.

The next few weeks I will however focus again on one of my research interests (that of algebraic combinatorics), in the G2R2 summer school in Novosibirsk, Russia. This three-week event combines a summer school with the G2R2 conference. The G2 conferences are a yearly summer school + conference combination, and this year the topics are Groups, Graphs, Representations and Relations (hence the name). I intend to write a small recap after every week. The first week is dedicated to a cultural program with visits to the Budker Institute of Nuclear Physics and several musea. Other participants went on a hiking tour towards the Altai mountains, but I was a tad too late in registering for this activity (procrastination is not a good habit). The second week, we will have lectures by Roman Nedela and Gareth Jones, although the latter might be replaced by Alexander Mednykh due to personal reasons. Personally, I’m mostly looking forward to the third week, when Akihiro Munemasa and Mikhail Muzychuk will talk about some topics in algebra. You can find a more detailed overview of the topics on the website of the summer school.

Come back in a few days for a recap of the cultural activities!

## Triangle-free induced subgraphs of the unitary polarity graph

That is the long title of an article which is joint work with Francesco Pavese. Last week, I received the news that it has been accepted for publication, my very first publication! In the article, we continue some work that was started in an earlier preprint with Leo Storme, which ironically, is still under review.

I have posted about this topic in an earlier blog post, but I’ll give a quick recap here.

Roughly speaking the question is the following: consider a finite projective plane of order $q$ and a unitary polarity $\perp$ of this plane (see [1] for all about this). A polar triangle with respect to $\perp$ is a triple of points $x_1,x_2,x_3$ such that $x_i^\perp = x_jx_k$ for any triple $i,j,k$ of distinct indices. We are interested in large sets of points such that no triple from this set forms a polar triangle. This is a particular instance of the classical forbidden configuration problem, which has appeared in many forms in the realm of extremal combinatorics.

Using a combination of algebraic graph theory techniques and geometrical constructions, we manage to obtain upper bounds for general projective planes, and lower bounds for the Desarguesian and Figueroa plane, which asymptotically match! It was the first time I got to use eigenvalue interlacing [2] in a new environment, so I’m quite content with the result.

It has been accepted to the European Journal of Combinatorics, but until its actual publication, you can check it out on the arXiv.

References

[1] D. Hughes, F. Piper, Projective planes, Graduate Texts in Mathematics, Springer-Verlag New York-Berlin, 1973.

[2] W.H. Haemers, Interlacing Eigenvalues and Graphs, Linear Algebra Appl.,
226/228:593–616, 1995.

Posted in Geen categorie | Tagged , | 2 Comments

## An extremal problem in projective planes

Some weeks ago, Francesco Pavese and I submitted a preprint to the arXiv, titled ‘Triangle-free induced subgraphs of the unitary polarity graph’. I’ll try to outline what we have done and what is there left to be done.

The problem is an instance of a rather general problem in combinatorics which can be roughly stated as:

“Given a class of objects (perhaps satisfying a certain condition) can we extremize a certain parameter, given that they do not contain certain sub-object?”

Generally, depending on the specific instance of the problem, it is clear whether the extremum we are looking for is a minimum or a maximum. This problem is often called the forbidden configuration problem, and appears quite frequently in extremal combinatorics. Let me give a few examples.

Example 1. Let $H$ be a fixed graph. What is the maximum number of edges for a graph on $n$ vertices, not containing $H$ as a subgraph? This maximum is the Turán number $\mathrm{ex}(n,H)$.

Its more famous sibling, the Ramsey number $R(G,H)$, where $G$ and $H$ are two fixed graphs, can also be seen as a variant of this problem.

Example 2. Consider the class of partial linear spaces of order $(s,t)$: every point is incident with $t+1$ lines and every line is incident with $s+1$ points. We can try to minimise the number of points such that the geometry contains no triangle. The minimum can be found by elementary counting and is $(s+1)(st+1)$. The extremal objects are exactly the generalized quadrangles of order $(s,t)$. In this way, a well-known family of point-line geometries can be seen as the extremizers to this forbidden configuration problem.

Posted in Geen categorie | | 4 Comments