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!

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

Large minimal multiple blocking sets

That’s four adjectives to describe the topic of my most recent preprint with Anurag Bishnoi and Jeroen Schillewaert. Although the object itself isn’t that hard to grasp, it doesn’t quite roll off the tongue very well. It deals with the following problem, for which we will start explaining adjectives right to left.

Consider a finite projective plane \Pi of order n. A blocking set of \Pi is a set of points such that every line contains at least one point. A t-fold blocking set, 1 \leq t \leq n+1, is a set of points such that every line contains at least, you guessed it, t points. If we do not wish to specify the number t, we can talk about multiple blocking sets. A t-fold blocking set is minimal if through every point of the blocking set there exists a line intersecting the set in exactly t points. Lastly,  large just refers to the size.

In general, most of the research in blocking sets has been occupied with how small a (t-fold) blocking set can be. This is probably the most natural question when first encountering this object. However, one can also look at the other end of the spectrum and ask how large it can be. Clearly, a blocking set has size at most n^2+n+1, so for this question to make sense, people have introduced the notion of minimality. It is equivalent to saying that we cannot remove any point of the blocking set without destroying the t-fold blocking property, so it is indeed minimal w.r.t. to set containment.

In this way, Bruen and Thas proved in 1977 that the size of a minimal blocking set is upper bounded by n\sqrt{n}+1. In the preprint, we managed to generalize this upper bound from blocking sets to t-fold blocking sets, and showed that equality can only occur in some simple examples. Furthermore, it contains a variety of other results and some open questions at the end in which finite geometry people might be interested. So other than copy-pasting these results, I’d like to mention the technique we used to obtain the upper bound and how we got there.

In fact, the main technique, which is the expander mixing lemma, has already been elaborated on by Anurag in his blog, in which you can already see the upper bound appearing. It is a tool in graph theory, based on eigenvalue techniques, that is widely applicable (one can check the preprint for references thereof). However, there is little added value in retelling the same story as Anurag did, so perhaps the motivation is more interesting.

He told me he was first interested in this lemma for the following idea. It is an open question whether there exists a finite projective plane containing two disjoint unitals. A unital is the unique largest minimal blocking set, so perhaps if we had two disjoint unitals, we could create a very large minimal 2-fold blocking set, perhaps too large (i.e. in contradiction with upper bounds). However, such upper bounds were non-existent, which immediately gave the motivation for this work (for which he did most of the groundwork).

Now, if you skimmed through the paper, you will probably see that there is no mention of disjoint unitals anywhere. This is for the following reason: two disjoint unitals form a minimal 2-fold blocking set if and only if every tangent to one unital is tangent to the other. Therefore, these upper bounds can’t say anything about the problem of disjoint unitals in general. However, using them, there is a little bit of information on the number of shared tangents we can extract in the following way. Whether or not this is useful is a question for the experts.

The upper bound for a minimal 2-fold blocking set in a projective plane of order n is

\frac{1}{2}n(\sqrt{8n-7}+1)+2.

Clearly, two disjoint unitals cannot share all tangents, as this would imply a minimal 2-fold blocking set of size 2(n\sqrt{n}+1) which is strictly larger than the upper bound above. So suppose they share all but one. Then there exists a point x_1 on the first unital and a point x_2 on the second, such that their respective tangents are secant to the other unital. Therefore, we can remove both these points and obtain a 2-fold blocking set, which is again minimal, as all other tangents were shared. However, one can compute that the size of this set is again larger than the upper bound. This means that two disjoint unitals cannot share all tangents but one. One can do the same for all but two, all but three, up to all but \sqrt{n}+1. Therefore, we obtain the following fact.

Proposition. Two disjoint unitals have at least \sqrt{n}+1 non-shared tangents.

Although one can do better with direct methods, I still liked this fact as an example of a connection between two questions that are unrelated at first sight and how an idea for one problem can lead you to other unexpected and uncharted areas.

 

 

Posted in Geen categorie | 1 Comment

A conference and a summer school

Phew, what a month. Unfortunately, I didn’t have the time to write a mathematical blog post. However, in between making, supervising and grading exams, I have had two great weeks in the month of June. First, I was able to go to Fq13, where I could meet new people, learn new mathematical concepts, listen to great mathematicians, and a give a talk myself! My slide, and others, can be found on the conference website. I think it went rather well for a first talk at an international conference. In September, I will give the same talk in Irsee, hoping that someone there might have some intuition on how to attack the problem I proposed. The problem is related to the weak cylinder conjecture, for those who have a background in finite geometry and would be interested in it.

Conference photo Fq13

Conference photo of Fq13, bonus points for finding me.

Then last week, there was a wonderful summer school at the University of Sussex, Brighton. Fatma Karaoglu took most of the organisation upon her shoulders and I have to say, she did a great job at it! The lectures were provided by Peter Cameron (who also gave a short review of the summer school), Jef Thas, Simeon Ball and Anton Betten. For those who couldn’t attend, the lectures were recored (although sometimes only partially, as lecturers forgot to press the ‘Record’ button at times), and the lecture notes should be available on the website. Peter gave very interesting lectures, starting from the innocuous-looking friendship theorem, but ultimately classified the polar spaces with
3 points on each line, using mostly graph theory! For the details, I will refer to his notes. Another very interesting lecture series, was Simeon’s.  I saw his paper ‘On planar arcs’ with Michel Lavrauw appear earlier this month, and put it high on my ‘To Read’ list. As of now, I got a headstart as he explained most of the content and the building up to the results he obtained in this paper. The other two were obviously fascinating as well, but were perhaps farther from my research interests than the two I highlighted.

Photo Summer School Brighton

Participants of the Summer School (a lot more visible in the green shirt now).

In any case, I have had a great time, both mathematically and with the people who attended these activities. I hope to see a lot of them again in September in Irsee!

Posted in Geen categorie | Leave a comment

Notes of the seminar ‘On the slice rank of functions’

Last week, I gave a seminar on the slice rank of functions (probably one of many concerning that particular subject since last year). The motivation being mainly that I, together with my advisors Jan De Beule and Philippe Cara, wanted to understand this method better, so what better way to understand something than to talk about it with fellow mathematicians?

I want to write down some of the material I presented on the blackboard, primarily to have a reference and some notes for myself, but perhaps they can also give someone else a better understanding of the ideas and concepts regarding this topic. I have not seen the visual interpretation of the different notions of rank is anywhere else, so this might be interesting as well. Let me know if this has helped you or if something needs more explanation!

Background

Last year, the combinatorial world was stunned by a series of results by Croot-Lev-Pach, Ellenberg-Gijswijt regarding arithmetic progressions in certain groups. I will not try and give an complete account of these, as several sources around the web have done so already quite extensively (blog post by Anurag Bishnoia rendition of the proof by Doron Zeilberger and references on Gil Kalai’s blog).  As an indicator of the gravity of these two results, both have been published in the Annals of Mathematics in the beginning of this year. Instead, I will try to elude the idea of ‘slice rank’ of a tensor, as was defined by Terry Tao in his reformulation of the Ellenberg-Gijswijt proof. I will try to indicate where the idea might have come from and how one can understand it in a sort of geometrical way. Most, if not all, of the theory can be developed for general tensors (see again Terry’s blog), but we will restrict ourselves to to a special case, which we will explain in the next paragraph. The reason for this is that I find the concepts easier to explain in this specific setting. So without further ado, let’s get on with it.

Continue reading

Posted in Geen categorie | Tagged , | Leave a comment

On the independence number of the Erdős-Rényi graph.

Recently, my first article has appeared online. Therefore, it seems like an opportune moment to show some of the ideas used. I will however, go about it in the opposite way: I will only briefly define the graphs under consideration without going into many details and present the results from the paper. The graph that is mainly discussed, the Erdős-Rényi polarity graph (not to be confused with the random graph) deserves some attention of its own, and we will do so in a later post. There are several equivalent ways to define this graph. We will do it in the following way.

Construction of the graph

Consider the projective plane \mathrm{PG}(2,q) over the finite field \mathbb{F}_q. We will denote the points by homogeneous coordinates (x,y,z) and the lines by dual coordinates [a,b,c]. This means that the line aX+bY+cZ=0 has coordinates [a,b,c]. Two points (x,y,z) and (a,b,c) of \mathrm{PG}(2,q) are orthogonal iff ax+by+cz=0. This definition corresponds to the classical notion of orthogonality in Euclidean geometry, but there are some important distinctions to be made. For example, a point in \mathrm{PG}(2,q) can be orthogonal to itself. In this case the point is called self-orthogonal. Another way of viewing this definition is by using dual coordinates. Two points (x,y,z) and (a,b,c) are orthogonal iff the line [x,y,z] contains the point (a,b,c) iff the line [a,b,c] contains the point (x,y,z). In a way, we have identified the point (x,y,z) with the line [x,y,z]. A point is self-orthogonal iff (x,y,z) lies on [x,y,z]. The structure of the set of self-orthogonal points relies heavily on the parity of q. We will explore this phenomenon more in depth later on, but for now, it explains why we have to treat these cases separately.

We are now in a position to define the Erdős-Rényi graph ER(q). Its set of vertices is the set of points of \mathrm{PG}(2,q). Two distinct vertices are adjacent iff they correspond to a pair orthogonal points. Remark that this definition is indeed symmetric and gives rise to a simple graph. In the remaining, we will not make the distinction between points of the projective plane and the vertices of the graph, it will be clear from the context what we mean.

Known bounds on the independence number

This graph was constructed in the 1960’s by Erdős and Rényi [2], and independently by Brown [1], to solve a question in extremal graph theory. Since then, the graph has been used in several applications. More recently, it became a subject of study itself. Benny Sudakov posed the question of determining the independence number \alpha(ER(q)) of this graph. Geometrically, an independent set in the polarity graph corresponds to a set of points in \mathrm{PG}(2,q) such that the lines with which they are identified, do not intersect this set.

Jason Williford showed in his thesis [3] that \alpha(ER(q)) = \Theta(q^{3/2}). He and others have further investigated this problem and the best known results on the lower and upper bound for \alpha(ER(q)) up until now were

\alpha(ER_q) \le \begin{cases} q^{3/2}-q+\sqrt{q}+1 & \mbox{if } q \mbox{ is an even square} \\ q^{3/2}+\sqrt{q}+1 & \mbox{for all } q \end{cases}

\alpha(ER_q) \ge \begin{cases} q^{3/2}-q+\sqrt{q} & \mbox{if } q \mbox{ is an even square} \\ \frac{q^{3/2}}{2 \sqrt{2}} & \mbox{if } q \mbox{ is an even non--square} \\ \frac{q^{3/2}+q+2}{2} & \mbox{if } q \mbox{ is an odd square}\\ \frac{120 q^{3/2}}{73 \sqrt{73}} & \mbox{if } q \mbox{ is an odd non--square} \end{cases}

Remark that the gap in the case when q is an even square is only 1. Also remark the particularly strange bound when q is an odd non-square.

We provide constructions showing the following improved lower bounds:

\alpha(ER_q) \ge \begin{cases} \frac{q^{3/2}}{\sqrt{2}} - q + \sqrt{\frac{q}{2}} & \mbox{if } q \mbox{ is an even non--square} \\ \frac{q^{3/2}-\sqrt{q}}{2} + q + 1 & \mbox{if } q \mbox{ is an odd square and } \sqrt{q} \equiv -1 \pmod 4 \\ \frac{q^{3/2}+3 q}{2} + 1 & \mbox{if } q \mbox{ is an odd square and } \sqrt{q} \equiv 1 \pmod 4 \end{cases}

We will discuss some of the ideas underlying the constructions.

New constructions

In the case when q is an even square, the lower bound is given by the construction of a maximal arc of degree \sqrt{q} that is also an independent set. A maximal arc of degree d is a set of points of \mathrm{PG}(2,q) such that every line contains either 0 or d points. Therefore, it seems natural to look for a similar construction in the case when q is an even non-square, and indeed, we managed to construct a maximal arc of degree \sqrt{q/2} that is also an independent set. By counting the number of lines skew to this arc, one can immediately see that this construction is not maximal. For each point of the arc corresponds to a line skew to the arc under the polarity, so there are points outside the arc for which the identified lines are skew to the arc. Hence, these points could be used to enlarge the independent set. Unfortunately, it is not clear to us how to add more than one point to the independent set in a controlled way.

In the case when q is odd, we used the following idea. We will construct an independent set as the orbit of a certain subgroup of the automorphism group G of ER(q) (how this group looks like, does not matter much for now). The advantage is the following: normally, when we consider a set of vertices I of the polarity graph as a candidate for an independent set, we need to check that every two vertices are non-adjacent. In the case when I is an orbit of a subgroup H, this can be checked more efficiently. In particular, consider any vertex u \in I, then it is sufficient to check the following condition for this single vertex:

u has no neighbours in I \hspace{1cm} (\star).

To see why this is sufficient, suppose for the sake of contradiction that there exists a vertex v \in I that has a neighbour w \in I. As I is an orbit, it follows that u = v^{h} for some h \in H. But then after applying h^{-1} to the edge vw, we see that u is adjacent to w^{h^{-1}} \in I, a contradiction with property (\star).

Now the problem is reduced to finding a good subgroup and orbit. The subgroup has to be large enough to improve the known lower bounds, but not too large such that orbits with property (\star) can still exist. The reason for q square is that we can consider the Baer subplane \mathrm{PG}(2,\sqrt{q}) and use this to find good subgroups. Moreover, different subgroups can be chosen, depending on \sqrt{q} \equiv \pm1 \mod 4. We gladly refer to the article for more details.

Bibliography
[1] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285.
[2] P. Erdős , A. Rényi, On a problem in the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 7A (1962), 623-641.
[3] J. Williford, Constructions in finite geometry with applications to graphs, Ph.D. thesis, University of Delaware (2004).

Posted in Geen categorie | Tagged , , | 3 Comments