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

## Polarity graphs are cores!

Recently, I managed to solve what was one of the first research questions I formulated myself. After I obtained my degree of Master in Mathematics, I went to the Discrete Mathematics Days in Barcelona. Partly because discrete mathematics is my field of interest, but mostly it was a good excuse to return to Barcelona after I had spent a year as an Erasmus exchange student there. I arrived with only some knowledge of the topics I encountered in my master’s thesis: some extremal graph theory and links to finite geometry, with the polarity graph $ER(q)$ in the spotlight. I already discussed this graph in a previous blog post, but since I promised I would write in more detail about this graph, and I didn’t (yet), let’s reiterate the definition of this graph.

The Erdős-Rényi graph, or polarity graph, $ER(q)$ is the following. Consider the classical finite projective plane $\mathrm{PG}(2,q)$ and an orthogonal or pseudo polarity $\perp$, depending on whether $q$ is odd or even. The vertices of $ER(q)$ are the points of $\mathrm{PG}(2,q)$ (or equivalently, the lines) and two vertices $x$ and $y$ are adjacent iff $x \in y^\perp$.

As I sat in the conference and listened to speakers explain their research, I tried to pick up some problems along the way as a starting point for my PhD. One of these talks was by David Roberson on cores of strongly regular graphs. The problem is the following: a homomorphism between two graphs $G$ and $H$ is a map $V(G) \rightarrow V(H)$ mapping edges to edges. We do not require anything on non-edges. When $G=H$ we talk about endomorphisms, and an endomorphism is proper if the image is a proper subgraph of $G$. A core is a graph with no proper endomorphisms. Every graph is homomorphically equivalent to a unique core, so these graphs play an important role.

As an example, the complete graph $K_n$ is a core, since in order to homomorphically map vertices to a proper subgraph, we need to map two vertices to a single one. But any two vertices are adjacent so they should always be mapped to adjacent vertices, contradiction. One can check that if a graph is homomorphically equivalent to $K_n$, it is $n$-colourable and has clique number $n$, and vice versa. For example, any bipartite graph is homomorphically equivalent to $K_2$.

Another example is the cycle $C_5$. You can try and see for yourself that there exist no proper endomorphisms (try to map two non-adjacent vertices to the same vertex and see what happens).

David showed that strongly regular graphs are either cores or have complete graphs as cores, answering a question by Cameron and Kazanidis. As the polarity graph $ER(q)$ is close to a strongly regular graph, I wondered if the same held true. In this case, the clique number is 3, while the graphs are not 3-colorable for $q$ large enough, so the appropriate question was: ‘is $ER(q)$ a core?’. The title kinda gives away the answer: yes it is! After finishing some other projects, I had some time to think about this question and the proof turned out to be relatively simple. I guess sometimes it takes a year to notice the obvious?

Before I give the proof, I should probably explain why $ER(q)$ is close to being strongly regular. Symmetric designs with polarities give rise to strongly regular graphs if either all points are absolute, or none are: take the vertex set to be the point set of the design and two vertices $x,y$ are adjacent if $x \in y^\perp$, where $\perp$ is the polarity. One can obtain the parameters of the srg from the parameters of the design. In the case of $ER(q)$, $q+1$ of the $q^2+q+1$ points are absolute, which give rise to loops as $x \in x^\perp$ for an absolute point $x$. So in a sense, we are $q+1$ loops away from being strongly regular. (Does there exist notion of strongly regular graphs allowing loops?)

To see that $ER(q)$ is a core, we will reason by contradiction. So suppose we can map two non-adjacent vertices $x,y$ to the same vertex (these should exist since we are mapping to a proper subgraph). We need the following lemma.

Lemma. Any two non-adjacent vertices are contained in a subgraph $C_5$.
Proof. Any two non-adjacent vertices $x,y$ have a unique common neighbour: the lines $x^\perp$ and $y^\perp$ intersect in a point, say $w$, which is not equal to $x$ or $y$. Take another neighbour $z$ of $x$, then we can repeat the argument to find a common neighbour $v$ of $z$ and $y$ so that $xwyvz$ induces a subgraph $C_5$.

The image of any subgraph $C_5$ in $ER(q)$ should again be $C_5$, as $C_5$ is a core. However, if we map two non-adjacent vertices to a single vertex, we could consider a $C_5$ containing these two and find a contradiction. We conclude that $ER(q)$ is indeed a core.

One can make the same argument for other types of polarity graphs, where the plane does not need to be classical or the polarity can be of another type. In any case, what is important is that any two non-adjacent vertices are contained in subgraph that is a core. Perhaps this idea has more applications (perhaps not), but in any case, I am happy that I managed to solve my one of my very first research questions!