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 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, is the following. Consider the classical finite projective plane and an orthogonal or pseudo polarity , depending on whether is odd or even. The vertices of are the points of (or equivalently, the lines) and two vertices and are adjacent iff .
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 and is a map mapping edges to edges. We do not require anything on non-edges. When we talk about endomorphisms, and an endomorphism is proper if the image is a proper subgraph of . 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 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 , it is -colourable and has clique number , and vice versa. For example, any bipartite graph is homomorphically equivalent to .
Another example is the cycle . 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 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 large enough, so the appropriate question was: ‘is 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 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 are adjacent if , where is the polarity. One can obtain the parameters of the srg from the parameters of the design. In the case of , of the points are absolute, which give rise to loops as for an absolute point . So in a sense, we are loops away from being strongly regular. (Does there exist notion of strongly regular graphs allowing loops?)
To see that is a core, we will reason by contradiction. So suppose we can map two non-adjacent vertices 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 .
Proof. Any two non-adjacent vertices have a unique common neighbour: the lines and intersect in a point, say , which is not equal to or . Take another neighbour of , then we can repeat the argument to find a common neighbour of and so that induces a subgraph .
The image of any subgraph in should again be , as is a core. However, if we map two non-adjacent vertices to a single vertex, we could consider a containing these two and find a contradiction. We conclude that 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!