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 over the finite field . We will denote the points by homogeneous coordinates and the lines by dual coordinates . This means that the line has coordinates . Two points and of are orthogonal iff . 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 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 and are orthogonal iff the line contains the point iff the line contains the point . In a way, we have identified the point with the line . A point is self-orthogonal iff lies on . The structure of the set of self-orthogonal points relies heavily on the parity of 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 . Its set of vertices is the set of points of . 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 , and independently by Brown , 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 of this graph. Geometrically, an independent set in the polarity graph corresponds to a set of points in such that the lines with which they are identified, do not intersect this set.
Jason Williford showed in his thesis  that . He and others have further investigated this problem and the best known results on the lower and upper bound for up until now were
Remark that the gap in the case when is an even square is only 1. Also remark the particularly strange bound when is an odd non-square.
We provide constructions showing the following improved lower bounds:
We will discuss some of the ideas underlying the constructions.
In the case when is an even square, the lower bound is given by the construction of a maximal arc of degree that is also an independent set. A maximal arc of degree is a set of points of such that every line contains either or points. Therefore, it seems natural to look for a similar construction in the case when is an even non-square, and indeed, we managed to construct a maximal arc of degree 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 is odd, we used the following idea. We will construct an independent set as the orbit of a certain subgroup of the automorphism group of (how this group looks like, does not matter much for now). The advantage is the following: normally, when we consider a set of vertices 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 is an orbit of a subgroup , this can be checked more efficiently. In particular, consider any vertex , then it is sufficient to check the following condition for this single vertex:
has no neighbours in .
To see why this is sufficient, suppose for the sake of contradiction that there exists a vertex that has a neighbour . As is an orbit, it follows that for some . But then after applying to the edge , we see that is adjacent to , a contradiction with property .
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 can still exist. The reason for square is that we can consider the Baer subplane and use this to find good subgroups. Moreover, different subgroups can be chosen, depending on . We gladly refer to the article for more details.
 W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285.
 P. Erdős , A. Rényi, On a problem in the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 7A (1962), 623-641.
 J. Williford, Constructions in finite geometry with applications to graphs, Ph.D. thesis, University of Delaware (2004).