Expander Mixing Lemma in Finite Geometry

In this post I will discuss some nice applications of the expander mixing lemma in finite incidence geometry, including a new result that I have obtained recently.

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 $G = (L, R, E)$ be a semiregular bipartite graph with degrees $d_L$ and $d_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{d_Ld_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$ .

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 $n$ has eigenvalues $n + 1, \sqrt{n}, -\sqrt{n}, -n-1$ (the eigenvalues of a bipartite graph are always symmetric around the origin). And more generally, the eigenvalues of the incidence graph of a $2$ – $(v, k, \lambda)$ design are $\pm \sqrt{rk}, \pm \sqrt{r - \lambda}, 0$ . 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 $B$ of points with the property that for every line $\ell$ of the plane we have $|\ell \cap B| \geq 1$ . 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 $B$ is minimal if no proper subset of $B$ 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 $n + 1$ , which we a trivial blocking set. For a non-trivial minimal blocking set $B$ , Bruen and Thas proved the following result, which is one of the main starting points for a systematic study of blocking sets:

$n + \sqrt{n} + 1 \leq |B| \leq n \sqrt{n} + 1$ .

Here is a new proof of the upper bound which uses Lemma 1. For each point $x$ of $B$ there must exist a line $\ell_x$ such that $\ell_x \cap B = \{x\}$ since otherwise $B \setminus \{x\}$ will also form a blocking set, contradicting the minimality of $B$ . We can choose a single such line for each point of $B$ to get a set $\mathcal{L}$ of lines in the projective plane with the property that (a) $|\mathcal{L}| = |B|$ and (b) the number of edges between the sets $B$ and $\mathcal{L}$ in the incidence graph is exactly $|\mathcal{L}|$ . The number of points/lines in a projective plane of order $n$ is $n^2 + n + 1$ . By applying Lemma 1, taking $S = B, T = \mathcal{L}$ and defining $b := |B|$ , we get the following:

$|b - (n + 1)b^2/(n^2 + n + 1)| \leq \sqrt{n} \sqrt{b^2(1 - b/(n^2 + n + 1))^2}$ .

We must have $b \geq n + 1$ since $B$ is a blocking set (prove it!) and therefore $b(n+1) > n^2 + n + 1$ , which helps us remove the mod sign in the inequality. We get

$(n + 1)b/(n^2 + n + 1) - 1 \leq \sqrt{n}(1 - b/(n^2 + n + 1)$ ),

which simplifies to

$b \leq (\sqrt{n} + 1)(n^2 + n + 1)/(n + \sqrt{n} + 1)$ .

Since $n^2 + n + 1 = (n + 1 - \sqrt{n})(n + 1 + \sqrt{n})$ , we get

$b \leq (\sqrt{n} + 1)(n - \sqrt{n} + 1) = n \sqrt{n} + 1$ . $\Box$

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 $t$ -fold minimal blocking in a projective plane of order $n$ is a set $B$ of points with the property that (a) for each line $\ell$ , we have $|\ell \cap B| \geq t$ , and (b) through each point $x \in B$ , there exists a line $\ell_x$ with the property that $|\ell_x \cap B| = t$ . We will prove that

$|B| \leq \frac{1}{2} n\sqrt{4tn - (3t + 1)(t - 1)} + \frac{1}{2} (t - 1)n + t$ .

Again, we define a set of lines $\mathcal{L}$ by taking a single line $\ell_x$ through each $x \in B$ . But this time we have $t|\mathcal{L}| \geq |B|$ . By getting rid of a few lines we can assume that $|\mathcal{L}| = |B|/t$ (technically it should be $|\mathcal{L}| = \lceil |B|/t \rceil$ , but it can be checked later that this won’t affect the proof). The number of incidences between $B$ and $\mathcal{L}$ is still $|B|$ since each line is incident with exactly $t$ points. Therefore, by applying Lemma 1 again we get

$\left\lvert b - \frac{(n+1)b^2}{t(n^2 + n + 1)} \right\rvert \leq \sqrt{n\frac{b^2}{t}\left(1 - \frac{b}{(n^2 + n+ 1)}\right)\left(1 - \frac{b}{t(n^2 + n + 1)}\right)}$ .

This can be simplified to the following quadratic inequality:

$b^2 - ((t - 1)n + 2t)b - t(n - t)(n^2 + n + 1) \leq 0$ .

This implies that $b$ must lie between the two roots of the quadratic equation $x^2 - ((t - 1)n + 2t)x - t(n - t)(n^2 + n + 1) = 0$ , which gives us the required bound. $\Box$

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 $\Pi = (P, L, I)$ , let $\alpha(\Pi)$ be the largest value of $|X||Y|$ where $X \subseteq P$ and $Y \subseteq L$ such that there are no edges between $X$ and $Y$ in the incidence graph of $\Pi$ . Then for $P$ equal to the set of points in the finite projective space $\mathrm{PG}(n, q)$ and $L$ equal to the set of $k$ -dimensional spaces in $\mathrm{PG}(n, q)$ , we have

$\alpha(\Pi) \approx q^{(k + 2)(n - k)}.$

This follows directly from Lemma 1 by observing that this incidence structure $\Pi$ formed by taking points and $k$ -spaces of $\mathrm{PG}(n,q)$ is in fact a $2$ – $({n + 1 \brack 1}_q$ $, {k + 1 \brack 1}_q, {n - 1 \brack k - 1}_q)$ design with $r = {n \brack k}_q$ .

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 $n$ , with respect to any polarity $\theta$ , has at most $(n^2 + n + 1)/2 + \sqrt{n}(n^2 + n + 1)/(n + 1)$ vertices. The polarity graph is defined by taking the points as vertices and making two points $x$ and $y$ adjacent if and only if $x \in \theta(y)$ . 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.

Expander Mixing Lemma in Finite Geometry

About Anurag Bishnoi

3 Responses to Expander Mixing Lemma in Finite Geometry

Leave a comment Cancel reply

Recent Posts

Archives

Categories

Blogs I Follow

Expander Mixing Lemma in Finite Geometry

Share this:

Related

About Anurag Bishnoi

3 Responses to Expander Mixing Lemma in Finite Geometry

Leave a comment Cancel reply

Recent Posts

Archives

Categories

Blogs I Follow