The Szemerédi–Trotter theorem is one of the central results in discrete geometry which gives us a (tight) bound on the number of incidences, i.e., the number of point-line pairs with the point lying on the line, between finite sets of points and lines in the Euclidean plane. More precisely, let and be finite sets of points and lines, respectively, in and define . Then we have
for some constant . This result can be proved in several ways (including polynomial method), all of which use some topological property of the real plane. The same result does not hold over arbitrary fields, as can be seen for example by taking all points and lines in , but some analogous results can be proved over other fields. The purpose of this post is to discuss one such result and some interesting things around it.
In 2011, Vinh proved that given a set of points and a set of lines in , we have
using some methods from spectral graph theory. His proof, which is done over the setting of the projective plane , does not really require any property of these planes over finite fields besides the fact that the points and lines form a combinatorial design (which of course holds for non-Desarguesian planes as well) . This was explicitly observed by Ben Lund and Shubhangi Saraf who proved the following incidence bound on – designs, which generalises the results of Vinh:
Theorem 1. Let be a – design with replication number and number of blocks , let be a subset of and let be a subset of . Then
Since and for the affine plane , we get (1) from this theorem. Moreover, since points and fixed dimensional affine (or projective) subspaces of an -dimensional space over also form -designs, we get some incidence bounds in those cases as well. The main tool used by Vinh, Lund and Saraf is the following spectral result for bipartite graphs.
Lemma 2. 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 .
Lemma 2 is often referred to as the expander mixing lemma in math and CS literature, and it roughly says that if the second largest eigenvalue of a graph (in absolute value) is small then the graph behaves like a random graph. Though Lemma 2 is usually attributed to a paper of Alon and Chung from 1988 (see for example Section 2.4 of the survey on expander graphs by Hoory, Linial and Wigderson), it actually appeared 9 years before that in the PhD thesis of Willem Haemers (see Theorem 3.1 in this and Theorem 5.1 in this), who proved it using interlacing technique. In fact, Haemers also implicitly proved Theorem 1 by making the observation that the second largest eigenvalue of the incidence graph of a – design is . Note that for Theorem 1 we simply need to plug in the relevant values in Lemma 2 and ignore the term on the right hand side. I’ll sketch the proof of Haemers (see also Section 4.9 in Spectra of Graphs by Brouwer and Haemers). For direct proof of Lemma 2, see Section 3.2 of this paper.
Lemma 3. Let be a real symmetric matrix with eigenvalues , and let be an real matrix satisfying . Let be the eigenvalues of the (real symmetric) matrix . Then we have for all .
Lemma 3 can be proved using basic properties of Rayleigh quotient. Given two sequences of real numbers and , with , we say that the second sequence interlaces the first when for all (sometimes the term interlace is used only in the case of ). Therefore, Lemma 1 tells us that the eigenvalues of the matrix interlace the eigenvalues of the matrix . By choosing the matrix appropriately, Lemma 3 has the following corollary for arbitrary graphs.
Corollary 4. Let be a graph on vertices and let be a partition of its vertices. Define the quotient matrix of the adjacency matrix of with respect to the given partition, by taking to be average row sum of the block of determined by and , i.e., the average number of edges from to . Then the eigenvalues of interlace the eigenvalues of .
Now to prove Lemma 2, we will use the partition of the bipartite graph . The quotient matrix that we get with respect to this partition is
Now let be the eigenvalues of , and let be the eigenvalues of . Then it can be easily shown that and . (Note that the eigenvalues of both and are symmetric with respect to the the origin.) From interlacing and the fact that , we get . Since is equal to the product of the eigenvalues of , we have
The determinant of is not too difficult to compute due to the particular block structure of and after some simplifications we can see that it is equal to .
Corollary 4 and interlacing techniques in general have several other interesting applications too, see the survey by Haemers and the book by Brouwer and Haemers. For another application of Theorem 1 to incidence problems see this paper by Stefaan De Winter, Jeroen Schillewaert and Jacques Verstraete. For a proof of Theorem 1 which does not require spectral graph theory, see this recent paper of Brendan Murphy and Giorgis Petridis. Recently, Ben Lund, Shubhangi Saraf and Charles Wolf have applied Theorem 1 to improve bounds on the finite field Nikodym problem in 3 dimensions, see this. Their work is the first one to show a gap between the lower bound on the size of a Nikodym set and the lower bound on the size of a Kakeya set in , for arbitrary .
Edit 05/10/2016: Here is a nice introduction to interlacing techniques and spectral graph theory in general by Haemers: http://upcommons.upc.edu/handle/2099.2/2454. This in particular contains a simple proof of Cheeger’s inequality for regular graphs using interlacing, which I couldn’t find in any other place. More such videos can be found on his webpage.
Very nice post! More people should read Haemers thesis.
Thanks Sebi. I hope that they do. His survey paper on interlacing techniques also contains several gems.
Pingback: Expander Mixing Lemma in Finite Geometry | Anurag's Math Blog
Pingback: Spectral proofs of theorems on the boolean hypercube | Anurag's Math Blog
Pingback: Proving Spectral Bounds With Quotient Matrices | Ratio Bound – A Combinatorics Blog