Graph, girth and expanders

In the book “Elementary number theory, group theory and Ramanujan graphs“, Sarnak et. al. gave an elementary construction of expander graphs. We decided to go through the construction in the small seminar and I am recently assigned to give a talk about the girth estimate of such graphs.

Given graph (finite and undirected) $G$ , we will denote the set of vertices by $V(G)$ and the set of edges $E(G) \subseteq V(G)^2$ . The graph is assumed to be equipped with the standard metric where each edge has length $1$ .

The Cheeger constant (or isoperimetric constant of a graph, see this pervious post) is defined to be:

$\displaystyle h(G) = \inf_{S\subseteq V_G} \frac{|\partial S|}{\min\{|S|, |S^c|\}}$

Here the notation $\partial S$ denote the set of edges connecting an element in $S$ to an element outside of $S$ .

Note that this is indeed like our usual isoperimetric inequalities since it’s the smallest possible ratio between size of the boundary and size of the set it encloses. In other words, this calculates the most efficient way of using small boundary to enclose areas as large as possible.

It’s of interest to find graphs with large Cheeger constant (since small Cheeger constant is easy to make: take two large graphs and connect them with a single edge).

It’s also intuitive that as the number of edges going out from each vertice become large, the Cheeger constant will become large. Hence it make sense to restrict ourselves to graphs where there are exactly $k$ edges shearing each vertex, those are called $k$ -regular graphs.

If you play around a little bit, you will find that it’s not easy to build large k-regular graphs with Cheeger constant larger than a fixed number, say, $1/10$ .

Definition: A sequence of k-regular graphs $(G_i)$ where $|V_{G_i}| \rightarrow \infty$ is said to be an expander family if there exists constant $c>0$ where $h(G_i) \geq c$ for all $i$ .

By random methods due to Erdos, we can prove that expander families exist. However an explicit construction is much harder.

Definition: The girth of $G$ is the smallest non-trivial cycle contained in $G$ . (Doesn’t this smell like systole? :-P)

In the case of trees, since it does not contain any non-trivial cycle, define the girth to be infinity.

The book constructs for us, given pair $p, q$ of primes where $p$ is large (but fixed) and $q \geq p^8$ , a graph $(p+1)$ -regular graph $X^{p,q}$ with

$\displaystyle h(X^{p,q}) \geq \frac{1}{2}(p+1 - p^{5/6 + \varepsilon} - p^{1/6-\varepsilon})$

where $0 < \varepsilon < 1/6$ .

Note that the bound is strictly positive and independent of $q$ . Giving us for each $p$ , $(X^{p,q})$ as q runs through primes larger than $p^8$ is a $(p+1)$ -regular expander family.

In fact, this constructs for us an infinite family of expander families: a $(k+1)$ -regular one for each prime $k$ and the uniform bound on Cheeger constant gets larger as $k$ becomes larger.

One of the crucial step in proving this is to bound the girth of the graph $X^{p,q}$ , i.e. they showed that $g(X^{p,q}) \geq 2 \log_p(q)$ and if the quadratic reciprocity $(\frac{p}{q}) = -1$ then $g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4)$ . This is what I am going to do in this post.

Let $\mathbb H ( \mathbb Z)$ be the set of quaternions with $\mathbb Z$ coefficient, i.e.

$\mathbb H ( \mathbb Z) = \{ a+bi+cj+dk \ | \ a,b,c,d \in \mathbb Z \}$

Fix odd prime $p$ , let

$\Lambda' = \{ \alpha \in \mathbb H(\mathbb Z) \ | \ \alpha \equiv 1 (mod 2) \}$

$\cup \ \{\alpha \in \mathbb H(\mathbb Z) \ | \ N(\alpha) = p^n \ \mbox{and} \ \alpha \equiv i+j+k (mod 2) \}$

where the norm $N$ on $\mathbb H(\mathbb Z)$ is the usual $N(a+bi+cj+dk) = a^2 + b^2 +c^2+d^2$ .

$\Lambda'$ consists of points with only odd first coordinate or points lying on spheres of radius $\sqrt{p^n}$ and having only even first coordinate. One can easily check $\Lambda'$ is closed under multiplication.

Define equivalence relation $\sim$ on $\Lambda'$ by

$\alpha \sim \beta$ if there exists $m, n \in \mathbb{N}$ s.t. $p^m \alpha = \pm p^n \beta$ .

Let $\Lambda = \Lambda' / \sim$ , let $Q: \Lambda' \rightarrow \Lambda$ be the quotient map.

Since we know $\alpha_1 \sim \alpha_2, \beta_1 \sim \beta_2 \Rightarrow \alpha_1\beta_1 \sim \alpha_2\beta_2$ , $\Lambda$ carries an induced multiplication with unit.

In elementary number theory, we know that the equation $a^2+b^2+c^2+d^2 = p$ has exactly $8(p+1)$ integer solutions. Hence the sphere of radius $p$ in $\mathbb H(\mathbb Z)$ contain $8(p+1)$ points.

In each $4$ -tuple $(a,b,c,d)$ exactly one is of a different parity from the rest, depending on whether $p\equiv1$ or $3 (mod 4)$ . Restricting to solutions where the first coordinate is non-negative, having different parity from the rest (in case the first coordinate is $0$ , we pick one of the two solutions $\alpha, -\alpha$ to be canonical), this way we obtain exactly $p+1$ solutions.

Let $S'_p = \{ \alpha_1, \bar{\alpha_1}, \cdots, \alpha_k, \bar{\alpha_k}, \beta_1, \cdots, \beta_l \}$ be this set of $p+1$ points on the sphere. Note that the $\beta$ s represent the solutions where the first coordinate is exactly $0$ .

Check that $S'_p$ generates $\Lambda'$ .

We have $\alpha_i \bar{\alpha_i} = p$ and $-\beta_j^2 = p$ . By definition $S'_p \subseteq \Lambda'$ and $Q$ is injective on $S'_p$ . Let $S_p = Q(S'_p)$ .

Consider the Cayley graph $\mathcal G (\Lambda, S_p)$ , this is a $(p+1)$ -regular graph. Since $S_p$ generares $\Lambda$ , $\mathcal G (\Lambda, S_p)$ is connected.

Claim: $\mathcal G (\Lambda, S_p)$ is a tree.

Suppose not, let $(v_0, v_1, \cdots, v_k=v_0)$ a non-trivial cycle. $k \geq 2$ . Since $\mathcal G$ is a Cayley graph, we may assume $v_0 = e$ .

Hence $v_1 = \gamma_1, \ v_2 = \gamma_1\gamma_2, \cdots, v_k = \gamma_1 \cdots \gamma_k$ , for some $\gamma_1, \cdots, \gamma_k \in S_p$ .

Since $v_{i-1} \neq v_{i+1}$ for all $1\leq i \leq k-1$ , the word $\gamma_1, \cdots, \gamma_k$ cannot contain either $\alpha_i\bar{\alpha_i}$ or $\beta_i^2$ , hence cannot be further reduced.

$\gamma_1, \cdots, \gamma_k = e$ in $\Lambda$ means for some $m, n$ we have

$\pm p^n \gamma_1, \cdots, \gamma_k = p^m$ .

Since every word in $\Lambda'$ with norm $N(\alpha) = p^k$ must have a unique factorization $\alpha = \pm p^r w_m$ where $w_m$ is a reduces word of length $m$ in $S'_p$ and $2r+m = k$ .

Contradiction. Establishes the claim.

Now we reduce the group $\mathbb H (\mathbb Z)$ mod $q$ :

$\pi_q: \mathbb H (\mathbb Z) \rightarrow \mathbb H (\mathbb{F}_q)$

One can check that $\pi_q(\Lambda') = \mathbb H (\mathbb{F}_q)^\times$ .

Let $Z_q = \{ \alpha \in \mathbb H (\mathbb{F}_q)^\times \ | \ \alpha = \bar{\alpha} \}$ , $Z_q < \mathbb H (\mathbb{F}_q)^\times$ is a central subgroup.

For $\alpha, beta \in \Lambda'$ , $\alpha \sim \beta \Rightarrow \pi_q(\alpha)^{-1}\pi_q(\beta) \in Z_q$ . Which means we have well defined homomorphism

$\Pi_q: \Lambda \rightarrow \mathbb H (\mathbb{F}_q)^\times / Z_p$ .

Let $T_{p,q} = \Pi_q(S_p)$ , if $q > 2\sqrt{q}$ we have $\Pi_q$ is injective on $S_p$ and hence $latex $| T_{p,q} | = p+1$ .

Now we are ready to define our expanding family:

$X^{p,q} = \mathcal{G}( \Pi_q(\Lambda), T_{p,q})$ .

Since $S_p$ generates $\Lambda$ , $T_{p,q}$ generates $\Pi_q(\Lambda)$ . Hence $X^{p,q}$ is $(p+1)$ -regular and connected.

Theorem 1: $g(X^{p,q}) \geq 2 \log_p(q)$

Let $(e, v_1, \cdots, v_k=e)$ be a cycle in $X^{p,q}$ , there is $t_1, \cdots, t_k \in T_{p,q}$ such that $v_i = t_1 t_2 \cdots t_k$ for $1 \leq i \leq k$ .

Let $\gamma_i = \Pi_q^{-1}(t_i), \ \gamma_i \in S_p$ , $\alpha = a_0 + a_1 i+a_2 j +a_3 k = \gamma_1 \cdots \gamma_k \in \Lambda$ . Note that from the above arguement we know $\alpha$ is a reduced word, hence $\alpha \neq e_{\Lambda}$ . In particular, this implies $a_1, a_2, a_3$ cannot all be $0$ .

Also, since $\alpha$ is reduced, $\displaystyle N(\alpha) = \Pi_{i=1}^k N(\gamma_i) = p^k$ .

By Lemma, since $\Pi_q(\alpha) = 1$ , $\alpha \in \mbox{ker}(\Pi_q)$ hence $q$ divide $a_1, a_2, a_3$ , we conclude

$N(\alpha) = a_0^2 + a_1^2 +a_2^2 +a_3^2 \geq q^2$

We deduce $p^k \geq q^2$ hence $k \geq \log_p(q)$ for all cycle. i.e. $g(X^{p,q}) \geq \log_p(q)$ .

Theorem 2: If $q$ does not divide $p$ and $p$ is not a square mod $q$ (i.e. $(\frac{p}{q}) = -1$ ), then $g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4)$ .

For any cycle of length $k$ as above, we have $N(\alpha) = p^k \equiv a_0^2 (\mbox{mod} \ q)$ , i.e. $(\frac{p^k}{q}) = 1$ .

Since $(\frac{p^k}{q}) = ((\frac{p}{q})^k$ , we have $(-1)^k = 1, \ k$ is even. Let $k = 2l$ .

Note that $p^k \equiv a_0^2 (\mbox{mod} \ q^2)$ , we also have

$p^{2l} \equiv a_0^2 (\mbox{mod} \ q^2)$

Hence $p^l \equiv a_0 (\mbox{mod} \ q^2)$ .

Since $a_0^2 \leq p^{2l}$ , $|a_0| \leq p^l$ .

If $2l < 4 \log_p(q) - \log_p(4)$ we will have $p^l < q^2/2$ . Then $|p^l\pm a_0| \leq 2|p^l| < q^2$ .

But we know that $p^l \equiv a_0 (\mbox{mod} \ q^2)$ , one of $p^l\pm a_0$ must be divisible by $q^2$ , hence $0$ .

Conclude $p^l = \pm a_0$ , $N(\alpha) = p^k = a_0^2$ , hence $a_1=a_2=a_3=0$ . Contradiction.

2 thoughts on “Graph, girth and expanders”

Ultrametrics and the nonlinear Dvoretzky problem « Area 777 says:

September 19, 2011 at 4:54 am

[…] Graph, girth and expanders […]

LikeLike

1729_ says:

April 17, 2021 at 3:24 am

> By Lemma, since \Pi_q(\alpha) = 1, \alpha \in \mbox{ker}(\Pi_q) hence q divide a_1, a_2, a_3…

What lemma? There are none in the post.

LikeLike

Area777

Chasing dreams from mathematics to the real world

Graph, girth and expanders

2 thoughts on “Graph, girth and expanders”

Leave a Reply Cancel reply

Share this:

Like this:

2 thoughts on “Graph, girth and expanders”

Leave a Reply Cancel reply