Incidence Bounds and Interlacing Eigenvalues

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 $P$ and $L$ be finite sets of points and lines, respectively, in $\mathbb{R}^2$ and define $I(P, L) = \{(p, \ell) \in P \times L \mid p \in \ell\}$ . Then we have

$|I(P, L)| \leq C(|P|^{2/3}|L|^{2/3} + |P| + |L|)$ ,

for some constant $C$ . 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 $q^2$ points and $q^2 + q$ lines in $\mathbb{F}_q^2$ , 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 $P$ of points and a set $L$ of lines in $\mathbb{F}_q^2$ , we have

$|I(P, L)| \leq \frac{|P||L|}{q} + q^{1/2}\sqrt{|P||L|},$ (1)

using some methods from spectral graph theory. His proof, which is done over the setting of the projective plane $\mathrm{PG}(2, q)$ , 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 $2$ – $(v, k, \lambda)$ designs, which generalises the results of Vinh:

Theorem 1. Let $(X, B)$ be a $2$ – $(v, k, \lambda)$ design with replication number $r$ and number of blocks $b$ , let $P$ be a subset of $X$ and let $L$ be a subset of $B$ . Then

$||I(P, L)| - \frac{r|P||L|}{b}| \leq (r - \lambda)^{1/2} \sqrt{|P||L|}.$

Since $r = q + 1, b = q^2 + q$ and $\lambda = 1$ for the affine plane $\mathbb{F}_q^2$ , we get (1) from this theorem. Moreover, since points and fixed dimensional affine (or projective) subspaces of an $n$ -dimensional space over $\mathbb{F}_q$ also form $2$ -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 $G = (L, R, E)$ be a semiregular bipartite graph with degrees $k_L$ and $k_R$ . Let $S \subseteq L$ and $T \subseteq R$ such that $|S| = \alpha|L|$ and $|T| = \beta |R|$ . Define $e(S, T) = |\{(x, y) \in S \times T \mid \{x, y\} \in E\}|$ . Then we have

$|\frac{e(S,T)}{e(G)} - \alpha \beta| \leq \frac{\lambda_2}{\lambda_1} \sqrt{\alpha \beta(1 - \alpha)(1 - \beta)}$ ,

where $\lambda_1 = \sqrt{k_Lk_R}$ is the largest eigenvalue of $G$ , $\lambda_2$ is the second largest eigenvalue of $G$ in absolute value, and $e(G)$ is the total number of edges in $G$ .

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 $2$ – $(v, k, \lambda)$ design is $(r - \lambda)^{1/2}$ . Note that for Theorem 1 we simply need to plug in the relevant values in Lemma 2 and ignore the $(1 - \alpha)(1 - \beta)$ 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 $A$ be a real symmetric matrix with eigenvalues $\lambda_1 \geq \dots \geq \lambda_n$ , and let $S$ be an $n \times m$ real matrix satisfying $S^TS = I$ . Let $\mu_1 \geq \dots \geq \mu_m$ be the eigenvalues of the (real symmetric) matrix $B = S^T A S$ . Then we have $\lambda_i \geq \mu_i \geq \lambda_{n - m + i}$ for all $i \in \{1, \dots, m\}$ .

Lemma 3 can be proved using basic properties of Rayleigh quotient. Given two sequences of real numbers $\lambda_1 \geq \dots \geq \lambda_n$ and $\mu_1 \geq \dots \geq \mu_m$ , with $m < n$ , we say that the second sequence interlaces the first when $\lambda_i \geq \mu_i \geq \lambda_{n - m + i}$ for all $i$ (sometimes the term interlace is used only in the case of $m = n - 1$ ). Therefore, Lemma 1 tells us that the eigenvalues of the matrix $B$ interlace the eigenvalues of the matrix $A$ . By choosing the matrix $S$ appropriately, Lemma 3 has the following corollary for arbitrary graphs.

Corollary 4. Let $G$ be a graph on $n$ vertices and let $X_1, \dots, X_m$ be a partition of its vertices. Define the $m \times m$ quotient matrix $B = (b_{ij})$ of the adjacency matrix $A$ of $G$ with respect to the given partition, by taking $b_{ij}$ to be average row sum of the block of $A$ determined by $X_i$ and $X_j$ , i.e., the average number of edges from $X_i$ to $X_j$ . Then the eigenvalues of $B$ interlace the eigenvalues of $A$ .

Now to prove Lemma 2, we will use the partition $X_1 = S, X_2 = L \setminus S, X_3 = T, X_4 = R \setminus T$ of the bipartite graph $G$ . The quotient matrix that we get with respect to this partition is

$B = \begin{bmatrix} 0 & 0 & \frac{e(S,T)}{|S|} & k_L - \frac{e(S,T)}{|S|} \\ 0 & 0 & \frac{k_R|T| - e(S,T)}{|L| - |S|} & k_L -\frac{k_R|T| - e(S,T)}{|L| - |S|} \\\frac{e(S,T)}{|T|} &k_R - \frac{e(S,T)}{|T|} & 0 & 0 \\\frac{k_L|S| - e(S,T)}{|R| - |T|} &k_R -\frac{k_L|T| - e(S,T)}{|R| - |T|} & 0 & 0 \end{bmatrix}$

Now let $\mu_1 \geq \mu_2 \geq \mu_3 \geq \mu_4$ be the eigenvalues of $B$ , and let $\lambda_1 \geq \lambda_2 \dots \geq \lambda_{n-1} \geq \lambda_n$ be the eigenvalues of $A$ . Then it can be easily shown that $\lambda_1 = \mu_1 = \sqrt{k_Lk_R}$ and $\lambda_n = \mu_4 = -\sqrt{k_Lk_R}$ . (Note that the eigenvalues of both $A$ and $B$ are symmetric with respect to the the origin.) From interlacing and the fact that $\mu_3, \lambda_{n-1} < 0$ , we get $-\mu_2 \mu_3 \leq -\lambda_2 \lambda_{n-1}$ . Since $\det(B)$ is equal to the product of the eigenvalues of $B$ , we have

$\det(B)/(k_Lk_R) \leq -\mu_2\mu_3 \leq -\lambda_2 \lambda_{n-1} = \lambda_2^2$ .

The determinant of $B$ is not too difficult to compute due to the particular block structure of $B$ and after some simplifications we can see that it is equal to $(k_L k_R)^2 \frac{(e(S,T)/e(G) - \alpha \beta)^2}{\alpha \beta (1 - \alpha)(1 - \beta)}$ . $\blacksquare$

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 $\mathbb{F}_q^3$ , for arbitrary $q$ .

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.

5 Responses to Incidence Bounds and Interlacing Eigenvalues

Sebi Cioaba says:

December 14, 2016 at 3:10 am

Very nice post! More people should read Haemers thesis.

- Anurag Bishnoi says:
  
  December 14, 2016 at 11:18 am
  
  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