In many of the applications of the lemma in finite geometry, the graph is bipartite, and therefore let’s start by recalling the bipartite version of the expander mixing lemma that I described in my last post.
Lemma 1. Let be a semiregular bipartite graph with degrees and . Let and such that and . Define . Then we have
where is the largest eigenvalue of , is the second largest eigenvalue of in absolute value, and is the total number of edges in .
There are interesting bipartite graphs related to finite geometries, block designs and other combinatorial structures, for which we know the second largest eigenvalue of the graph exactly. For example, the incidence graph (a.k.a. Levi graph) of a finite projective plane of order has eigenvalues (the eigenvalues of a bipartite graph are always symmetric around the origin). And more generally, the eigenvalues of the incidence graph of a – design are . Therefore, applying expander mixing lemma to these graphs can potentially give some nice results in finite geometry. Let’s start with one of the classical results in the area of finite geometry and see how it can be proved using Lemma 1.
A blocking set in a finite projective plane (or in general, any hypergraph) is a set of points with the property that for every line of the plane we have . One of the central problems in the area of finite geometry has been to understand the possible sizes of a minimal blocking set, where a blocking set is minimal if no proper subset of is also a blocking set. If we do not assume minimality, then this problem becomes trivial as you can obtain a blocking sets of any size by adding some points to a given blocking set. The simplest, and the smallest!, example of a blocking set is a line of the projective plane since every two lines intersect each other. This gives us a blocking set of size , which we a trivial blocking set. For a non-trivial minimal blocking set , Bruen and Thas proved the following result, which is one of the main starting points for a systematic study of blocking sets:
Here is a new proof of the upper bound which uses Lemma 1. For each point of there must exist a line such that since otherwise will also form a blocking set, contradicting the minimality of . We can choose a single such line for each point of to get a set of lines in the projective plane with the property that (a) and (b) the number of edges between the sets and in the incidence graph is exactly . The number of points/lines in a projective plane of order is . By applying Lemma 1, taking and defining , we get the following:
We must have since is a blocking set (prove it!) and therefore , which helps us remove the mod sign in the inequality. We get
which simplifies to
Since , we get
Question 1. Can the lower bound on non-trivial minimal blocking sets be proved using eigenvalue methods as well?
The proof above is quite flexible as it can be easily adapted to similar situations, sometimes giving us new results. One such result is about minimal multiple blocking sets that I obtained while exploring the power of this method.
A -fold minimal blocking in a projective plane of order is a set of points with the property that (a) for each line , we have , and (b) through each point , there exists a line with the property that . We will prove that
Again, we define a set of lines by taking a single line through each . But this time we have . By getting rid of a few lines we can assume that (technically it should be , but it can be checked later that this won’t affect the proof). The number of incidences between and is still since each line is incident with exactly points. Therefore, by applying Lemma 1 again we get
This can be simplified to the following quadratic inequality:
This implies that must lie between the two roots of the quadratic equation , which gives us the required bound.
For more applications of this proof method, see my preprint “Minimal multiple blocking sets” on arXiv.
Another interesting result in finite geometry that can be obtained easily via Lemma 1 is the following Theorem of Stefaan De Winter, Jeroen Schillewaert and Jacques Verstraete on incidence free subsets. For an incidence structure , let be the largest value of where and such that there are no edges between and in the incidence graph of . Then for equal to the set of points in the finite projective space and equal to the set of -dimensional spaces in , we have
This follows directly from Lemma 1 by observing that this incidence structure formed by taking points and -spaces of is in fact a – design with .
Just last week, a new application of the expander mixing lemma to a graph theoretical problem related to finite geometry has appeared on arXiv. Jared Loucks and Craig Timmons have proved that the largest triangle free induced subgraph of the polarity graph of a projective plane of order , with respect to any polarity , has at most vertices. The polarity graph is defined by taking the points as vertices and making two points and adjacent if and only if . These graphs were introduced by Erdős and Renyi for the special case of orthogonal polarity, and independently by W. G. Brown. They have since been used in many problems in extremal graph theory.
I am sure that there are plenty of interesting applications of the expander mixing lemma in finite geometry and extremal graph theory waiting to be discovered. I will soon write about another new result in this direction which I proved a couple of weeks back.