3 3. Diameters and eigenvalues

Definition 102 Distance, s3.1

✓

In a graph $G$, the distance between two vertices $u$ and $v$, denoted $d(u,v)$, is the length of a shortest path joining $u$ and $v$ in $G$ (and $d(u,v)=\infty $ if $u,v$ lie in different components). One has $d(u,u)=0$, $d(u,v)=d(v,u)$, and the triangle inequality $d(u,w)\le d(u,v)+d(v,w)$.

Definition 103 Diameter, s3.1

✓

The diameter of $G$, denoted $D(G)$, is the maximum distance over all pairs of vertices, $D(G)=\max _{u,v\in V(G)} d(u,v)$.

Definition 104 Distance between two subsets, s3.2

For two subsets $X,Y$ of vertices of $G$, the distance between $X$ and $Y$ is

\[ d(X,Y) \; =\; \min \{ d(x,y) : x\in X,\ y\in Y \} . \]

We write $\bar X = V(G)\setminus X$ for the complement of $X$, and $\operatorname {vol}X = \sum _{x\in X} d_x$ for the volume of $X$ (where $d_x$ is the degree of $x$).

Lemma 105 Matrix powers respect graph distance

Let $G$ be a graph on the vertex set $V$ and let $M$ be a real matrix with rows and columns indexed by $V$ such that $M(u,v)=0$ whenever $u\neq v$ and $u\not\sim v$ (i.e. $M$ has the sparsity pattern of the closed neighborhoods, as does $I+A$ or the normalized Laplacian $\mathcal{L}$). Then for every integer $k\ge 0$ and every pair $u,v$ with $d(u,v){\gt}k$ we have $M^k(u,v)=0$.

Proof ▶

Note first that $M(w,v)\neq 0$ forces $w=v$ or $w\sim v$, hence $d(w,v)\le 1$. We induct on $k$. For $k=0$, $M^0=I$ and $I(u,v)=0$ whenever $u\neq v$; since $d(u,v){\gt}0$ implies $u\neq v$, the claim holds. Assume the claim for $k$ and let $d(u,v){\gt}k+1$. Writing $M^{k+1}(u,v)=\sum _{w} M^{k}(u,w)\, M(w,v)$, consider a term with $M(w,v)\neq 0$; then $d(w,v)\le 1$, so by the triangle inequality $d(u,w)\ge d(u,v)-d(w,v)\ge (k+2)-1 = k+1 {\gt} k$, and the induction hypothesis gives $M^{k}(u,w)=0$. Every summand vanishes, so $M^{k+1}(u,v)=0$.

Lemma 106 Polynomial criterion for the diameter, s3.1

Let $M$ be an $n\times n$ matrix indexed by $V(G)$ with $M(u,v)=0$ whenever $u\neq v$ and $u\not\sim v$. Suppose that for some integer $t\ge 0$ and some polynomial $p_t$ of degree $t$ we have $p_t(M)(u,v)\neq 0$ for all $u,v\in V(G)$. Then $D(G)\le t$.

Proof ▶

Write $p_t(x)=\sum _{k=0}^{t} c_k x^k$, so $p_t(M)(u,v)=\sum _{k=0}^{t} c_k\, M^{k}(u,v)$. Suppose, for contradiction, that some pair satisfies $d(u,v){\gt}t$. Then for every $k\le t$ we have $d(u,v){\gt}t\ge k$, so $M^{k}(u,v)=0$ by Lemma 105. Hence $p_t(M)(u,v)=0$, contradicting the hypothesis. Therefore $d(u,v)\le t$ for all $u,v$, i.e. $D(G)\le t$.

Theorem 107 Theorem 3.1: distance between two subsets, logarithmic form

Suppose $G$ is not a complete graph, with normalized Laplacian eigenvalues $0=\lambda _0\le \lambda _1\le \cdots \le \lambda _{n-1}$ (so $\lambda _1\neq \lambda _{n-1}$). For nonempty $X,Y\subset V(G)$,

\[ d(X,Y) \; \le \; \left\lceil \frac{\log \sqrt{\dfrac {\operatorname {vol}\bar X\, \operatorname {vol}\bar Y}{\operatorname {vol}X\, \operatorname {vol}Y}}}{\log \dfrac {\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}} \right\rceil . \]

Proof ▶

For $S\subset V(G)$ let $\psi _S$ be the indicator function ($\psi _S(x)=1$ if $x\in S$, else $0$), and let $T$ be the diagonal degree matrix. We claim that if for some integer $t$ and some degree-$t$ polynomial $p_t$ we have $\langle T^{1/2}\psi _Y,\ p_t(\mathcal{L})T^{1/2}\psi _X\rangle {\gt}0$, then $d(X,Y)\le t$. Indeed

\[ \langle T^{1/2}\psi _Y, p_t(\mathcal{L})T^{1/2}\psi _X\rangle = \sum _{u\in Y,\, v\in X} \sqrt{d_u d_v}\; p_t(\mathcal{L})(u,v), \]

so if the sum is positive there is a pair $u\in Y$, $v\in X$ with $p_t(\mathcal{L})(u,v)\neq 0$. Since $\mathcal{L}$ satisfies $\mathcal{L}(u,v)=0$ for $u\neq v$, $u\not\sim v$, Lemma 105 applied to each power in $p_t(\mathcal{L})$ gives $d(u,v)\le t$, whence $d(X,Y)\le t$.

Let $\{ \phi _i\} _{i=0}^{n-1}$ be an orthonormal basis of eigenfunctions of $\mathcal{L}$, with $\phi _0 = T^{1/2}\mathbf{1}/\sqrt{\operatorname {vol}G}$. Expand $T^{1/2}\psi _X=\sum _i a_i\phi _i$ and $T^{1/2}\psi _Y=\sum _i b_i\phi _i$. Then

\[ a_0=\langle T^{1/2}\psi _X,\phi _0\rangle =\frac{\operatorname {vol}X}{\sqrt{\operatorname {vol}G}},\qquad b_0=\frac{\operatorname {vol}Y}{\sqrt{\operatorname {vol}G}},\qquad a_0b_0=\frac{\operatorname {vol}X\, \operatorname {vol}Y}{\operatorname {vol}G}, \]

and, using $\| T^{1/2}\psi _X\| ^2=\operatorname {vol}X$,

\[ \sum _{i{\gt}0}a_i^2 = \operatorname {vol}X-\frac{(\operatorname {vol}X)^2}{\operatorname {vol}G} = \frac{\operatorname {vol}X\, \operatorname {vol}\bar X}{\operatorname {vol}G},\qquad \sum _{i{\gt}0}b_i^2 = \frac{\operatorname {vol}Y\, \operatorname {vol}\bar Y}{\operatorname {vol}G}. \]

Choose $p_t(z)=\bigl(1-\tfrac {2z}{\lambda _1+\lambda _{n-1}}\bigr)^t$, so $p_t(0)=1$. The affine map $z\mapsto 1-\tfrac {2z}{\lambda _1+\lambda _{n-1}}$ sends $[\lambda _1,\lambda _{n-1}]$ onto $[-(1-\lambda ),\, 1-\lambda ]$ with $\lambda := \tfrac {2\lambda _1}{\lambda _{n-1}+\lambda _1}$ and $1-\lambda =\tfrac {\lambda _{n-1}-\lambda _1}{\lambda _{n-1}+\lambda _1}$; hence $|p_t(\lambda _i)|\le (1-\lambda )^t$ for all $i\ge 1$. Therefore

\begin{align*} \langle T^{1/2}\psi _Y, p_t(\mathcal{L})T^{1/2}\psi _X\rangle & = a_0b_0 + \sum _{i{\gt}0} p_t(\lambda _i)\, a_i b_i \; \ge \; a_0 b_0 - (1-\lambda )^t \sum _{i{\gt}0}|a_i b_i| \\ & \ge \frac{\operatorname {vol}X\, \operatorname {vol}Y}{\operatorname {vol}G} - (1-\lambda )^t\, \frac{\sqrt{\operatorname {vol}X\, \operatorname {vol}\bar X\, \operatorname {vol}Y\, \operatorname {vol}\bar Y}}{\operatorname {vol}G}, \end{align*}

the last step by Cauchy–Schwarz. This is ${\gt}0$ as soon as $(1-\lambda )^t {\lt} \sqrt{\operatorname {vol}X\, \operatorname {vol}Y/(\operatorname {vol}\bar X\, \operatorname {vol}\bar Y)}$, i.e. (since $\log \frac1{1-\lambda }{\gt}0$)

\[ t \; \ge \; \frac{\log \sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}}{\log \frac{1}{1-\lambda }} \; =\; \frac{\log \sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}}{\log \frac{\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}}. \]

Taking $t$ equal to the ceiling of the right-hand side gives $d(X,Y)\le t$, as claimed.

Corollary 108 Corollary 3.2: diameter of a regular graph

Suppose $G$ is a regular graph which is not complete. Then

\[ D(G) \; \le \; \left\lceil \frac{\log (n-1)}{\log \frac{\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}} \right\rceil . \]

(The weaker bound $D(G)\le \lceil \log (n-1)/\log \frac{1}{1-\lambda _1}\rceil $ holds under the additional condition $1-\lambda _1\ge \lambda _{n-1}-1$, and the displayed form is obtained from it by the spectrum-shifting substitution $\lambda =2\lambda _1/(\lambda _{n-1}+\lambda _1)$.)

Proof ▶

Let $u,v$ realize the diameter and apply Theorem 107 with the singletons $X=\{ u\} $, $Y=\{ v\} $. For a $d$-regular graph, $\operatorname {vol}X=\operatorname {vol}Y=d$ and $\operatorname {vol}\bar X=\operatorname {vol}\bar Y=(n-1)d$, so $\sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)} =\sqrt{(n-1)^2}=n-1$. Hence $D(G)=d(u,v)\le \lceil \log (n-1)/\log \frac{\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}\rceil $.

Construction 109 Shifted Chebyshev polynomials, s3.2

The Chebyshev polynomials of the first kind are $T_0(z)=1$, $T_1(z)=z$, and $T_{t+1}(z)=2zT_t(z)-T_{t-1}(z)$ for $t{\gt}1$; equivalently $T_t(z)=\cosh \bigl(t\cosh ^{-1}z\bigr)$. For a non-complete graph $G$ with $\lambda _1\neq \lambda _{n-1}$ define the degree-$t$ polynomial

\[ S_t(x)\; =\; \frac{T_t\! \left(\dfrac {\lambda _1+\lambda _{n-1}-2x} {\lambda _{n-1}-\lambda _1}\right)}{T_t\! \left(\dfrac {\lambda _{n-1}+\lambda _1} {\lambda _{n-1}-\lambda _1}\right)} . \]

Lemma 110 Bounds for $S_t$ on the spectrum

With $\mu := \dfrac {\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}{\gt}1$, we have $S_t(0)=1$ and $|S_t(x)|\le 1/T_t(\mu )$ for all $x\in [\lambda _1,\lambda _{n-1}]$; in particular $|S_t(\lambda _i)|\le 1/T_t(\mu )$ for every $i\ge 1$.

Proof ▶

The affine map $g(x)=\dfrac {\lambda _1+\lambda _{n-1}-2x}{\lambda _{n-1}-\lambda _1}$ sends $x=\lambda _1$ to $1$ and $x=\lambda _{n-1}$ to $-1$, hence $g([\lambda _1,\lambda _{n-1}])=[-1,1]$; also $g(0)=\mu $. Since $|T_t|\le 1$ on $[-1,1]$ (a standard property of the Chebyshev polynomials, from $T_t=\cos (t\arccos \cdot )$), for $x\in [\lambda _1,\lambda _{n-1}]$ we get $|S_t(x)|=|T_t(g(x))|/T_t(\mu )\le 1/T_t(\mu )$. Finally $S_t(0)=T_t(g(0))/T_t(\mu )=T_t(\mu )/T_t(\mu )=1$.

Theorem 111 Theorem 3.3: distance between two subsets, Chebyshev form

Suppose $G$ is not a complete graph. For nonempty $X,Y\subset V(G)$,

\[ d(X,Y) \; \le \; \left\lceil \frac{\cosh ^{-1}\sqrt{\dfrac {\operatorname {vol}\bar X\, \operatorname {vol}\bar Y}{\operatorname {vol}X\, \operatorname {vol}Y}}}{\cosh ^{-1}\dfrac {\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}} \right\rceil . \]

Proof ▶

Repeat the proof of Theorem 107, replacing $p_t(\mathcal{L})$ by $S_t(\mathcal{L})$, which has degree $t$. As there, if $\langle T^{1/2}\psi _Y, S_t(\mathcal{L})T^{1/2}\psi _X\rangle {\gt}0$ then $d(X,Y)\le t$ (Lemma 105). By Lemma 110, $S_t(0)=1$ and $|S_t(\lambda _i)|\le 1/T_t(\mu )$ for $i\ge 1$, where $\mu =\frac{\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}$. Hence, with the Fourier data of the previous proof,

\[ \langle T^{1/2}\psi _Y, S_t(\mathcal{L})T^{1/2}\psi _X\rangle \; \ge \; \frac{\operatorname {vol}X\, \operatorname {vol}Y}{\operatorname {vol}G} - \frac{1}{T_t(\mu )}\, \frac{\sqrt{\operatorname {vol}X\, \operatorname {vol}\bar X\, \operatorname {vol}Y\, \operatorname {vol}\bar Y}}{\operatorname {vol}G}, \]

by Cauchy–Schwarz. This is ${\gt}0$ once $T_t(\mu ){\gt}\sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}$. Since $T_t(\mu )=\cosh (t\cosh ^{-1}\mu )$ and $\mu {\gt}1$, this holds when $t\cosh ^{-1}\mu {\gt}\cosh ^{-1}\sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}$, i.e. $t\ge \cosh ^{-1}\sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}/\cosh ^{-1}\mu $. Taking $t$ equal to the ceiling proves the bound.

Corollary 112 Chebyshev diameter bound for regular graphs, s3.1

Suppose $G$ is a regular graph which is not complete. Then

\[ D(G) \; \le \; \left\lceil \frac{\cosh ^{-1}(n-1)}{\cosh ^{-1}\frac{\lambda _{n-1}+\lambda _1}{\lambda _{n-1}-\lambda _1}} \right\rceil . \]

For example, for $k$-regular Ramanujan graphs one has $1-\lambda _1=\lambda _{n-1}-1=\frac{1}{2}\sqrt{k-1}$ (in the adjacency normalization), giving $D\le \log (n-1)/(2\log (k-1))$ from the logarithmic form, within a factor of $2$ of the best possible bound.

Proof ▶

Apply Theorem 111 to singletons $X=\{ u\} $, $Y=\{ v\} $ realizing the diameter; for a regular graph $\sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}=n-1$ exactly as in Corollary 108.

Definition 113 $s$-boundary and $s$-neighborhood of a vertex set, s3.2

For $X\subseteq V(G)$ and $s\ge 1$, the $s$-boundary of $X$ is

\[ \delta _s X \; =\; \{ \, y : y\notin X \text{ and } d(x,y)\le s \text{ for some } x\in X \, \} , \]

and the $s$-neighborhood is $N_s^*X = X\cup \delta _s X$. In particular $\delta _1 X = \delta X$ is the usual vertex boundary of $X$, and $N_s^*X=\{ \, z: d(z,X)\le s\, \} $.

Lemma 114 Lemma 3.4: volume of the vertex boundary

For all $X\subseteq V(G)$,

\[ \frac{\operatorname {vol}\delta X}{\operatorname {vol}X} \; \ge \; \frac{1-(1-\lambda )^2}{(1-\lambda )^2+\operatorname {vol}X/\operatorname {vol}\bar X}, \qquad \lambda =\frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}. \]

Proof ▶

For a complete graph the inequality is immediate, so assume $G$ is not complete. Take $Y=\bar X-\delta X$ and $t=1$; then $d(X,Y)\ge 2{\gt}1$, so from the proof of Theorem 107, with $p_1(\mathcal{L})$ (which has entries supported on closed neighborhoods),

\[ 0=\langle T^{1/2}\psi _Y, p_1(\mathcal{L})T^{1/2}\psi _X\rangle {\gt} \frac{\operatorname {vol}X\, \operatorname {vol}Y}{\operatorname {vol}G} - (1-\lambda )\, \frac{\sqrt{\operatorname {vol}X\, \operatorname {vol}\bar X\, \operatorname {vol}Y\, \operatorname {vol}\bar Y}}{\operatorname {vol}G}. \]

Hence $(1-\lambda )^2\, \operatorname {vol}\bar X\, \operatorname {vol}\bar Y {\gt} \operatorname {vol}X\, \operatorname {vol}Y$. Since $\bar Y = X\cup \delta X$, we have $\operatorname {vol}\bar Y=\operatorname {vol}X+\operatorname {vol}\delta X$ and $\operatorname {vol}Y=\operatorname {vol}G-\operatorname {vol}X-\operatorname {vol}\delta X = \operatorname {vol}\bar X-\operatorname {vol}\delta X$, so

\[ (1-\lambda )^2\, \operatorname {vol}\bar X\, (\operatorname {vol}X+\operatorname {vol}\delta X) \; {\gt}\; \operatorname {vol}X\, (\operatorname {vol}\bar X - \operatorname {vol}\delta X). \]

Writing $a=\operatorname {vol}X$, $b=\operatorname {vol}\bar X$, $c=\operatorname {vol}\delta X$, $\mu =(1-\lambda )^2$: $\mu b(a+c){\gt}a(b-c)$ gives $c(\mu b + a) {\gt} ab(1-\mu )$, i.e. $\frac{c}{a} {\gt} \frac{b(1-\mu )}{\mu b + a} = \frac{1-\mu }{\mu + a/b}$, which is the claim.

Corollary 115 Corollary 3.5: vertex-isoperimetric bound

For $X\subseteq V(G)$ with $\operatorname {vol}X\le \operatorname {vol}\bar X$, where $G$ is not a complete graph,

\[ \frac{\operatorname {vol}\delta X}{\operatorname {vol}X}\; \ge \; \lambda ,\qquad \lambda =\frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}. \]

Proof ▶

By Lemma 114 and $\operatorname {vol}X/\operatorname {vol}\bar X\le 1$,

\[ \frac{\operatorname {vol}\delta X}{\operatorname {vol}X} \ge \frac{1-(1-\lambda )^2}{(1-\lambda )^2+\operatorname {vol}X/\operatorname {vol}\bar X} \ge \frac{1-(1-\lambda )^2}{1+(1-\lambda )^2} = \frac{\lambda (2-\lambda )}{2-2\lambda +\lambda ^2}. \]

This last quantity is $\ge \lambda $ iff $2-\lambda \ge 2-2\lambda +\lambda ^2$, i.e. $\lambda \ge \lambda ^2$, which holds because $0{\lt}\lambda \le 1$.

Lemma 116 Lemma 3.6: volume of the $t$-boundary

For $X\subseteq V(G)$ ($G$ not complete) and any integer $t{\gt}0$,

\[ \frac{\operatorname {vol}\delta _t X}{\operatorname {vol}X} \; \ge \; \frac{1-(1-\lambda )^{2t}}{(1-\lambda )^{2t}+\operatorname {vol}X/\operatorname {vol}\bar X}, \qquad \lambda =\frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}. \]

Proof ▶

Argue exactly as in Lemma 114 but with $Y=\bar X-\delta _t X$ (so $d(X,Y)\ge t+1{\gt}t$ and $\bar Y=X\cup \delta _t X=N_t^*X$) and with the degree-$t$ polynomial $p_t(\mathcal{L})$, whose nonzero eigenvalues obey $|p_t(\lambda _i)|\le (1-\lambda )^t$. This yields $(1-\lambda )^{2t}\operatorname {vol}\bar X\, \operatorname {vol}\bar Y{\gt}\operatorname {vol}X\, \operatorname {vol}Y$, and the same algebra with $\mu =(1-\lambda )^{2t}$ gives the stated inequality.

Lemma 117 Lemma 3.7: $t$-boundary, balanced case

For an integer $t{\gt}0$ and $X\subseteq V(G)$ with $\operatorname {vol}X\le \operatorname {vol}\bar X$,

\[ \frac{\operatorname {vol}\delta _t X}{\operatorname {vol}X}\; \ge \; \frac{1-(1-\lambda )^{2t}}{1+(1-\lambda )^{2t}}, \qquad \lambda =\frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}. \]

Proof ▶

Substitute $\operatorname {vol}X/\operatorname {vol}\bar X\le 1$ into the denominator of Lemma 116.

Lemma 118 Lemma 3.8: volume of the $t$-neighborhood (Tanner-type bound)

For $X\subseteq V(G)$ with $\operatorname {vol}X\le \operatorname {vol}\bar X$ and any integer $t{\gt}0$, with $N_t^*X=X\cup \delta _t X$,

\[ \frac{\operatorname {vol}N_t^*X}{\operatorname {vol}X}\; \ge \; \frac{1}{(1-\lambda )^{2t}\, \dfrac {\operatorname {vol}\bar X}{\operatorname {vol}G} +\dfrac {\operatorname {vol}X}{\operatorname {vol}G}}, \qquad \lambda =\frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}. \]

(For a regular graph and $t=1$ this is the inequality of Tanner underlying the vertex-expansion properties discussed in Chapter 6.)

Proof ▶

As in Lemma 116 take $Y=\bar X-\delta _t X=V\setminus N_t^*X$, so $\bar Y=N_t^*X$ and $\operatorname {vol}Y=\operatorname {vol}G-\operatorname {vol}N_t^*X$; the proof of Theorem 107 gives $(1-\lambda )^{2t}\operatorname {vol}\bar X\, \operatorname {vol}N_t^*X{\gt}\operatorname {vol}X(\operatorname {vol}G-\operatorname {vol}N_t^*X)$. Writing $N=\operatorname {vol}N_t^*X$ this reads $N\bigl((1-\lambda )^{2t}\operatorname {vol}\bar X+\operatorname {vol}X\bigr){\gt}\operatorname {vol}X\cdot \operatorname {vol}G$, hence $\frac{N}{\operatorname {vol}X}{\gt}\frac{\operatorname {vol}G}{(1-\lambda )^{2t}\operatorname {vol}\bar X+\operatorname {vol}X}$, which is the claim after dividing numerator and denominator by $\operatorname {vol}G$.

Lemma 119 Lemma 3.9: two vectors with non-negative inner product

Let $x_1,x_2,\dots ,x_{d+2}$ be $d+2$ arbitrary vectors in $d$-dimensional Euclidean space. Then there are two of them, say $x_i,x_j$ with $i\neq j$, such that $\langle x_i,x_j\rangle \ge 0$.

Proof ▶

We induct on $d$. For $d=1$ the vectors are three or more real numbers; among any three reals two share a sign (or one is zero), so some product is $\ge 0$. Assume the statement for $(d-1)$-dimensional space, and suppose for contradiction that all pairs among $x_1,\dots ,x_{d+2}$ have negative inner product. Let $P$ be the hyperplane orthogonal to $x_{d+2}$ and let $x_i'$ be the orthogonal projection of $x_i$ onto $P$ for $i=1,\dots ,d+1$. Because $\langle x_i,x_{d+2}\rangle {\lt}0$ for each $i\le d+1$, all these $x_i$ lie in the same open half-space bounded by $P$, so $x_i=x_i'+a_i e$ with $a_i{\gt}0$ and $e$ a unit vector orthogonal to $P$ pointing into that half-space. Then for $i\neq j$,

\[ 0{\gt}\langle x_i,x_j\rangle =\langle x_i'+a_i e,\; x_j'+a_j e\rangle =\langle x_i',x_j'\rangle + a_i a_j, \]

so $\langle x_i',x_j'\rangle {\lt}-a_ia_j{\lt}0$. Thus $x_1',\dots ,x_{d+1}'$ are $d+1=(d-1)+2$ vectors in the $(d-1)$-dimensional space $P$ with pairwise negative inner products, contradicting the induction hypothesis.

Theorem 120 Theorem 3.10: distances among $k+1$ subsets, logarithmic form

Suppose $G$ is not a complete graph, and let $X_i\subset V(G)$ for $i=0,1,\dots ,k$. If $1-\lambda _k\ge \lambda _{n-1}-1$, then

\[ \min _{i\neq j} d(X_i,X_j) \; \le \; \max _{i\neq j} \left\lceil \frac{\log \sqrt{\operatorname {vol}\bar X_i\, \operatorname {vol}\bar X_j /(\operatorname {vol}X_i\, \operatorname {vol}X_j)}}{\log \frac{1}{1-\lambda _k}} \right\rceil . \]

Proof ▶

Let $X,Y$ be any two distinct members of $\{ X_i\} $, with Fourier coefficients $a_i,b_i$ of $T^{1/2}\psi _X,T^{1/2}\psi _Y$. Using the polynomial $(I-\mathcal{L})^t$ (whose eigenvalue on $\phi _i$ is $(1-\lambda _i)^t$ and which is supported on closed neighborhoods),

\[ \langle T^{1/2}\psi _Y,(I-\mathcal{L})^tT^{1/2}\psi _X\rangle \ge a_0b_0 + \sum _{i=1}^{k-1}(1-\lambda _i)^t a_i b_i - \sum _{i\ge k}(1-\lambda _i)^t|a_ib_i|. \]

Endow $\mathbb {R}^{k-1}$ with the scalar product $\langle (a),(b)\rangle =\sum _{i=1}^{k-1}(1-\lambda _i)^t a_i b_i$ (a genuine Euclidean inner product when $(1-\lambda _i)^t{\gt}0$ for $i\le k-1$, e.g. $\lambda _{k-1}{\lt}1$ or $t$ even). To each $X_m$ associate the vector $(a_1^{(m)},\dots ,a_{k-1}^{(m)})$; these are $k+1$ vectors in $\mathbb {R}^{k-1}$, so by Lemma 119 two of them, say those for $X$ and $Y$, satisfy $\sum _{i=1}^{k-1}(1-\lambda _i)^t a_i b_i\ge 0$. Since $1-\lambda _k\ge \lambda _{n-1}-1$ we have $|1-\lambda _i|\le 1-\lambda _k$ for all $i\ge k$, so with Cauchy–Schwarz on the tail,

\[ \langle T^{1/2}\psi _Y,(I-\mathcal{L})^tT^{1/2}\psi _X\rangle {\gt} \frac{\operatorname {vol}X\, \operatorname {vol}Y}{\operatorname {vol}G} - (1-\lambda _k)^t\, \frac{\sqrt{\operatorname {vol}X\, \operatorname {vol}\bar X\, \operatorname {vol}Y\, \operatorname {vol}\bar Y}}{\operatorname {vol}G}. \]

This is positive once $t\ge \log \sqrt{\operatorname {vol}\bar X\, \operatorname {vol}\bar Y/(\operatorname {vol}X\, \operatorname {vol}Y)}/\log \frac1{1-\lambda _k}$, and then $d(X,Y)\le t$ as in Theorem 107. As $X,Y$ are among the $X_i$, $\min _{i\neq j}d(X_i,X_j)\le d(X,Y)\le \max _{i\neq j}\lceil \cdots \rceil $.

Theorem 121 Theorem 3.11: distances among $k+1$ subsets, Chebyshev-shifted form

Let $X_i\subset V(G)$ for $i=0,1,\dots ,k$. If $\lambda _k\neq \lambda _{n-1}$, then

Proof ▶

Repeat the proof of Theorem 120 but, exactly as in the passage from the logarithmic to the shifted form of Theorem 107, replace the tail polynomial $(I-\mathcal{L})^t$ by $\bigl(1-\tfrac {2\mathcal{L}}{\lambda _k+\lambda _{n-1}}\bigr)^t$. For $i\ge k$ the eigenvalues then satisfy $\bigl|1-\tfrac {2\lambda _i}{\lambda _k+\lambda _{n-1}}\bigr| \le \tfrac {\lambda _{n-1}-\lambda _k}{\lambda _{n-1}+\lambda _k}=1-\lambda $ with $\lambda =\tfrac {2\lambda _k}{\lambda _{n-1}+\lambda _k}$, which removes the hypothesis $1-\lambda _k\ge \lambda _{n-1}-1$ and replaces $\frac1{1-\lambda _k}$ by $\frac1{1-\lambda }=\frac{\lambda _{n-1}+\lambda _k}{\lambda _{n-1}-\lambda _k}$.

Theorem 122 Theorem 3.12: distances among $k+1$ subsets, optimized window

Let $X_i\subset V(G)$ for $i=0,1,\dots ,k$. Then

\[ \min _{i\neq j} d(X_i,X_j) \; \le \; \min _{0\le j{\lt}k}\ \max _{i\neq j} \left\lceil \frac{\log \sqrt{\operatorname {vol}\bar X_i\, \operatorname {vol}\bar X_j /(\operatorname {vol}X_i\, \operatorname {vol}X_j)}}{\log \frac{\lambda _{n-1-j}+\lambda _{k-j}}{\lambda _{n-1-j}-\lambda _{k-j}}} \right\rceil , \]

where the outer index $j$ ranges over values with $\lambda _{k-j}\neq \lambda _{n-1-j}$.

Proof ▶

Fix $j$ with $1\le j\le k-1$. Proceed as in Theorem 120, but keep as the “middle” coordinates the index set $S=\{ \, i: 1\le i\le k-j \text{ or } n-j+1\le i\le n-1\, \} $, which has $|S|=(k-j)+(j-1)=k-1$ elements. Associating to each $X_m$ the vector $(a_i^{(m)})_{i\in S}\in \mathbb {R}^{k-1}$ and using the scalar product $\sum _{i\in S}(1-\lambda _i)^t a_i b_i$, Lemma 119 yields two subsets $X,Y$ whose vectors satisfy $\sum _{i\in S}(1-\lambda _i)^t a_i b_i\ge 0$. The remaining eigenvalues (indices $i\notin S\cup \{ 0\} $, whose spectral window has endpoints $\lambda _{k-j}$ and $\lambda _{n-1-j}$) are handled by the shifted polynomial as in Theorem 121, contributing the denominator $\log \frac{\lambda _{n-1-j}+\lambda _{k-j}}{\lambda _{n-1-j}-\lambda _{k-j}}$. Taking the best (smallest) bound over admissible $j$ gives the stated inequality.

Definition 123 Universal setting for a Laplacian, s3.4

The continuous and discrete cases are treated by a common framework:

an underlying space $M$ equipped with a finite measure $\mu $;
a Laplace operator $\mathcal{L}$ on functions on $M$ that is self-adjoint on $L^2(M,\mu )$ and has discrete spectrum;
if $M$ has a boundary, a boundary condition chosen so as not to disrupt the self-adjointness of $\mathcal{L}$;
a distance function $\mathrm{dist}(x,y)$ on $M$ with $|\nabla \, \mathrm{dist}|\le 1$ for an appropriate notion of gradient.

For a finite connected graph (also denoted $M$), $\mu $ is the vertex-degree measure and $\mathcal{L}$ the normalized Laplacian; all four properties hold.

Definition 124 Support-neighborhood and finite propagation, s3.4

For $f\in L^2(M,\mu )$ and $r\in \mathbb {R}$, the $r$-neighborhood of the support is $\mathrm{supp}_r f=\{ x\in M:\mathrm{dist}(x,\mathrm{supp}\, f)\le r\} $. In the discrete case, a degree-$s$ polynomial $p_s$ satisfies

\[ \mathrm{supp}\ p_s(\mathcal{L})f\ \subset \ \mathrm{supp}_s f, \]

which is the manifold-analog locality property carried over to the continuous setting.

Definition 125 Bounded propagation family and the operator $\Phi (\mathcal{L})$, s3.4

Assume there is a family of bounded continuous functions $P_s(\lambda )$ on $\mathrm{Spec}\, \mathcal{L}$, indexed by $s\in [0,\infty )$, such that for every $f\in L^2(M,\mu )$,

\[ \mathrm{supp}\ P_s(\mathcal{L})f\ \subset \ \mathrm{supp}_s f. \]

For instance $P_s(\lambda )=\cos (\sqrt\lambda \, s)$ satisfies this (finite propagation speed of the wave equation). Set $p(s)=\sup _{\lambda \in \mathrm{Spec}\, \mathcal{L}}|P_s(\lambda )|$ and assume $p$ is locally integrable. For a measurable $\phi $ on $(0,\infty )$ with $\int _0^\infty |\phi (s)|\, p(s)\, ds{\lt}\infty $, define the bounded function $\Phi (\lambda )=\int _0^\infty \phi (s)P_s(\lambda )\, ds$ on $\mathrm{Spec}\, \mathcal{L}$, and the operator $\Phi (\mathcal{L})$ on $L^2(M,\mu )$.

Lemma 126 Lemma 3.13: locality estimate for $\Phi (\mathcal{L})$

If $f\in L^2(M,\mu )$ then, with $\| \cdot \| _2=\| \cdot \| _{L^2(M,\mu )}$,

\[ \| \Phi (\mathcal{L})f\| _{L^2(M\setminus \mathrm{supp}_r f)} \; \le \; \| f\| _2\int _r^\infty |\phi (s)|\, p(s)\, ds . \]

Proof ▶

Let $w(x)=\Phi (\mathcal{L})f(x)=\int _0^\infty \phi (s)P_s(\mathcal{L})f(x)\, ds$. If $x\notin \mathrm{supp}_r f$ then $P_s(\mathcal{L})f(x)=0$ whenever $s\le r$ (because $\mathrm{supp}\ P_s(\mathcal{L})f\subset \mathrm{supp}_s f\subseteq \mathrm{supp}_r f$ for $s\le r$), so $w(x)=\int _r^\infty \phi (s)P_s(\mathcal{L})f(x)\, ds$ there. By the integral (Minkowski) inequality and $\| P_s(\mathcal{L})f\| _2\le p(s)\| f\| _2$,

\[ \| w\| _{L^2(M\setminus \mathrm{supp}_r f)} \le \Bigl\| \int _r^\infty \phi (s)P_s(\mathcal{L})f\, ds\Bigr\| _2 \le \int _r^\infty \| \phi (s)P_s(\mathcal{L})f\| _2\, ds \le \int _r^\infty |\phi (s)|\, p(s)\, \| f\| _2\, ds. \qedhere \]

Corollary 127 Corollary 3.14: bilinear locality estimate

If $f,g\in L^2(M,\mu )$ and the distance between $\mathrm{supp}\, f$ and $\mathrm{supp}\, g$ is $D$, then

\[ \Bigl|\int _M f\, \Phi (\mathcal{L})g\, d\mu \Bigr| \; \le \; \| f\| _2\, \| g\| _2 \int _D^\infty |\phi (s)|\, p(s)\, ds . \]

Proof ▶

The integrand is supported on $\mathrm{supp}\, f$, which lies in $M\setminus \mathrm{supp}_D\, g$ since $\mathrm{dist}(\mathrm{supp}\, f, \mathrm{supp}\, g)=D$. Apply Lemma 126 to $g$ with $r=D$ and then Cauchy–Schwarz:

\[ \Bigl|\int _M f\, \Phi (\mathcal{L})g\, d\mu \Bigr| \le \| f\| _2\, \| \Phi (\mathcal{L})g\| _{L^2(M\setminus \mathrm{supp}_D g)} \le \| f\| _2\, \| g\| _2\int _D^\infty |\phi (s)|\, p(s)\, ds. \qedhere \]

Corollary 128 Corollary 3.15: Gaussian heat-semigroup estimate

If $f,g\in L^2(M,\mu )$ and $\mathrm{dist}(\mathrm{supp}\, f,\mathrm{supp}\, g)=D$, then

\[ \Bigl|\int _M f\, e^{-t\mathcal{L}}g\, d\mu \Bigr| \; \le \; \| f\| _2\, \| g\| _2 \int _D^\infty \frac{1}{\sqrt{\pi t}}\, e^{-s^2/4t}\, ds . \]

Proof ▶

Take $P_s(\lambda )=\cos (\sqrt\lambda \, s)$, so $p(s)=\sup _\lambda |\cos (\sqrt\lambda \, s)|\le 1$, and choose $\phi (s)=\frac{1}{\sqrt{\pi t}}e^{-s^2/4t}$. Then $\Phi (\lambda )=\int _0^\infty \frac{1}{\sqrt{\pi t}}e^{-s^2/4t} \cos (\sqrt\lambda \, s)\, ds=e^{-\lambda t}$, so $\Phi (\mathcal{L})=e^{-t\mathcal{L}}$. Now apply Corollary 127, bounding $\int _D^\infty |\phi |\, p\le \int _D^\infty \frac{1}{\sqrt{\pi t}}e^{-s^2/4t}\, ds$.

Corollary 129 Corollary 3.16: weaker Gaussian estimate

Under the hypotheses of Corollary 128,

\[ \Bigl|\int _M f\, e^{-t\mathcal{L}}g\, d\mu \Bigr| \; \le \; \| f\| _2\, \| g\| _2\, e^{-D^2/4t}. \]

Proof ▶

Substituting $u=s/(2\sqrt t)$ in the tail integral of Corollary 128,

\[ \int _D^\infty \frac{1}{\sqrt{\pi t}}e^{-s^2/4t}\, ds = \frac{2}{\sqrt\pi }\int _{D/2\sqrt t}^\infty e^{-u^2}\, du = \mathrm{erfc}\! \Bigl(\frac{D}{2\sqrt t}\Bigr) \le e^{-D^2/4t}, \]

using the standard bound $\mathrm{erfc}(x)\le e^{-x^2}$ for $x\ge 0$.

Definition 130 Laplace operator of a Riemannian metric, s3.4

Let $M$ be a smooth connected compact Riemannian manifold. In local coordinates $x_1,\dots ,x_n$, the Laplace operator is

\[ \Delta u \; =\; \frac{1}{\sqrt g}\sum _{i,j=1}^n \frac{\partial }{\partial x_i}\Bigl(\sqrt g\, g^{ij} \frac{\partial u}{\partial x_j}\Bigr), \]

where $g_{ij}$ is the metric tensor, $g=\det \| g_{ij}\| $, and $g^{ij}=\| g_{ij}\| ^{-1}$ are the contravariant components. The operator $\mathcal{L}=-\Delta $ is self-adjoint with discrete spectrum $0=\lambda _0{\lt}\lambda _1\le \lambda _2\le \cdots $ in $L^2(M,\mu )$, $\mu $ the Riemannian measure.

Definition 131 Boundary conditions on a manifold, s3.4

If $M$ has a boundary $\partial M$, impose

\[ \alpha \, u + \beta \, \frac{\partial u}{\partial \nu } = 0 \]

on $\partial M$, where $\alpha ,\beta $ are non-negative smooth functions with $\alpha (x)+\beta (x){\gt}0$ for all $x\in \partial M$. Both the Dirichlet ($\beta \equiv 0$) and Neumann ($\alpha \equiv 0$) conditions satisfy these assumptions, and each keeps $\mathcal{L}=-\Delta $ self-adjoint. When there is no boundary, or the Dirichlet/Neumann condition holds, there is a zero eigenvalue with constant eigenfunction $\phi _0=1/\sqrt{\mu M}$.

Lemma 132 Eigenfunction expansion of the heat kernel

Let $p(x,y,t)$ be the heat kernel, i.e. the unique fundamental solution of $\partial _t u-\Delta u=0$ (with the boundary condition 131 if $\partial M\neq \varnothing $), and let $\{ \phi _i\} $ be the orthonormal eigenfunctions with eigenvalues $\lambda _i$. Then

\[ p(x,y,t)\; =\; \sum _{i=0}^\infty e^{-\lambda _i t}\, \phi _i(x)\, \phi _i(y). \]

Theorem 133 Theorem 3.17: eigenvalue upper bounds via distance on a manifold

Let $M$ be a complete Riemannian manifold of finite volume (or a compact manifold with the Neumann or Dirichlet boundary condition), $\mathcal{L}=-\Delta $ with spectrum $0=\lambda _0{\lt}\lambda _1\le \lambda _2\le \cdots $. For two arbitrary measurable disjoint sets $X,Y\subset M$,

\[ \lambda _1 \; \le \; \frac{1}{\mathrm{dist}(X,Y)^2} \Bigl(1+\log \frac{(\mu M)^2}{\mu X\, \mu Y}\Bigr)^2 . \]

Moreover, if $X_0,X_1,\dots ,X_k$ are $k+1$ disjoint subsets with pairwise distance $\ge D{\gt}0$, then for any $k\ge 1$,

\[ \lambda _k \; \le \; \frac{1}{D^2} \Bigl(1+\sup _{i\neq j}\log \frac{(\mu M)^2}{\mu X_i\, \mu X_j}\Bigr)^2 . \]

Proof ▶

Normalize the eigenfunctions $\phi _i$ orthonormally, with $\phi _0=1/\sqrt{\mu M}$. Two facts about the heat kernel $p(x,y,t)$ are used: the eigenfunction expansion (Lemma 132), and the Gaussian estimate, obtained from Corollary 129, that for disjoint Borel sets $X,Y$ with $D=\mathrm{dist}(X,Y)$ and functions $f,g$,

\[ \int _X\! \int _Y p(x,y,t)f(x)g(y)\, \mu (dx)\, \mu (dy) \le \Bigl(\int _X f^2\int _Y g^2\Bigr)^{1/2}\exp \! \Bigl(-\frac{D^2}{4t}\Bigr). \tag {$\ast $} \]

Case $k=2$ (bounding $\lambda _1$). Set $I(f,g)=\int _X\! \int _Y p(x,y,t)f(x)g(y)\, \mu \mu $. By the eigenfunction expansion, $I(f,g)=\sum _{i\ge 0}e^{-\lambda _i t}\int _X f\phi _i\int _Y g\phi _i$. Write $f_i=\int _X f\phi _i$ (the Fourier coefficients of $f\psi _X$) and $g_i=\int _Y g\phi _i$. Then, using $\lambda _0=0$ and Cauchy–Schwarz on the tail,

\[ I(f,g)= f_0g_0+\sum _{i\ge 1}e^{-\lambda _i t}f_ig_i \ge f_0g_0 - e^{-\lambda _1 t}\| f\psi _X\| _2\, \| g\psi _Y\| _2 . \]

Comparing with $(\ast )$,

\[ e^{-\lambda _1 t}\| f\psi _X\| _2\| g\psi _Y\| _2 \ge f_0g_0-\| f\psi _X\| _2\| g\psi _Y\| _2\, e^{-D^2/4t}. \]

Choose $t=\dfrac {D^2}{4\log \frac{2\| f\psi _X\| _2\| g\psi _Y\| _2}{f_0g_0}}$, so the subtracted term equals $\tfrac 12 f_0g_0$; then $e^{-\lambda _1 t}\| f\psi _X\| _2\| g\psi _Y\| _2\ge \tfrac 12 f_0g_0$, whence $\lambda _1\le \frac1t\log \frac{2\| f\psi _X\| _2\| g\psi _Y\| _2}{f_0g_0}$. Substituting the value of $t$,

\[ \lambda _1\le \frac{4}{D^2} \Bigl(\log \frac{2\| f\psi _X\| _2\| g\psi _Y\| _2}{f_0g_0}\Bigr)^2 . \]

Take $f=g=\phi _0$. Then $f_0=\int _X\phi _0^2=\mu X/\mu M$, $\| f\psi _X\| _2=(\int _X\phi _0^2)^{1/2}=\sqrt{f_0}$, and likewise for $Y$, so $\frac{2\| f\psi _X\| _2\| g\psi _Y\| _2}{f_0g_0}=\frac{2}{\sqrt{f_0g_0}} =\frac{2\mu M}{\sqrt{\mu X\, \mu Y}}$ and

\[ \lambda _1\le \frac{1}{D^2} \Bigl(\log \frac{4}{\int _X\phi _0^2\int _Y\phi _0^2}\Bigr)^2 = \frac{1}{D^2}\Bigl(\log \frac{4(\mu M)^2}{\mu X\, \mu Y}\Bigr)^2 , \]

which is the stated first inequality (up to the additive constant, since $\log 4$ is replaced by $1$ in the clean form).

General $k{\gt}2$. For a function $f$ write $f_i^{\, j}=\int _{X_j}f\phi _i$. As in $(\ast )$, with $I_{lm}(f,f)=\int _{X_l}\! \int _{X_m}p(x,y,t)f(x)f(y)\, \mu \mu $,

\[ I_{lm}(f,f)\le \| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2\, e^{-D^2/4t}, \]

while the eigenfunction expansion gives the lower bound

\[ I_{lm}(f,f)\ge e^{-\lambda _1 t}f_0^{\, l}f_0^{\, m} +\sum _{i=1}^{k-1}e^{-\lambda _i t}f_i^{\, l}f_i^{\, m} -e^{-\lambda _k t}\| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2 . \]

Regard $f^{m}=(f_1^{\, m},\dots ,f_{k-1}^{\, m})$ as $k+1$ vectors in $\mathbb {R}^{k-1}$ with the (positive-weight) scalar product $\langle v,w\rangle =\sum _{i=1}^{k-1}v_i w_i e^{-\lambda _i t}$; by Lemma 119 there exist $l\neq m$ with $\langle f^l,f^m\rangle \ge 0$, eliminating the middle sum. Combining the two bounds gives

\[ e^{-\lambda _k t}\| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2 \le f_0^{\, l}f_0^{\, m} -\| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2\, e^{-D^2/4t}. \]

Choosing $t=\min _{l\neq m}\dfrac {D^2}{4\log \frac{2\| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2}{f_0^{\, l}f_0^{\, m}}}$ makes the right-hand side $\ge \tfrac 12 f_0^{\, l} f_0^{\, m}$, so $\lambda _k\le \frac1t\log \frac{2\| f\psi _{X_l}\| _2\| f\psi _{X_m}\| _2}{f_0^{\, l}f_0^{\, m}}$. Substituting $t$ and taking $f=\phi _0$ yields the second inequality.