Dependencies

The Buckyball (truncated icosahedron, the molecule \(C_{60}\)) is the Cayley graph on the alternating group \(A_5\) with symmetric edge generating set \(\{ a,a^{-1},b\} \) where \(a=(1\, 2\, 3\, 4\, 5)\) and \(b=(1\, 2)(3\, 4)\). It has \(|A_5|=60\) vertices; the edges from \(a,a^{-1}\) are the “single bonds” and the edges from \(b\) the “double bonds”. Equivalently \(A_5\cong PSL(2,5)\). The irreducible representations of \(A_5\) have dimensions \(1,3,3',4,5\) with \(1^2+3^2+3^2+4^2+5^2=60\).

Take \(X=\mathbb {R}^3\) and equilibrium positions \(\mathbf u\) of the vertices. A small displacement \(h:V\to \mathbb {R}^3\) moves vertex \(u\) to \(\mathbf u+h(u)\). With spring constants \(k_{u,w}\) on the edges, Hooke’s law gives potential energy

Expanding to second order in \(h\), with the unit vector \(\omega _{u,w}=(\mathbf u-\mathbf w)/\| \mathbf u-\mathbf w\| \),

so the edge operator of the vibrational Laplacian (Definition 303) is the rank-one \(3\times 3\) matrix

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

Fix column sums \(c_1,\dots ,c_n\) and row sums \(r_1,\dots ,r_m\). Let \(\Gamma \) have vertex set the collection of all \(m\times n\) matrices with integral (possibly negative) entries. Two vertices \(x,y\) are adjacent if they differ in exactly four entries determined by two columns \(i,j\) and two rows \(k,m'\):

Then \(\Gamma \) is a homogeneous graph whose edge generating set consists of all \(2\times 2\) submatrices \(\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}\), and it may be viewed as embedded in \(\mathbb {R}^{mn}\) (in fact in an \((mn-m-n+1)\)-dimensional subspace). Let \(S\) be the set of all \(m\times n\) matrices with nonnegative integral entries and the prescribed row and column sums, and let \(M\) be the submanifold

Then \(S = M\cap V(\Gamma )\) is a convex subgraph of the lattice graph \(\Gamma \).

Let \(S\) be the space of all \(m\times n\) matrices with non-negative integral entries having fixed column sums \(c_1,\dots ,c_n\) and row sums \(r_1,\dots ,r_m\). Construct a homogeneous graph \(\Gamma \) whose vertices are all \(m\times n\) matrices with integral (possibly negative) entries and the same row and column sums, where two matrices \(u,v\) are adjacent iff they differ in exactly four entries determined by two columns \(i,j\) and two rows \(k,\ell \) with

i.e. the edge generating set consists of all \(2\times 2\) submatrix moves \(\left(\begin{smallmatrix} 1 & -1 \\ -1 & 1 \end{smallmatrix}\right)\). Then \(S\) is the intersection of the halfplanes \(\{ \)matrices whose \((i,j)\) entry is non-negative\(\} \), and each such halfplane is convex; consequently, by 346, \(S\) is a convex subgraph of \(\Gamma \).

Let \(\Gamma \) be distance transitive of diameter \(D\), fix a vertex \(v\), and let \(V_i=\{ u:d(u,v)=i\} \) for \(i=0,\dots ,D\). Contract each \(V_i\) to a single vertex \(v_i\) to form a weighted path \(P\) on the \(D+1\) vertices \(v_0,\dots ,v_D\):

• the edge \(\{ v_i,v_{i+1}\} \) has weight equal to the number of edges of \(\Gamma \) between \(V_i\) and \(V_{i+1}\);

• the loop \(\{ v_i,v_i\} \) has weight equal to twice the number of edges of \(\Gamma \) with both endpoints in \(V_i\) plus the number of loops in \(V_i\).

By distance transitivity these counts are the intersection numbers of \(\Gamma \): every \(x\in V_i\) has the same number \(b_i\) of neighbours in \(V_{i+1}\), \(a_i\) in \(V_i\), and \(c_i\) in \(V_{i-1}\), with \(b_i+a_i+c_i=k\) and \(c_{i+1}{\gt}0\).

Work in the finite field \(GF(p^t)\simeq GF(p)(x)\); for \(x\in GF(p^t)\) consider the coset \(x+GF(p)\), and, via a generator \(g\) of \(GF^*(p^t)\), identify each \(y=g^k\) with the integer \(k\in \{ 1,\dots ,p^t-1\} \). Let \(X\) be the set of integers corresponding to the coset \(x+GF(p)\). The coset graph \(C_{p,t}\) has vertices \(1,\dots ,p^t-1=n\), with \(\{ a,b\} \) an edge iff \(a+b\in X\). Its eigenvalues are \(\sum _{a\in X}\theta ^a\) over all \(n\)th roots of unity \(\theta \). By the Weil-type character-sum inequality, if \(\theta \) is a \((p^t-1)\)th root of unity with \(\theta \ne 1\) then \(\bigl|\sum _{a\in X}\theta ^a\bigr|\le (t-1)\sqrt p\). Hence \(C_{p,t}\) has edge density \(n^{1-1/t}\) and eigenvalues

Let \(\Gamma \) be the Cayley graph with vertex set \(\mathbb {Z}_q\times \mathbb {Z}_2\) and symmetric edge generating set \(\{ (k,0):k\in \mathbb {Z}_q\} \cup \{ (0,1)\} \). Concretely \(\Gamma \) is formed by two complete graphs on \(q\) vertices joined by a perfect matching (the “dumb-bell”). Its degree is \(k=q\) and its diameter is \(D=2\), and its Cheeger constant is

Thus in Theorem 277 the factor \(\operatorname {index}\Gamma \) genuinely occurs: here \(\operatorname {vol}\Gamma \) is large but the matching class is small, forcing \(\operatorname {index}\Gamma \) to be of order \(q\).

Fix an integer \(r{\gt}0\); let \(p=mr+1\) be a prime with \(p\equiv 1\pmod4\), and let \(T\subset \mathbb Z_p^*\) consist of \(t\) nonzero residues such that for distinct \(a,b\in T\) the quotient \(ab^{-1}\) is not an \(r\)th power in \(\mathbb Z_p^*\). The graph \(P_{p,r,t}\) has vertex set \(\{ 0,1,\dots ,p-1\} \), with \(i,j\) adjacent iff \(i+j=aq\) for some \(a\in T\) and some \(r\)th power \(q\). Its eigenvalues are

By Deligne’s theorem, \(\bigl|\sum _{x\in \mathbb Z_p}e^{2\pi i jx^2/p}\bigr|\le (r-1)\sqrt p\), so

Fix integers \(t\ge 1\) and \(n\), and let \(\Gamma _t\) have vertex set

where \((a_1,\dots ,a_i,\dots ,a_j,\dots ,a_t)\) is adjacent to \((a_1,\dots ,a_i+1,\dots ,a_j-1,\dots ,a_t)\) for all \(1\le i,j\le t\). For a fixed \(i\), the halfplane

is strongly convex, and the intersection \(\bigcap _i H_i=\{ (a_1,\dots ,a_t)\in V(\Gamma _t): a_i\ge 0\ \forall i\} \) is strongly convex.

The intersection graph \(G(n,r,k)\) has vertex set all \(r\)-subsets of \(\{ 1,\dots ,n\} \), and two vertices \(A,B\) are adjacent iff \(|A\cap B|=k\). It is a homogeneous graph with associated group the symmetric group \(S_n\) and isotropy group \(S_r\times S_{n-r}\) (permuting inside and outside a fixed \(r\)-set). The Petersen graph is the special case of \(2\)-subsets of \(\{ 1,\dots ,5\} \) adjacent when disjoint (\(|A\cap B|=0\)).

The \(m\)-petal graph (friendship graph) on \(n = 2m+1\) vertices \(v_0, v_1, \dots , v_{2m}\) has edges \(\{ v_0, v_i\} \) for \(1\le i\le 2m\) and \(\{ v_{2i-1}, v_{2i}\} \) for \(1\le i\le m\). Its Laplacian eigenvalues are \(0\), \(\tfrac 12\) (with multiplicity \(m-1\)), and \(\tfrac 32\) (with multiplicity \(m+1\)), so \(\max _{i\ne 0}|1-\lambda _i| = \tfrac 12\). However, \(\sqrt{\frac{n-d_H}{(n-1)d_H}} \to \frac{1}{\sqrt2}\) as \(m\to \infty \), so the analogue of Lemma 35 obtained by replacing \(k\) with the harmonic mean degree \(d_H\) fails.

Construct a major-access network \(M(n)\) with \(n\) inputs and \(24n\) outputs by combining two copies of \(M(n/2)\) and two copies of the bipartite Ramanujan graph \(R(12n,5)\) (with \(12n\) inputs and degree \(p+1=6\)). Then \(M(n)\) is a major-access network, and its edge count satisfies \(e(M(n))=2\, e\! \left(M(\tfrac n2)\right)+6\cdot 12\cdot 2n\), so \(M(n)\) has at most \(144\, n\log n\) edges and the resulting non-blocking network has at most \(288\, n\log n\) edges.

Set \(n=m^2\) and \(V=\mathbb Z_m\times \mathbb Z_m\). Consider the six transformations of \(V\) to itself (addition modulo \(m\)):

The Margulis graph \(M_n=(V,E)\) has an edge \(\{ u,v\} \) whenever \(u=\sigma _i(v)\) or \(v=\sigma _i(u)\) for some \(i\) (a loop adds \(2\) to the degree). Then \(M_n\) is \(12\)-regular and

The graph \(M_n^k\) has vertex set \(V\), with vertices \(u,v\) joined by \(s\) parallel edges, where \(s\) is the number of walks of length \(k\) from \(v\) to \(u\) in \(M_n\). Consequently the adjacency matrix of \(M_n^k\) equals \(A^k\), and its eigenvalues are \(\rho _i^k\), where the \(\rho _i\) are the eigenvalues of the adjacency matrix \(A\) of \(M_n\).

Let \(p\) be a prime with \(p\equiv 1\pmod4\). The Paley graph \(P_p\) has vertex set \(\{ 0,1,\dots ,p-1\} \), and vertices \(i,j\) are adjacent iff \(i-j\) is a nonzero quadratic residue modulo \(p\). It is \(\tfrac {p-1}{2}\)-regular, and, being a Cayley graph of \(\mathbb Z_p\), its normalized-Laplacian eigenvalues are

For \(j\not\equiv 0\) the Gauss sum \(\sum _{x\in \mathbb Z_p^*} e^{2\pi i jx^2/p}\) equals \(\sqrt p-1\) or \(-\sqrt p-1\), whence

Moreover \(P_p\) contains every graph on \(c\sqrt{\log p}\) vertices as an induced subgraph.

Let \(p\) be a prime. The Paley sum graph \(\bar P_p\) has vertex set \(\{ 0,\dots ,p-1\} \) and vertices \(i,j\) are adjacent iff \(i+j\) is a quadratic residue modulo \(p\). With \(\phi _j(k)=e^{2\pi i jk/p}\) the eigenvectors of the Paley graph, the eigenvectors of \(\bar P_p\) are

where \(\lambda _j\) is the eigenvalue of \(\phi _j\) for the Paley graph, and the eigenvalues of \(\bar P_p\) are exactly \(1\pm \sqrt{|(1-\lambda _j)(1-\lambda _{-j})|}\). For \(p\equiv 1\pmod4\) the eigenvalues coincide with those of the Paley graph. For \(p\equiv 3\pmod4\) the eigenvalues are \(0\), \(1-\tfrac {1}{2\sqrt{p}-1}\) (with multiplicity \(\tfrac {p-1}{2}\)) and \(1+\tfrac {1}{2\sqrt{p}-1}\) (with multiplicity \(\tfrac {p-1}{2}\)). Both \(P_p\) and \(\bar P_p\) have edge density about \(\tfrac 12\).

Let \(p,q\) be primes each congruent to \(1\) modulo \(4\). Let \(H(\mathbb Z)\) be the integral quaternions \(\{ a_0+a_1 i+a_2 j+a_3 k:a_\ell \in \mathbb Z\} \), and for \(\alpha =a_0+a_1i+a_2j+a_3k\) put \(N(\alpha )=\alpha \bar\alpha =a_0^2+a_1^2+a_2^2+a_3^2\). There are exactly \(p+1\) conjugate pairs \(\{ \alpha ,\bar\alpha \} \) with \(N(\alpha )=p\), \(\alpha \equiv 1\pmod2\) and \(a_0{\gt}0\); let \(S\) be the set of associated \(2\times 2\) matrices \(\tilde\alpha =\begin{pmatrix} a_0+ia_1 & a_2+ia_3 \\ -a_2+ia_3 & a_0-ia_1 \end{pmatrix}\), viewed in \(PGL(2,\mathbb Z/q\mathbb Z)\). The graph \(X^{p,q}\) is the Cayley graph of \(PSL(2,\mathbb Z/q\mathbb Z)\) relative to \(S\) when the Legendre symbol \(\left(\tfrac pq\right)=1\), and the Cayley graph of \(PGL(2,\mathbb Z/q\mathbb Z)\) relative to \(S\) (a bipartite graph, equal to \(X^{p,q}\)’s set-theoretic complement) when \(\left(\tfrac pq\right)=-1\). For \(\left(\tfrac pq\right)=1\) the graphs are \((p+1)\)-regular with \(q(q^2-1)/2\) vertices, and

so \(X^{p,q}\) is a Ramanujan graph; the graphs with \(\left(\tfrac pq\right)=-1\) are bipartite expander graphs.

A superconcentrator \(S(n)\) is built recursively: place a perfect matching between the \(n\) inputs and \(n\) outputs, and add a concentrator \(B\) with \(n\) inputs and \(\tfrac 56 n\) outputs which is an \((n,\tfrac 56,6,\tfrac 12,\tfrac 12)\)- concentrator, feeding a recursively constructed \(S(\tfrac 56 n)\). Concretely, the first \(\tfrac n6\) inputs of \(B\) each have degree \(5\) and are joined to \(\tfrac 56 n\) distinct outputs, while the remaining \(\tfrac 56 n\) inputs are joined to the outputs by a Ramanujan graph of degree \(6=p+1\). Then \(S(n)\) is a superconcentrator whose edge count satisfies

so \(S(n)\) has at most \(76n\) edges.

Question 2 asks whether the hypothesis

forces \(\operatorname {disc} G \le 100\alpha \). The answer is negative. Let \(H\) have vertex set \(A\cup B\) with \(|A| = |B| = n/2\) and \(A\cap B = \emptyset \), where: the induced subgraph on \(A\) is a random graph of edge density \(1/2\); the induced subgraph on \(B\) is a random graph of edge density \(1/4\); and the bipartite subgraph between \(A\) and \(B\) has edge density \(1/3\). Then \(H\) satisfies (5.2), yet \(\operatorname {disc} H\) is large (about \(cn^2\) with \(c \ge 0.01\)), and \(H\) is not even almost regular. Thus "almost regular” is a necessary condition for quasi-randomness.

Let \(q\) be a prime power. Define a graph \(G\) with vertex set

and edge set

A result of Frankl–Wilson implies that \(G\) contains no clique and no independent set of size \(\binom {m}{q-1}\). Taking \(m = q^3\) produces a graph on \(n = \binom {m}{q^2-1}\) vertices containing no clique and no independent set of size

markedly deviating from the Ramsey bounds of random graphs.

Let \(G\) have eigenfunction \(f\) associated with \(\lambda _1\). For each vertex \(v\) set

Then \(\lambda _1{\gt}1-\sqrt{1-\alpha ^2}\).

For a graph \(G\),

where \(f\) ranges over functions with

For any connected simple graph \(G\),

For a connected graph \(G\) on vertex set \(V\) and any vertex \(v\), applying Theorem 331 to the induced subgraph \(S=V\setminus \{ v\} \) (so \(\delta S=\{ v\} \)) puts the rooted spanning forests of \(S\) in one-to-one correspondence with the spanning trees of \(G\). Consequently the number of spanning trees of \(G\) equals the determinant of the cofactor of the combinatorial Laplacian \(L=T-A\) obtained by deleting the row and column of \(v\).

Let \(S\) be a convex subgraph of a simple lattice graph, embedded into a \(d\)-dimensional manifold \(M\) with convex boundary. Then the Neumann eigenvalue \(\lambda _1\) of \(S\) satisfies

where \(D(S)\) is the graph diameter of \(S\), \(\mathcal{K}\) is the set of edge generators, and \(c_0\) is an absolute constant depending only on the simple lattice graph.

For any graph \(G\),

Suppose \(G\) is a regular graph which is not complete. Then

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.

Suppose \(G\) is a regular graph which is not complete. Then

(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)\).)

For \(f:S\to \mathbb R\) with \(f(y)=0\) for \(y\in \delta S\) one has, for all \(x\in S\), \(\mathcal Lf(x)=\mathcal L_S f(x)\), where \(\mathcal L_S\) is the principal submatrix of \(\mathcal L\) on the rows and columns indexed by \(S\). Since \(\delta S\ne \emptyset \), \(\mathcal L_S\) is nonsingular; all its eigenvalues are positive; they are exactly the Dirichlet eigenvalues; and

Let \(X\) be a subset of vertices in a graph \(G\). Then the edge boundary \(\partial X\) satisfies

Let \(X\) be a subset of vertices in a \(k\)-regular graph \(G\) on \(n\) vertices. Then

Let \(X\) be a subset of vertices in a graph \(G\). Then

For a weighted graph \(G\) with isoperimetric dimension \(\delta \), suppose \(f\) satisfies \(\sum _x\lambda f^p(x)d_x\ge \sum _x f^{p-1}(x)Lf(x)\) (for the relevant range of \(p\)). Then

for some absolute constant \(c\).

Under the hypotheses of 355, for all \(x\in S\) and \(a\in \mathcal{K}\),

Under the hypotheses of 352, for every \(x\in V(\Gamma )\),

Let \(S\) be a strongly convex subgraph in an abelian homogeneous graph \(\Gamma \) with edge generating set \(\mathcal{K}\) of \(k\) generators, and let \(f\colon S\to \mathbb {R}\) be an eigenfunction with Neumann eigenvalue \(\lambda \). Then for all \(x\in S\), \(a\in \mathcal{K}\) (with \(ax\in S\)),

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

Under the hypotheses of Corollary 128,

In a connected graph \(G\) with isoperimetric dimension \(\delta \) and isoperimetric constant \(c_\delta \), for an arbitrary \(f:V(G)\to \mathbb {R}\),

In a connected graph \(G\) with isoperimetric dimension \(\delta \) and isoperimetric constant \(c_\delta \), for \(f:V(G)\to \mathbb {R}\), a vertex \(w\), and \(m\) as in Theorem 388, define the truncated function

the boundary count

and the level set \(S_w=\{ v:f(v)\ge f(w)\} \) if \(f(w)\ge m\), resp. \(S_w=\{ u:f(u)\le f(w)\} \) if \(f(w){\lt}m\). Then

If, in addition to the hypotheses of Lemma 414, \(G\) and \(G'\) are regular with degrees \(k\) and \(k'\) respectively, then

For any graph \(G\) with at least one edge, \(\ \omega (G)\le \sigma (G)\le \chi (G)\).

For a \(k\)-regular graph \(G\) on \(n\) vertices, suppose there is a set \(P\) of \(\binom {n}{2}\) paths joining all pairs of vertices such that each edge of \(G\) is contained in at most \(m\) paths in \(P\). Then the Cheeger constant satisfies

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

The modified Cheeger constant of the cartesian product satisfies

For the \(n\)-cube \(Q_n\), \(rc(Q_n)\ge 2\).

For any graph \(G\),

where \(G'\) ranges over all induced subgraphs of \(G\) and \(W\) over all weight matrices for \(G'\). This inequality is strict for some graphs (for instance odd cycles).

For a graph \(G\),

where \(\lambda _{max}\) is the largest eigenvalue of the (unweighted) normalized Laplacian, and more generally the right-hand side may be maximized over all induced subgraphs \(G'\) of \(G\).

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

For a connected graph \(G\), \(2g_G\ge \lambda _1\).

For all \(A\subseteq V(G)\),

A homogeneous graph whose associated group \(\mathcal{H}\) is abelian is called an abelian homogeneous graph. Every abelian homogeneous graph is invariant (in the sense of 339); more generally, if \(\mathcal{H}\) is nonabelian but \(\mathcal{K}\) is a subgroup of \(\mathcal{H}\), then \(\Gamma \) is still invariant.

A \(k\)-access graph has the property that for any set \(S\) of vertex-disjoint paths connecting inputs to outputs, a new input can be connected to \(k\) different outputs by paths containing no vertex in \(S\). If \(k\) is at least half of the total number of outputs, the \(k\)-access graph is a major-access network. A non-blocking network can be formed by combining a major-access network and its mirror image.

The adjacency matrix \(A\) of \(G\) is the \(n\times n\) matrix with \(A(x,y) = 1\) if \(x\) is adjacent to \(y\), and \(A(x,y)=0\) otherwise.

A family of graphs \(G\) (with \(|V(G)|=n\to \infty \)) is almost regular if it satisfies

where \(\rho _v=d_v/n\) and \(\rho =\sum _v d_v/n^2\). Equivalently, all but \(o(n)\) vertices have degree within a \((1+o(1))\) factor of the average degree.

For every family of connected \(k\)-regular graphs with the number of vertices tending to infinity, the spectral gap satisfies

equivalently the second largest adjacency eigenvalue obeys \(\mu _2\ \ge \ 2\sqrt{k-1}-o(1)\). Hence a Ramanujan graph (Definition 235) attains, up to the \(o(1)\) term, the best possible spectral gap for a fixed degree \(k\).

For \(S\subseteq V(G)\) the vertex boundary is \(\delta (S)=N(S)\setminus S=\{ x\notin S : x\sim y \text{ for some }y\in S\} \). A regular graph \(G\) on \(n\) vertices is a \(c\)-expander if every subset \(S\subseteq V(G)\) satisfies

The constant \(c\) is called the expander coefficient.

The cartesian product \(G\, \square \, H\) has vertex set \(V(G)\times V(H)\), with \((u,v)\) adjacent to \((u',v')\) if and only if either \(u=u'\) and \(v\sim v'\) in \(H\), or \(v=v'\) and \(u\sim u'\) in \(G\).

A Cayley graph is a homogeneous graph whose isotropy group is trivial, \(\mathcal I=\{ \mathrm{id}\} \). Its vertices are labelled by the associated group \(\mathcal H\), and \(\{ g,h\} \) is an edge if and only if \(g^{-1}h\in \mathcal K\) for the (symmetric) edge generating set \(\mathcal K\). For example, the cycle \(C_n\) is a Cayley graph with associated group \(\mathbb {Z}_n=\mathbb {Z}/n\mathbb {Z}\).

For \(S\subseteq V\) the characteristic vector \(\psi _S : V\to \{ 0,1\} \) is

It satisfies \(|S| = \langle \psi _S, \mathbf1\rangle \) and, with \(T\) the diagonal degree matrix, \(\mathrm{vol}\, S = \langle \psi _S, T\mathbf1\rangle = \langle \psi _S, T\psi _S\rangle \).

For \(\emptyset \ne S\subsetneq V(G)\) put

The Cheeger constant of \(G\) is

Equivalently, for every \(\emptyset \ne S\subsetneq V(G)\) one has \(|\partial S|\ge h_G\, \min (\mathrm{vol}\, S,\mathrm{vol}\, \bar S)\); in particular \(|\partial S|\ge h_G\, \mathrm{vol}\, S\) whenever \(\mathrm{vol}\, S\le \mathrm{vol}\, \bar S\).

The \(\chi \)-squared distance after \(s\) steps is

The chromatic number \(\chi (G)\) is the smallest integer \(k\) such that the vertices of \(G\) can be \(k\)-colored so that any two adjacent vertices receive different colors.

The clique number \(\omega (G)\) is the number of vertices of a largest complete subgraph (clique) of \(G\).

Let \(T\) denote the diagonal degree matrix, with \((v,v)\)-entry equal to \(d_v\). The combinatorial Laplacian of \(G\) is \(L = T - A\), i.e.

Let \(0=\lambda '_0\le \lambda '_1\le \cdots \le \lambda '_{n-1}\) be the eigenvalues of \(L=T-A\). Then

\(f\) ranging over functions with \(\sum _v f(v)=0\), not identically zero. The denominator carries no factor \(d_v\), unlike \(\mathcal L\).

An \((n,\theta ,k,\alpha ,\beta )\)-concentrator is a bipartite graph with \(n\) inputs, \(\theta n\) outputs and \(kn\) edges, such that every input subset \(A\) with \(|A|\ge \alpha n\) has at least \(\beta n\) neighbors among the outputs.

A weight function \(w\) is consistent if for every vertex \(v\)

The weight \(w_0\) is consistent; \(w_1\) need not be. For a consistent \(w\) the associated random walk has transition probability \(P(u,v)=w(u,v)/w(v)\).

Given integer vectors \(\bar r=(r_1,\dots ,r_m)\) and \(\bar c=(c_1,\dots ,c_n)\) with \(r_i,c_j\ge 0\) and \(\sum _i r_i=\sum _j c_j\), let \(\mathcal{T}=\mathcal{T}(\bar r,\bar c)\) be the set of all \(m\times n\) arrays \(T\) with nonnegative integer entries satisfying

The associated Neumann walk on \(\mathcal{T}\) moves between tables that differ by one basic move (an edge generator of the contingency-table lattice graph of Construction 371).

A contraction of a weighted graph \(G\) identifies two distinct vertices \(u,v\) into a single vertex \(v^{*}\), with the incident weights

For a subset \(X\) of vertices let \(N^{*}(X)=\{ y : y\in X\text{ or } y\sim x\text{ for some }x\in X\} \). An induced subgraph \(S\) of a homogeneous graph \(\Gamma \) with vertex boundary \(\delta S\) is convex if it has the boundary expansion property: for every subset \(X\subseteq \delta S\),

In words, every subset \(X\) of the boundary \(\delta S\) has at least \(|X|\) neighbors lying outside \(S\cup \delta S\).

For a vertex \(v\) of a graph \(G\), the degree \(d_v\) is the number of vertices adjacent to \(v\). A vertex \(v\) is isolated if \(d_v = 0\). A graph is nontrivial if it contains at least one edge.

The deviation of a graph \(G\) with edge density \(\rho \) is

where \(x,y,z,w\) range independently over all vertices of \(G\). In the special case \(\rho =\tfrac 12\), the deviation equals \(\tfrac {1}{16 n^4}\) times the number of “even” \(4\)-cycles minus the number of “odd” \(4\)-cycles, where a \(4\)-cycle \(\{ x,y,z,w\} \) is called even if \(\chi (x,y)\chi (y,z)\chi (z,w)\chi (w,x)\) is positive.

A family of graphs \(G\) has the deviation property if

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)\).

A function \(f:V\to \mathbb {R}\) satisfies the Dirichlet boundary condition for \(S\) if \(f(x)=0\) for every vertex \(x\in \delta S\). We write \(f\in D^{*}\) to denote that \(f\) satisfies this condition.

Let \(S\subseteq V\) with \(\delta S\ne \emptyset \). The Dirichlet eigenvalues of the induced subgraph on \(S\) are defined for functions in \(D^{*}\) (satisfying \(f(x)=0\) for \(x\in \delta S\)) by

and in general

where \(C_i\) is spanned by the eigenfunctions \(\phi _j\) achieving \(\lambda _j\), \(1\le j\le i\). We write \(\lambda ^{(D)}=\lambda _1^{(D)}\) and index by \(1\le i\le |S|\).

For an induced subgraph \(S\) with non-empty boundary \(\delta S\) and a boundary datum \(\sigma :\delta S\to \mathbb R\), the energy of a function \(f\) is

the sum ranging over edges with at least one endpoint in \(S\). The corresponding partition function at coupling \(c{\gt}0\) is

where \(f\) ranges over all functions on \(S\cup \delta S\) whose restriction to \(\delta S\) equals \(\sigma \).

Let \(G\) have vertex set \(V\), \(|V| = n\), and edge density \(\rho \). For \(S\subseteq V\) the discrepancy of \(S\) is

For \(0 {\lt} \alpha \le 1\) the \(\alpha \)-discrepancy of \(G\) is the maximum discrepancy over all \(S\) with \(|S| = \lfloor \alpha n\rfloor \),

and the discrepancy of \(G\) is

The \(\alpha \)-discrepancy is a quantitative version of the Ramsey property; determining it is NP-complete in general, which motivates the eigenvalue upper bounds below.

Let \(\{ G_n\} \) be a family of graphs with \(|V(G_n)| = n\to \infty \) and edge densities \(\rho = \rho (G_n)\). The family satisfies the discrepancy property \(\mathrm{DISC}\) if

equivalently, for all \(X,Y\subseteq V(G_n)\),

In the general (not necessarily almost-regular) normalisation this is expressed through the volume-weighted count as \(\bigl| e(X,Y) - \tfrac {\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\bigr| = o(\mathrm{vol}\, G)\).

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)\).

For two subsets \(X,Y\) of vertices of \(G\), the distance between \(X\) and \(Y\) is

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\)).

A graph \(\Gamma \) is distance transitive if for any two pairs of vertices \(\{ x,y\} \) and \(\{ z,w\} \) with \(d(x,y)=d(z,w)\) there is an automorphism \(f\) with \(f(x)=z\) and \(f(y)=w\).

For \(S\subseteq V(G)\) the edge boundary \(\partial S\) consists of all edges with exactly one endpoint in \(S\):

Writing \(\bar S=V(G)-S\) for the complement, we have \(\partial S=\partial \bar S=E(S,\bar S)\), where \(E(A,B)\) denotes the set of edges with one endpoint in \(A\) and one endpoint in \(B\).

For a graph \(G\) on \(n\) vertices with \(e\) edges, the edge density is

Equivalently, with \(A\) the adjacency matrix, \(\mathbf1\) the all-ones vector and \(J = \mathbf1\mathbf1^{*}\) the all-ones matrix,

since \(\langle \mathbf1,A\mathbf1\rangle = 2e\) and \(\langle \mathbf1,J\mathbf1\rangle = n^2\).

Using the counting measure (number of vertices) rather than the volume, define for \(\emptyset \ne S\subsetneq V(G)\)

\(h'_G\) is called the isoperimetric number (the edge-expansion constant) of \(G\).

Let \(\Gamma \) be a homogeneous graph with associated group \(\mathcal H\) and isotropy group \(\mathcal I\) at \(v\), and identify \(V(\Gamma )\) with \(\mathcal H/\mathcal I\). An edge generating set is a set \(\mathcal K\subseteq \mathcal H\) such that every edge of \(\Gamma \) has the form \(\{ v,gv\} \) for some \(g\in \mathcal K\). For an undirected graph one requires \(g\in \mathcal K\) if and only if \(g^{-1}\in \mathcal K\); \(\mathcal K\) is a union of double cosets, \(\mathcal K = \mathcal I\mathcal K\mathcal I\).

Let \(S^{*}\) denote the set of edges consisting of all edges of \(G\) with both endpoints in \(S\) together with all edges of the edge boundary \(\partial S\) (edges with exactly one endpoint in \(S\)).

A graph \(G\) is edge-transitive if for any two edges \(\{ x,y\} ,\{ z,w\} \in E(G)\) there is an \(f\in \mathrm{Aut}(G)\) with \(\{ f(x),f(y)\} =\{ z,w\} \).

Let \(G\) have vertex set \(V\) and edge set \(E\). For \(X,Y\subseteq V\) (not necessarily disjoint) put

Here \(E(X,Y)\) consists of ordered pairs, so \(e(S,S)\) counts every edge inside \(S\) twice. We also write \(e(S)\) for the number of (unordered) edges with both endpoints in \(S\), so \(e(S,S) = 2e(S)\).

The expansion factor of a graph \(G\) on \(n\) vertices is

where \(\bar S=V(G)\setminus S\).

An explicit construction is a deterministic description from which one can construct a graph on \(n\) vertices in a number of steps polynomial in \(n\), for infinitely many \(n\). Equivalently, an explicit construction is a polynomial-time algorithm for defining a graph.

Let \(G\) be a graph with vertex set \(V\) and edge set \(E\), and let \(X\) and \(Y\) be two equinumerous (multi)subsets of \(V\) with \(|X|=|Y|=m\) (not necessarily disjoint). A flow \(F\) from \(X\) to \(Y\) consists of \(m\) paths in \(G\) joining the vertices of \(X\) to the vertices of \(Y\) in a one-to-one fashion. The multiset \(X\) is the input of \(F\) and \(Y\) its output. The paths are typically required to be edge-disjoint or vertex-disjoint, or, more generally, to have small congestion: no edge (or vertex) of \(G\) should be used by too many paths of \(F\).

Let \(w\) assign nonnegative values to the vertices and edges of \(G\). The general Cheeger constant is

For \(w_0(v)=d_v\), \(w_0(u,v)=1\) we recover the ordinary Cheeger constant \(h_G=h(G,w_0)\); for \(w_1(v)=1\), \(w_1(u,v)=1\) we recover the modified constant \(h'_G=h(G,w_1)\).

The girth of a graph is the size of a smallest cycle in the graph.

For a graph \(G\), an automorphism \(f : V(G) \to V(G)\) is a bijection of the vertex set that preserves edges: for all \(u,v \in V(G)\), \(\{ u,v\} \in E(G)\) if and only if \(\{ f(u),f(v)\} \in E(G)\). The automorphisms form a group \(\mathrm{Aut}(G)\) under composition.

Since \(\mathcal{L}\) is real symmetric positive semidefinite, its eigenvalues are real and nonnegative. We list them in increasing order

and call this multiset the spectrum of \(G\). We fix an orthonormal basis \(\phi _0,\dots ,\phi _{n-1}\) of eigenfunctions, with \(\phi _0 = T^{1/2}\mathbf{1}/\sqrt{\operatorname {vol}G}\).

Let \(G\) be a graph (or an induced subgraph \(S\) with nonempty boundary) and let \(f\colon V\to \mathbb {R}\). We say \(f\) is a harmonic eigenfunction with eigenvalue \(\lambda \) if, at every vertex \(x\), the incident edges are stretched in a balanced way:

where \(d_x\) denotes the degree of \(x\). This is precisely the eigenfunction equation \(\mathcal{L}f=\lambda f\) for the (normalized) Laplacian written in the harmonic normalization.

The harmonic mean \(d_H\) of the degrees is defined by \(\frac{1}{d_H} = \frac{1}{n}\sum _v \frac{1}{d_v}\).

A graph \(G\) is said to satisfy the Harnack inequality (with some absolute constant \(c\)) if every eigenfunction \(f\) with eigenvalue \(\lambda \) satisfies, for every vertex \(x\),

For a function \(f:S\cup \delta S\to \mathbb {R}\) (where \(\delta S\) is the boundary of the induced subgraph \(S\)) define

Thus \(F(\cdot ,t)\) is the solution of the heat equation with initial data \(f\).

Let \(S\) be an induced subgraph on \(n\) vertices of a graph \(G\), and let \(\mathcal{L}\) denote the Laplacian of \(S\) acting on functions subject to Neumann or Dirichlet boundary conditions (as in Chapter 8). Write

where \(\lambda _0\le \lambda _1\le \dots \le \lambda _{n-1}\) are the eigenvalues of \(\mathcal{L}\) and \(I_i\) is the orthogonal projection onto the eigenfunction \(\phi _i\) of \(S\). For \(t\ge 0\) the heat kernel \(H_t\) of \(S\) is the \(n\times n\) matrix

In particular \(H_0 = I\). The heat kernel is the fundamental solution of the heat equation

A homogeneous graph is a graph \(\Gamma \) together with a group \(\mathcal H \le \mathrm{Aut}(\Gamma )\) that acts transitively on \(V(\Gamma )\): for any \(u,v\in V(\Gamma )\) there is \(g\in \mathcal H\) with \(gu=v\). The group \(\mathcal H\) is called the associated group.

Let \(\Gamma \) be a homogeneous graph with edge generating set \(\mathcal{K}\) of \(k\) generators (so \(\Gamma \) is \(k\)-regular and the neighbors of \(x\) are exactly \(\{ ax:a\in \mathcal{K}\} \)). The (normalized) Laplacian \(L\) acts on \(f\colon V(\Gamma )\to \mathbb {R}\) by

An eigenfunction with eigenvalue \(\lambda \) satisfies \(Lf(x)=\lambda f(x)\).

The \(n\)-cube (hypercube) is the cartesian product of \(n\) copies of a single edge \(K_2\). In a hypercube the vertex subsets of given size with minimum vertex boundary are the “Hamming balls”, the sets of all vertices within a fixed distance of a given vertex.

The automorphism group of \(\Gamma \) partitions \(E(\Gamma )\) into equivalence classes \(E_1,\dots ,E_s\), where \(e_1\sim e_2\) iff some automorphism maps \(e_1\) to \(e_2\). The index of \(\Gamma \) is

One has \(1\le \operatorname {index}\Gamma \le k\), and \(\operatorname {index}\Gamma =1\) when \(\Gamma \) is edge-transitive.

A homogeneous graph \(\Gamma \) with edge generating set \(\mathcal{K}\) is invariant if for every \(a\in \mathcal{K}\),

that is, \(\mathcal{K}\) is invariant as a set under conjugation by its own elements.

The irregularity of a graph \(G\) is

where \(|V(G)|=n\), \(\rho _v = d_v/n\) and \(\rho = \sum _v d_v/n^2\). The smaller \(\operatorname {irr} G\) is, the more closely \(G\) approximates a regular graph; \(\operatorname {irr} G = 0\) if and only if \(G\) is regular.

A graph \(G\) has isoperimetric dimension \(\delta \) with isoperimetric constant \(c_\delta \) if for every subset \(X\subseteq V(G)\) the number of edges between \(X\) and its complement \(\bar X\), denoted \(|E(X,\bar X)|\), satisfies

where \(c_\delta \) depends only on \(\delta \). Equivalently, the Sobolev constant \(c_\delta \) is

Let \(G\) be a weighted undirected graph with edge weights \(w_{u,v}=w_{v,u}\), \(d_v=\sum _u w_{u,v}\), and \(\operatorname {vol}X=\sum _{v\in X}d_v\). We say \(G\) has isoperimetric dimension \(\delta \) with isoperimetric constant \(c_\delta \) if

The isoperimetric number \(i(G)\) of a graph \(G\) on \(n\) vertices is

For a \(k\)-regular graph, the conductance equals \(\tfrac 1k\, i(G)\).

Let \(\Gamma \) be a homogeneous graph with associated group \(\mathcal H\) and let \(v\in V(\Gamma )\) be a fixed vertex. The isotropy group at \(v\) is

Since \(\mathcal H\) acts transitively, \(V(\Gamma )\) can be identified with the coset space \(\mathcal H/\mathcal I\).

Let \(G\) be a graph with normalised Laplacian \(\mathcal L = I - T^{-1/2}AT^{-1/2}\) (\(T\) the diagonal degree matrix, \(A\) the adjacency matrix) and eigenvalues \(0 = \lambda _0 \le \lambda _1 \le \cdots \le \lambda _{n-1}\). We set

Thus \(\bar\lambda \) measures how far the nontrivial Laplacian eigenvalues stay away from \(1\); the eigenvalue quasi-random property asks that \(\bar\lambda = o(1)\).

The spectral gap of \(G\) is \(\lambda _G := \lambda _1\), the smallest nonzero-index eigenvalue of \(\mathcal{L}\).

Let \(G\) be a weighted graph on \(n\) vertices with normalized Laplacian eigenvalues \(0=\lambda _0\le \lambda _1\le \cdots \le \lambda _{n-1}\). For the ordinary random walk we set

For the lazy walk of Theorem 1.16 (the “modified walk” defined in (1.16)) one may instead take

This \(\lambda \) is the effective spectral gap controlling convergence.

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

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.

The (normalized) Laplacian of \(G\) is

with the convention \(T^{-1}(v,v) = 0\) when \(d_v = 0\).

Suppose the vertices of a homogeneous graph \(\Gamma \) (with symmetric edge generating set \(\mathcal{K}\)) can be embedded into a manifold \(\mathcal{M}\) with a measure \(\mu \) such that

If moreover \(\mu (x,gx)=\mu (x,g'x)\) for all \(g,g'\in \mathcal{K}\) and \(x\in V(\Gamma )\), then \(\Gamma \) is called a lattice graph.

Let \(G=(V,E)\) be a weighted graph with edge weights \(w_{x,y}\), degrees \(d_x=\sum _y w_{x,y}\) and \(\operatorname {vol}G=\sum _x d_x\). For a nontrivial \(f:V\to \mathbb R\) the relative entropy \(\sum _{x}f^2(x)d_x\log \frac{f^2(x)\operatorname {vol}G}{\sum _z f^2(z)d_z}\) is nonnegative (writing \(\mu (x)=f^2(x)d_x/\sum _z f^2(z)d_z\) it equals \(\big(\sum _z f^2 d_z\big)\, \mathrm{KL}(\mu \Vert \pi )\ge 0\)). The logarithmic Sobolev constant \(\alpha _G=\alpha \) is the largest constant such that the log-Sobolev inequality

holds for every nontrivial \(f:V\to \mathbb R\); equivalently

Let \(S\subseteq V(G)\), let \(S^{*}\) be the set of edges with at least one endpoint in \(S\), and let \(\delta S\) be the vertex boundary of \(S\). The Dirichlet log-Sobolev constant is

where \(f\) ranges over all nontrivial \(f:S\cup \delta S\to \mathbb R\) satisfying \(f(y)=0\) for \(y\in \delta S\), and \(\operatorname {vol}S=\sum _{x\in S}d_x\).

For a smooth, compact, connected Riemannian manifold \(M\) with Laplace–Beltrami operator \(\Delta \) and gradient \(\nabla \) (with no boundary, or with convex boundary and Dirichlet or Neumann conditions), the log-Sobolev constant \(\alpha \) is the least value such that

holds for all \(f:M\to \mathbb R\) with \(\int |f|^2=\operatorname {vol}M\).

With \(S,S^{*},\delta S\) as above, the Neumann log-Sobolev constant is

where \(f\) ranges over all non-constant \(f:S\cup \delta S\to \mathbb R\). If one restricts to \(f\) normalized by \(\sum _{x\in S}f^2(x)d_x=\operatorname {vol}S\) the denominator simplifies to \(\sum _{x\in S}f^2(x)d_x\log f^2(x)\).

The Lovász theta function \(\vartheta (G)\) admits several equivalent formulations. In eigenvalue form,

where \(\rho _{max}(W')\), \(\rho _{min}(W')\) are the largest and smallest eigenvalues of \(W'\), and \(W'\) ranges over all symmetric matrices indexed by \(V(G)\) with \(W'(u,v)\ne 0\) only for non-adjacent \(u\ne v\). Equivalently, via an orthonormal labeling (an assignment of a unit vector \(x_v\) to each vertex \(v\) with \(\langle x_u,x_v\rangle =0\) whenever \(u\ne v\) and \(u\not\sim v\)),

the minimum over all orthonormal labelings \(x\) and unit vectors \(y\).

If \(M\) has a boundary \(\partial M\), impose

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}\).

Let \(n(k,D)\) denote the maximum number of vertices in a graph of maximum degree at most \(k\) and diameter at most \(D\).

For a graph \(G\) and \(S\subseteq V(G)\), the neighborhood \(N(S)\) is

Note that \(S\) is not necessarily contained in \(N(S)\).

A function \(f:S\cup \delta S\to \mathbb {R}\) satisfies the Neumann boundary condition if for every \(x\in \delta S\)

equivalently \(f(x)=\dfrac {1}{d’_x}\sum _{\substack {y\in S\\ y\sim x}}f(y)\), i.e. the value at each boundary vertex is the average of its values over its neighbors in \(S\).

The Neumann eigenvalue of an induced subgraph \(S\) is

where \(f\) ranges over functions \(S\cup \delta S\to \mathbb {R}\). More generally the \(i\)-th Neumann eigenvalue is

where \(C_k\) is the subspace spanned by functions \(\phi _j\) achieving \(\lambda _{S,j}\) for \(0\le j\le k\). One has \(\lambda _{S,0}=0\) and \(\lambda _{S,1}=\lambda _S\).

For \(X\subseteq V\) let \(L_X\) denote the principal submatrix of the normalized Laplacian \(\mathcal L\) on rows and columns indexed by \(X\). Let \(N\) be the matrix with rows indexed by \(S\cup \delta S\) and columns indexed by \(S\) defined by

Thus \(N\) extends a function \(f\) on \(S\) to \(S\cup \delta S\) by the Neumann averaging rule. Define the \(|S|\times |S|\) matrix \(\mathcal N_S=T^{-1/2}N^{*}L_{S\cup \delta S}NT^{-1/2}\), where \(N^{*}\) is the transpose of \(N\).

For an induced subgraph \(S\) of \(G\), the Neumann random walk on \(S\) has transition matrix \(P\) (rows and columns indexed by \(S\)) acting by

From a vertex it moves to each neighbor in \(S\) with probability \(1/(\text{degree})\); if it selects a neighbor \(z\notin S\), it “reflects” from \(z\) to each neighbor of \(z\) in \(S\) with the additional probability \(1/(d_u d'_z)\), where \(d'_z\) is the number of neighbors of \(z\) in \(S\). The stationary distribution is \(\pi (v)=d_v/\sum _{u\in S}d_u=d_v/\mathrm{vol}\, S\). Its eigenvalues are denoted \(\rho _0=1\ge \rho _1\ge \cdots \), and \(\rho :=\rho _1\).

A non-blocking network is a directed graph with two specified disjoint vertex subsets (inputs and outputs) such that whenever a set of vertex-disjoint paths already joins some inputs to some outputs, any further input can be connected to a desired free output by a new path vertex-disjoint from the existing ones. The quantity of interest is the number of edges in such a network.

A graph \(G\) is perfect if its chromatic number equals its clique number, and the same holds for every induced subgraph of \(G\).

Let \(G\) be a weighted graph with stationary distribution \(\pi (x)=d_x/\operatorname {vol}G\), and let \(\Pi \) denote the diagonal matrix with \((x,x)\)-entry \(\pi (x)\). For \(f:V(G)\to \mathbb R\) and \(p\ge 1\) the \((\pi ;p)\)-norm is

In particular \({}_\pi \| f\| _2=\big(\sum _x f^2(x)\pi (x)\big)^{1/2}=\| \Pi ^{1/2}f\| _2\).

For a vertex \(v\) and an integer \(r\ge 0\) let \(N_r(v)=\{ u\in V(G):d(u,v)\le r\} \), where \(d(u,v)\) is the graph distance. The graph \(G\) has polynomial growth rate of type \((c,\delta )\) if

A graph with isoperimetric dimension \(\delta \) and constant \(c_\delta \) has polynomial growth rate of some type \((c',\delta )\), but the converse fails.

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 )\),

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 )\).

A family of graphs \(G\) has the eigenvalue property (EIG) if

where \(\lambda _0=0\le \lambda _1\le \dots \le \lambda _{n-1}\) are the eigenvalues of the (normalized) Laplacian of \(G\).

For a graph \(G\) on \(n\) vertices with edge density \(1/2\), consider the following properties (the \(o(\cdot )\) estimates are meant as \(n\to \infty \)).

• \(\displaystyle \max _{i\neq 0}|1-\lambda _i| = o(1)\) and \(G\) is almost regular, i.e. all but \(o(n)\) vertices have degree \(n/2 + o(n)\).

• For each subset \(S\subseteq V(G)\), the number \(e(S)\) of edges of \(G\) with both endpoints in \(S\) satisfies \(e(S) = \tfrac 14|S|^2 + o(n^2)\).

• For each subset \(S\subseteq V(G)\) with \(|S| = \lfloor n/2\rfloor \), \(\; e(S) = \bigl(\tfrac 1{16} + o(1)\bigr)n^2\).

• For \(u\in V(G)\) let \(N(u) = \{ v : u\sim v\} \). Then \(\displaystyle \sum _{u,v}\Bigl||N(u)\cap N(v)| - \tfrac n4\Bigr| = o(n^2)\).

• For \(s\ge 4\) and all graphs \(M(s)\) on \(s\) vertices, the number \(N^{*}_G(M(s))\) of labelled induced subgraphs of \(G\) isomorphic to \(M(s)\) satisfies \(N^{*}_G(M(s)) = (1+o(1))\, n^{s}\, 2^{-\binom s2}\).

• For the \(2t\)-cycle \(C_{2t}\), \(t\ge 2\), the number \(N_G(C_{2t})\) of occurrences of \(C_{2t}\) as a labelled subgraph of \(G\) is \(N_G(C_{2t}) = (1+o(1))\bigl(\tfrac n2\bigr)^{2t}\), and \(e(G) \ge (1+o(1))\tfrac {n^2}{4}\).

A \(k\)-regular graph is a Ramanujan graph if its spectral gap satisfies

This is the best possible bound for fixed \(k\) as the number of vertices tends to infinity (see the Alon–Boppana bound below).

The standard random-graph model on \(n\) labelled vertices assigns equal probability to each of the \(2^{\binom {n}{2}}\) possible graphs on those vertices (equivalently, each of the \(\binom {n}{2}\) potential edges is present independently with probability \(\tfrac 12\)). A random graph \(G\) on \(n\) vertices is said to satisfy property \(P\) if all but a \(o(1)\) fraction of the graphs satisfy \(P\), where the \(o(1)\) term tends to \(0\) as \(n\to \infty \).

A walk is a sequence of vertices \(v_0, v_1, \dots , v_s\) with \(\{ v_{i-1},v_i\} \in E(G)\). A random walk is governed by transition probabilities \(P(u,v) = \mathrm{Prob}(x_{i+1}=v \mid x_i = u)\), independent of \(i\), with \(\sum _v P(u,v) = 1\) for each \(u\). Given an initial distribution \(f\) (a row vector with \(\sum _v f(v) = 1\)), the distribution after \(k\) steps is \(fP^k\). The walk is ergodic if there is a unique stationary distribution \(\pi \) with \(\lim _{s\to \infty } fP^s = \pi \) for every \(f\). The walk is irreducible if for all \(u,v\) some \(P^s(u,v) {\gt} 0\), and aperiodic if \(\gcd \{ s : P^s(u,v) {\gt} 0\} = 1\); these two are necessary and sufficient for ergodicity.

A random walk of length \(l\) starting at a vertex \(v\) is a randomly chosen sequence \(v=v_0,v_1,\dots ,v_l\), where each \(v_{i+1}\) is chosen uniformly at random and independently among the neighbors of \(v_i\), for \(i=0,\dots ,l-1\); the walk visits \(v_i\) at time \(i\). Equivalently, the transition matrix is \(P(u,v)=1/d_u\) if \(u\sim v\) and \(0\) otherwise, so \(P=T^{-1}A\) with \(T=\operatorname {diag}(d_v)\).

The Rayleigh quotient of \(\mathcal{L}\) at a function \(g \ne 0\) is \(\langle g, \mathcal{L}g\rangle /\langle g,g\rangle \). Writing \(g = T^{1/2}f\), it equals \(\frac{\sum _{u\sim v}(f(u)-f(v))^2}{\sum _v f(v)^2 d_v}\); the numerator \(\sum _{u\sim v}(f(u)-f(v))^2\) is called the Dirichlet sum of \(G\). A nonzero function \(f\) attaining the infimum in the variational characterization of an eigenvalue (via \(g=T^{1/2}f\)) is called a harmonic eigenfunction of \(\mathcal{L}\).

A random walk is reversible if \(\pi (u)P(u,v) = \pi (v)P(v,u)\). A reversible walk is described by a weighted connected graph with edge weights \(w(u,v) = w(v,u) = \pi (v)P(v,u)/c\) (for any convenient constant \(c\)), for which the transition probabilities are \(P(u,v) = \frac{w(u,v)}{d_u}\), where \(d_u = \sum _z w(u,z)\). The unweighted case \(w \in \{ 0,1\} \) gives \(P(u,v) = 1/d_u\) if \(u\sim v\) and \(0\) otherwise.

Let \(S\) be an induced subgraph with non-empty boundary in \(G\). A rooted spanning forest of \(S\) is a subgraph \(F\) of \(G\) satisfying

• \(F\) is an acyclic subgraph of \(G\);

• \(F\) has vertex set \(S\cup \delta S\);

• each connected component of \(F\) contains exactly one vertex of \(\delta S\).

Let \(G=(V,E)\) be connected on \(n\) vertices. For a permutation \(\pi \), a route set \(P\) is a set of paths \(P_i\) joining each \(v_i\) to \(\pi (v_i)\). For an edge \(e\), let \(rc(e,G,\pi ,P)\) be the number of paths of \(P\) containing \(e\). The route covering number is

A route set is a flow together with a specified input–output assignment \(A=\{ (x_i,y_i):x_i\in X,\ y_i\in Y\} \): it consists of paths \(P_i\) joining \(x_i\) to \(y_i\) for each \(i\). Thus an assignment specifies “who is talking to whom.”

A routing \(R\) is a dynamic version of a route set, defined as a pebble game. Initially a pebble \(p_i\) is placed at each input vertex \(x_i\), with destination \(y_i\), for each assignment \((x_i,y_i)\in A\). At each time unit a pebble may be moved to an adjacent vertex. The routing \(R\) is a route set together with a strategy for moving the pebbles to their destinations; additional requirements (e.g. at each time unit the edges used are vertex- or edge-disjoint, or all edges have small congestion) may be imposed.

Let \(G=(V,E)\) be connected, \(|V|=n\). Initially each vertex \(v\) carries a distinct pebble \(p_v\) with destination \(\pi (v)\in V\), where \(\pi \) is a permutation. At each step a disjoint set of edges is chosen and the pebbles at the two endpoints of each chosen edge are interchanged. Let \(p_v(t)\) be the location at time \(t\) of the pebble that started at \(v\); \(\{ p_v(t):v\in V\} \) is always a permutation of \(V\). Let \(rt(G,\pi )\) be the minimum number of steps needed to realize \(\pi \), and define the routing number

Equivalently, \(rt(G)\) is the largest number \(r\) of factors needed to write some permutation of \(S_n\) as a product \((u_1v_1)(u_2v_2)\cdots (u_rv_r)\) where each factor is a product of disjoint transpositions along edges of \(G\).

The relative pointwise distance (r.p.d.) after \(s\) steps is

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

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\, \} \).

The \(\sigma \) function of a graph \(G\) is

where \(W\) ranges over all weight matrices of \(G\).

For \(p,q{\gt}0\) define the Sobolev constant

where \(f\) ranges over functions satisfying \(\sum _x|f(x)-c|^q d_x\ge \sum _x|f(x)|^q d_x\) for all \(c\) (equivalently \(\int |f-c|^q\ge \int |f|^q\)). The eigenvalue \(\lambda _1\) corresponds to \(p=q=2\), and the Cheeger constant to \(p=q=1\); general cases appear in Chapter 11 on Sobolev inequalities.

For a function \(f:V(G)\to \mathbb {R}\) write \(\| \nabla f\| _p=\big(\sum _{u\sim v}|f(u)-f(v)|^{p}\big)^{1/p}\) and \(\| f\| _q=\big(\sum _{v}|f(v)|^{q}d_v\big)^{1/q}\). For \(p,q{\gt}0\) the Sobolev constant of \(G\) is

The Cheeger constant of \(G\) equals \(h_G=s_{1,1}\), and the isoperimetric constant \(c_\delta \) is the case \(\delta =\infty \) of the Cheeger constant. The two Sobolev inequalities proved below (Corollary 389 and Theorem 391) concern \(s_{1,q}\) and \(s_{2,q}\) for \(q\) depending on \(\delta \).

An induced subgraph \(S\) of a homogeneous graph \(\Gamma \), with vertex boundary \(\delta S\), is strongly convex if \(\mathcal{K}\) satisfies condition (A):

(A) For all \(a,b\in \mathcal{K}\) and \(x\in \delta S\), if \(ax\in S\) and \(bx\in S\), then \(b^{-1}a\in \mathcal{K}\).

A superconcentrator is a graph with \(n\) inputs and \(n\) outputs such that for any set of inputs and any equinumerous set of outputs there exists a set of vertex-disjoint paths joining the inputs to the outputs in a one-to-one fashion (the correspondence being immaterial). The measure of interest is how few edges a superconcentrator can have.

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

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

The total variation distance after \(s\) steps is

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

1. an underlying space \(M\) equipped with a finite measure \(\mu \);

2. a Laplace operator \(\mathcal{L}\) on functions on \(M\) that is self-adjoint on \(L^2(M,\mu )\) and has discrete spectrum;

3. if \(M\) has a boundary, a boundary condition chosen so as not to disrupt the self-adjointness of \(\mathcal{L}\);

4. 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.

The variance of a graph \(G\) is

For \(S\subseteq V(G)\) the vertex boundary \(\delta S\) is the set of all vertices not in \(S\) but adjacent to some vertex of \(S\):

For \(\emptyset \ne S\subsetneq V(G)\) define

With the counting measure (weight \(1\) per vertex) one defines, for a not necessarily regular \(G\),

For regular graphs \(g_G(S)=\bar g_G(S)\). Both \(g_G\) and \(\bar g_G\) measure the vertex expansion of \(G\).

A graph \(G\) is vertex-transitive if for any two vertices \(u,v\) there is an automorphism of \(G\) mapping \(u\) to \(v\).

Let \(\Gamma \) be a graph and \(X\) a vector space. The vibrational Laplacian \(\mathcal{L}_X\) acts on \(\mathcal F(V,X)=\{ f:V(\Gamma )\to X\} \) and is defined through the quadratic form: to each edge \(e=\{ u,v\} \) associate a self-adjoint operator \(A_e\) on \(X\), and set

For \(X=\mathbb {R}\) and \(A_e=1\) this is the usual Dirichlet sum, so \(\mathcal{L}_X\) generalizes the Laplacian; the case \(X=\mathbb {R}^3\) gives the vibrational spectrum of a molecule whose atoms are the vertices and whose bonds are the edges.

The volume of \(G\) is \(\operatorname {vol}G = \sum _v d_v\). More generally, for a set \(S\) of vertices, \(\operatorname {vol}S = \sum _{v\in S} d_v\).

Let \(G\) be a graph. For \(S\subseteq V(G)\), the volume of \(S\) is

the sum of the degrees of the vertices in \(S\). We write \(\mathrm{vol}\, G=\mathrm{vol}\, V(G)\). This measure takes the degree at each vertex into account, in contrast to the counting measure which assigns weight \(1\) to each vertex.

Let \(G\) be a simple graph and \(W=(w_{uv})\) a weight matrix with \(w_{uv}=w_{vu}\ge 0\) and \(w_{uv}=0\) whenever \(u,v\) are non-adjacent or \(u=v\). The \(W\)-weighted Laplacian \(\mathcal L_W\) has rows and columns indexed by \(V(G)\) with entries

Here \(W\) ranges over all weight matrices of a fixed graph \(G\); this differs from the Laplacian of a single fixed weighted graph. Write \(\lambda _{max}(G_W)\) for the maximum eigenvalue of \(\mathcal L_W\), and \(\lambda _{max}(G)\) for \(\lambda _{max}(G_W)\) when \(w_{uv}=1\) for \(u\sim v\) and \(0\) otherwise.

Let \(G,G'\) have consistent weight functions \(w,w'\). The weighted cartesian product \(G\otimes G'\) has vertex set \(V(G)\times V(G')\) and consistent weight \(w\otimes w'\): for an edge \(\{ u,v\} \in E(G)\), \((w\otimes w')((u,v'),(v,v'))=w(u,v)w'(v')\); for an edge \(\{ u',v'\} \in E(G')\), \((w\otimes w')((u,u'),(u,v'))=w(u)w'(u',v')\); and a vertex \(x=(u,v)\) has weight \((w\otimes w')(x)=2\, w(u)w'(v)\). For \(k\) factors \(G_1\otimes \cdots \otimes G_k\) (with consistent \(w_i\)), an edge \(\{ u,v\} \in E(G_i)\) contributes the edge joining \((v_1,\dots ,v_{i-1},u,v_{i+1},\dots ,v_k)\) and \((v_1,\dots ,v_{i-1},v,v_{i+1},\dots ,v_k)\) with weight \(w_1(v_1)\cdots w_{i-1}(v_{i-1})\, w_i(u,v)\, w_{i+1}(v_{i+1})\cdots w_k(v_k)\). The natural consistent weight of a graph \(G\) has edge weight \(1\) and vertex weight \(d_x\).

A weighted (undirected) graph \(G\), possibly with loops, carries a weight function \(w : V \times V \to \mathbb {R}\) with

and \(w(u,v) = 0\) whenever \(\{ u,v\} \notin E(G)\). Unweighted graphs are the special case where all weights are \(0\) or \(1\). The degree of \(v\) is \(d_v = \sum _u w(u,v)\), and \(\operatorname {vol}G = \sum _v d_v\).

For a graph \(G\) with edge density \(\rho \), the weighted indicator function \(\chi \colon V\times V\to \mathbb {R}\) is

Equivalently \(\chi (x,y)=a_{xy}-\rho \), where \(a_{xy}\) is the adjacency indicator of the pair \(\{ x,y\} \). Note \(\chi \) is symmetric. For a \(4\)-cycle \(C\) we set

For a weighted graph, the combinatorial Laplacian is

and, with \(T = \mathrm{diag}(d_v)\), the normalized Laplacian is \(\mathcal{L}= T^{-1/2} L T^{-1/2}\), i.e.

Let \(G\) be a bipartite graph with vertex set \(X\cup Y\) and edges between \(X\) and \(Y\) (not necessarily regular). Define the modified matrix \(\mathcal M(u,v)=1/\sqrt{d_v}\) for \(\{ u,v\} \in E\) (and \(0\) otherwise). For a subset \(S\) of \(X\) (with \(|X|=n\)), the neighborhood \(N(S)\) satisfies

where \(\rho ^2\) is the second largest eigenvalue of \(\mathcal M^*\mathcal M\). The inequality is strict when the eigenvalues of \(\mathcal M^*\mathcal M\) other than the largest are not all equal.

Let \(G\) be a bipartite graph with vertex set \(X\cup Y\) and edges between \(X\) and \(Y\), and suppose all vertices in \(X\) have the same degree. For a subset \(S\) of \(X\) (with \(|X|=n\)), the neighborhood \(N(S)\) satisfies

where \(\rho ^2 k^2\) is the second largest eigenvalue of \(M^*M\), \(M=M(G)\) being the bipartite adjacency (incidence) matrix with \(M(x,y)=1\) iff \(\{ x,y\} \in E\). The inequality is strict when the eigenvalues of \(M^*M\) other than the largest are not all equal.

The following are equivalent:

1. \(G\) is bipartite;

2. \(G\) has \(i+1\) connected components and \(\lambda _{n-j} = 2\) for \(1 \le j \le i\);

3. for each eigenvalue \(\lambda _i\), the value \(2 - \lambda _i\) is also an eigenvalue of \(G\).

For graphs \(G,H\),

where the random walk on \(G_1\, \square \, \cdots \, \square \, G_k\) has transition probability \(P'\bigl((\dots ,v_i,\dots ),(\dots ,u_i,\dots )\bigr)=w_{v_i,u_i}/\sum _{1\le j\le k}w_{v_j}\).

Let \(B\) be an \(m\times N\) real matrix (\(m\le N\)). Then \(\det (BB^{*})=\sum _{X}\det B_X\, \det B_X^{*}\), where \(X\) ranges over all sets of \(m\) columns of \(B\) and \(B_X\) is the \(m\times m\) submatrix on those columns.

For real vectors, \(\bigl(\sum _i a_i b_i\bigr)^2 \le \bigl(\sum _i a_i^2\bigr)\bigl(\sum _i b_i^2\bigr)\); in particular \(\bigl(\sum _{i=1}^m c_i\bigr)^2 \le m\sum _{i=1}^m c_i^2\).

For real numbers \(a_1,\dots ,a_m\) and \(b_1,\dots ,b_m\), \(\bigl(\sum _i a_ib_i\bigr)^2\le \bigl(\sum _i a_i^2\bigr)\bigl(\sum _i b_i^2\bigr)\). In particular \(\bigl(\sum _{i=1}^m a_i\bigr)^2\le m\sum _{i=1}^m a_i^2\).

Let \(f:V(\Gamma )\to \mathbb {R}\), and for an edge \(e=\{ u,v\} \) write \(f(e)=|f(u)-f(v)|\). If \(P\) is a path of length \(\ell \) from \(x\) to \(y\) then

For real numbers \(a_1,\dots ,a_\ell \), \(\bigl(\sum _{i=1}^{\ell } a_i\bigr)^2 \le \ell \sum _{i=1}^{\ell } a_i^2\).

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\).

Let \(g:V(G)\to \mathbb {R}_{\ge 0}\) be nonnegative with the support \(\{ g{\gt}0\} \) of volume at most \(\tfrac 12\mathrm{vol}\, G\). Order the vertices \(v_1,\dots ,v_n\) so that \(g(v_1)\le \cdots \le g(v_n)\) (so \(g(v_1)=0\)). For \(1\le i\le n-1\) set \(C_i=\{ \{ v_j,v_k\} \in E(G): j\le i{\lt}k\} \) and

Then \(\alpha \ge h_G\) and

For a connected graph \(G\),

Let \(I_0\) denote the projection onto \(\phi _0\). Then

with equality if \(G\) is vertex-transitive.

\(\Delta '(s) \ge 2\Delta _{TV}(s)\) and \(\Delta '(s) \le \Delta (s)\).

A graph \(G\) (with no isolated vertices) is connected if and only if \(h_G{\gt}0\). We henceforth consider only connected graphs.

If \(G\) is connected then \(\lambda _1 {\gt} 0\). In general, if \(\lambda _i = 0\) and \(\lambda _{i+1} \ne 0\) then \(G\) has exactly \(i+1\) connected components.

For the contingency-table lattice graph (Construction 371), the matrix \((a_{ij})\) of the first-order approximation (10.10), when restricted to the manifold \(M\), has all eigenvalues equal to \(8\). Hence one may take \(C_1=C_2=8\) in Theorem 373, and the constant there is

If \(H\) is formed from \(G\) by contractions, then \(\lambda _G \le \lambda _H\).

If two induced subgraphs \(F_1,F_2\) are both convex, then \(F_1\cap F_2\) is convex.

Suppose \(M\) is convex and contains an open ball \(B(cRN)\) of radius \(cRN\) with \(cN\ge 2\), where \(v_1,\dots ,v_N\) generate \(\Gamma \) and \(R=\tfrac 12(\sum _{\nu =1}^N\| v_\nu \| ^2)^{1/2}\). Then, with \(U\) the volume of a Voronoi region and \(S = M\cap V(\Gamma )\),

Let \(\bar\lambda = \max _{i\ne 0}|1-\lambda _i|\). Then

Let \(S\) be a convex subgraph of a graph \(G\) and let \(f\) be an eigenfunction with Dirichlet eigenvalue \(\lambda \) defined on \(S\cup \delta S\). Then \(f\) can be extended to all vertices of \(G\) that are adjacent to some vertex \(x\in S\cup \delta S\) so that it satisfies the harmonic relation

at every such \(x\).

Let \(g\) be an eigenfunction of \(\mathcal L\) with Dirichlet eigenvalue \(\lambda \), i.e. \(g:S\to \mathbb R\) satisfies (8.7) and \(g(x)=0\) for \(x\in \delta S\). Then:

• for \(x\in S\),  \(\displaystyle \mathcal Lg(x)=\frac{1}{\sqrt{d_x}} \sum _{\substack {y\\ \{ x,y\} \in S^{*}}}\Bigl(\frac{g(x)}{\sqrt{d_x}}-\frac{g(y)}{\sqrt{d_y}}\Bigr)=\lambda g(x)\);

• for any function \(h:V\to \mathbb R\),  \(\displaystyle \sum _{x\in S}h(x)\mathcal Lg(x) =\sum _{\{ x,y\} \in S^{*}}\Bigl(\frac{h(x)}{\sqrt{d_x}}-\frac{h(y)}{\sqrt{d_y}}\Bigr) \Bigl(\frac{g(x)}{\sqrt{d_x}}-\frac{g(y)}{\sqrt{d_y}}\Bigr)\).

Let \(F(x,t)=(H_t f)(x)\) and let \(S^{*}\) be the set of edges with at least one endvertex in \(S\). For all \(t\ge 0\),

Let \(\Gamma \) be distance transitive of diameter \(D\). For \(0\le j\le D\) let \(A_j\) be the \(0/1\) matrix with \(A_j(x,y)=1\) iff \(d(x,y)=j\). Then each \(A_j\) is a polynomial of degree \(j\) in \(A=A_1\), and \(I=A_0,A,A^2,\dots ,A^{D}\) are linearly independent.

Let \(\lambda \) be an eigenvalue of a distance transitive graph \(\Gamma \), and fix a vertex \(v\). Let \(V_i=\{ u\in V(\Gamma ):d(u,v)=i\} \). Then \(\lambda \) is achieved by an eigenfunction \(f\) that is constant on each \(V_i\): \(x,y\in V_i\) implies \(f(x)=f(y)\).

For any \(X\subseteq V(G)\),

An edge-transitive graph \(G\) with no isolated vertices is vertex-transitive or bipartite (or both).

Let \(A\) be the adjacency matrix of \(G\). For all \(X,Y\subseteq V\),

and in particular \(e(S,S) = \langle \psi _S, A\psi _S\rangle \).

For a graph \(G\) on \(n\) vertices with average degree \(k = \frac{\operatorname {vol}G}{n}\), the quantity \(\bar\lambda = \max _{i\ne 0}|1-\lambda _i|\) satisfies

A \(k\)-regular abelian homogeneous graph, or a strongly convex subgraph of one, satisfies the eigenvalue bound

where \(D\) is the diameter, and this lower bound is sharp up to the constant factor of \(k\) (the factor \(k\) is necessary for some homogeneous graphs).

The eigenvalues of \(L\) and of \(\mathcal L\) satisfy \(0\le \lambda '_i\le \lambda _i\max _v d_v\) for all \(i\).

For \(K_{m,n}\) the eigenvalues of \(\mathcal{L}\) are \(0\), \(1\) (with multiplicity \(m+n-2\)), and \(2\).

For the complete graph \(K_n\) the eigenvalues of \(\mathcal{L}\) are \(0\) and \(\frac{n}{n-1}\) (with multiplicity \(n-1\)).

For the cycle \(C_n\) the eigenvalues of \(\mathcal{L}\) are \(1 - \cos \frac{2\pi k}{n}\) for \(k = 0, 1, \dots , n-1\).

For the \(n\)-cube \(Q_n\) on \(2^n\) vertices the eigenvalues of \(\mathcal{L}\) are \(\frac{2k}{n}\) with multiplicity \(\binom {n}{k}\), for \(k = 0, 1, \dots , n\).

For all \(i\), \(\lambda _i \le 2\). Moreover \(\lambda _{n-1} = 2\) if and only if a connected component of \(G\) is bipartite and nontrivial.

For the path \(P_n\) on \(n\) vertices the eigenvalues of \(\mathcal{L}\) are \(1 - \cos \frac{\pi k}{n-1}\) for \(k = 0, 1, \dots , n-1\).

For the star \(S_n = K_{1,n-1}\) on \(n\) vertices the eigenvalues of \(\mathcal{L}\) are \(0\), \(1\) (with multiplicity \(n-2\)), and \(2\).

For all \(a,b\ge 0\) and \(p\ge 1\),

For a regular graph \(G\),

where \(g_G:=\inf _S \dfrac {\mathrm{vol}\, \delta S}{\min (\mathrm{vol}\, S,\mathrm{vol}\, \bar S)}\) is the Cheeger constant of \(G\).

For \(a{\gt}0\), \(\int _{-\infty }^{\infty }e^{-a x^2}\, dx=\sqrt{\pi /a}\).

Any graph of maximum degree at most \(\Delta \) is \((\Delta +1)\)-colorable.

Let \(f\) be a harmonic eigenfunction achieving \(\lambda _G\) in Lemma 15. Then for every vertex \(x\),

Among all functions \(f\) with \(f|_{\delta S}=\sigma \), the energy \(H(f)\) is minimized by a function \(f_0\) which is discrete-harmonic on \(S\):

If \(S\) is connected, \(f_0\) exists and is uniquely determined by \(\sigma \).

Inequality (9.1) does not hold for all graphs. The graph obtained by joining two complete graphs of the same size by a single edge is a counterexample.

Let \(F(x,t) = (H_t f)(x)\) and let \(d_x\) denote the degree of \(x\). Let \(S^{*}\) denote the set of all edges having at least one endvertex in \(S\). Then:

• \(F(x,0)=f(x)\).

• For every \(x\in S\cup \delta S\), \(\displaystyle \sum _{y\in S\cup \delta S} H_t(x,y)\sqrt{d_y} = \sqrt{d_x}\); by symmetry of \(H_t\) also \(\sum _{x} H_t(x,y)\sqrt{d_x} = \sqrt{d_y}\).

• \(F\) satisfies the heat equation \(\dfrac {\partial F}{\partial t} = -\mathcal{L}F\).

• Under the Neumann boundary condition, for any vertex \(x\in \delta S\),

  \[ (\mathcal{L}F)(x,t) = \frac{1}{\sqrt{d_x}}\sum _{y\sim x}\Bigl(\frac{F(x,t)}{\sqrt{d_x}} - \frac{F(y,t)}{\sqrt{d_y}}\Bigr) = 0 . \]

  Under the Dirichlet boundary condition, for any vertex \(x\in \delta S\), \(F(x,t)=0\).

• \(\displaystyle \sum _{\{ x,y\} \in S^{*}}\Bigl(\frac{F(x,t)}{\sqrt{d_x}} - \frac{F(y,t)}{\sqrt{d_y}}\Bigr)^2 = \sum _{x\in S} F(x,t)\, (\mathcal{L}F)(x,t)\).

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

Assume \(\delta {\gt}2\) and set \(\gamma =\frac{2\delta }{\delta -2}\). Let \(H_t\) be the heat kernel of \(G\), fix a vertex \(x\), and let \(m\) be the value associated (as in Theorem 388) to the function \(y\mapsto H_{1/2}(x,y)/\sqrt{d_y}\). Then

For all \(x,y\in S\cup \delta S\) and all \(t\ge 0\),

For \(0 \le s \le t\) and all vertices \(x,z\),

The heat kernel \(H_t\) of a graph (or induced subgraph) \(S\) with eigenfunctions \(\phi _i\) and eigenvalues \(\lambda _i\) satisfies, for every pair of vertices \(x,y\),

For nonnegative reals \(f_i,g_i\) and exponents \(p,q{\gt}0\) with \(\frac1p+\frac1q=1\),

The case \(p=q=2\) is the Cauchy–Schwarz inequality.

Let \(\Gamma \) be an invariant homogeneous graph, let \(Lf=\lambda f\), and set \(\rho (x)=\frac1k\sum _{a\in \mathcal{K}}\bigl(f(x)-f(ax)\bigr)^2\). Then for every vertex \(x\),

If \(Lf=\lambda f\), then for every vertex \(x\),

In the \(n\)-cube \(Q_n\), among all vertex sets of a given cardinality the initial segments of the Hamming (binary) order minimize the edge boundary. Consequently the edge boundary of \(X\subseteq V(Q_n)\) with \(\operatorname {vol}X=m\) is minimized (up to lower-order terms) when \(X\) is close to a Hamming ball, which yields the isoperimetric estimates for \(Q_n\) used below.

For the \(n\)-cube \(Q_n\), the lazy random walk converges to the uniform distribution: under total variation distance \(\Delta _{TV}(s) \le e^{-c}\) whenever \(s \ge \tfrac 14 n\log n + cn\), and under relative pointwise distance \(\Delta (s) \le e^{-c}\) whenever \(s \ge \tfrac 12 n\log n + cn\).

Let \(B\) be the \(|S|\times |E(S^{*})|\) incidence matrix with rows indexed by \(S\) and columns indexed by edges of \(S^{*}\), defined by \(B(x,e)=1/\sqrt{d_x}\) if \(e=\{ x,y\} \) with \(x{\lt}y\), \(B(x,e)=-1/\sqrt{d_x}\) if \(e=\{ x,y\} \) with \(x{\gt}y\), and \(0\) otherwise. If a set \(X\) of \(|S|\) edges is such that the subgraph on \(S\cup \delta S\) with edge set \(X\) contains a cycle, then \(\det B_X=0\).

With \(B\) as in Lemma 328, if the subgraph formed by an \(|S|\)-edge set \(X\) is a rooted spanning forest of \(S\), then

With \(B\) as in Lemma 328, if the subgraph on edge set \(X\) has a connected component containing two or more vertices of \(\delta S\), then \(\det B_X=0\).

Let \(E_1,\dots ,E_M\) be independent events with \(\Pr [E_i]=p_i\) and \(\sum _i p_i\le \gamma \). Then for every positive integer \(s\),

For any \(A\subseteq V(G)\),

For a \(k\)-regular graph \(G\), \(\ i(G)\ \ge \ \tfrac {k}{2}-2\, \mathrm{disc}(G)\), where \(\mathrm{disc}(G)\) is the discrepancy of \(G\).

Let \(\phi _i\) be the orthonormal eigenfunctions of \(\mathcal{L}\) and let \(\lambda ' = \lambda _1\) if \(1-\lambda _1 \ge \lambda _{n-1}-1\), and \(\lambda ' = 2-\lambda _{n-1}\) otherwise (so \(\lambda ' = 1 - \max _{i\ne 0}|1-\lambda _i|\)). Then for any initial distribution \(f\),

Let \(P_{k-1}\) denote the span of the eigenfunctions \(\phi _i\) for \(i \le k-1\). Then

For a connected graph \(G\) with diameter \(D\),

Let \(G\) be a graph with diameter \(D \ge 4\) and maximum degree \(k\). Then

The spectral gap admits the equivalent expressions

where \(\bar f = \frac{\sum _v f(v) d_v}{\operatorname {vol}G}\) and the last denominator ranges over unordered pairs \(\{ u,v\} \) of vertices.

If \(G\) is not the complete graph, then \(\lambda _1 \le 1\).

For \(n \ge 2\), \(\lambda _1 \le \frac{n}{n-1}\), with equality if and only if \(G\) is the complete graph \(K_n\). If moreover \(G\) has no isolated vertices, then \(\lambda _{n-1} \ge \frac{n}{n-1}\).

where \(f \perp T\mathbf{1}\) means \(\sum _v f(v) d_v = 0\), and the corresponding harmonic eigenfunction \(f\) gives \(g = T^{1/2}f\) achieving the eigenvalue.

Let \(L\) be as in 348 and let \(g\colon V(\Gamma )\to \mathbb {R}\). If a vertex \(v\) satisfies \(g(v)\ge g(av)\) for every \(a\in \mathcal{K}\) (in particular if \(g\) attains its maximum over the relevant vertex set at \(v\)), then \(Lg(v)\ge 0\).

On the vertices of nonzero degree,

Viewing \(\mathcal{L}\) as an operator on functions \(g : V(G) \to \mathbb {R}\), for every vertex \(u\) with \(d_u \ne 0\),

Let \(S\) be the matrix whose rows are indexed by vertices and columns by edges, where an edge \(e=\{ u,v\} \) has entry \(1/\sqrt{d_u}\) in the row of \(u\), entry \(-1/\sqrt{d_v}\) in the row of \(v\), and \(0\) elsewhere (the two signs may be chosen arbitrarily as long as one is positive and one negative). Then \(\mathcal{L}= S S^{*}\), where \(S^{*}\) is the transpose of \(S\). Consequently \(\mathcal{L}\) is symmetric and positive semidefinite; its eigenvalues are real and nonnegative, and for every \(g\),

If \(G\) is \(k\)-regular then \(\mathcal{L}= I - \frac{1}{k} A\).

Let \(L\subset \mathbb {R}^N\) be the lattice generated by vectors \(v_1,\dots ,v_N\). Then the covering radius of \(L\) is at most

Fix a constant \(c \ge 0\) and modify the weights by adding a loop of weight \(c\, d_v\) at each vertex, i.e. \(w'(u,v) = w(u,v) + c\, d_v\) if \(u=v\) and \(w'(u,v) = w(u,v)\) otherwise. Then the new Laplacian eigenvalues are \(\lambda _k' = \frac{\lambda _k}{1+c}\). In particular, taking \(c=1\) gives the lazy walk with \(\bar\lambda _k = \lambda _k/2 \le 1\). Choosing \(c = \frac{\lambda _1 + \lambda _{n-1}}{2} - 1 \le \tfrac 12\) yields \(\lambda _1' = \frac{2\lambda _1}{\lambda _1 + \lambda _{n-1}}\) with the symmetric relation \(1 - \lambda _1' = \lambda _{n-1}' - 1\).

Let \(M\) be a \(d\)-dimensional compact manifold with boundary \(\partial M\). Suppose the Ricci curvature of \(M\) is nonnegative, and if \(\partial M\ne \emptyset \) suppose in addition that \(\partial M\) is convex. Then the fundamental solution \(h(t,x,y)\) of the heat equation with the Neumann boundary condition satisfies

for a constant \(C(\epsilon ){\gt}0\) depending on \(\epsilon {\gt}0\) and \(d\). Here \(B_x(r)\) is the intersection of \(M\) with the ball of radius \(r\) centered at \(x\).

Let \(G=(V,E)\) and \(G'=(V',E')\) be connected graphs with log-Sobolev constants \(\alpha =\alpha _G\) and \(\alpha '=\alpha _{G'}\). Suppose \(\rho :V\to V'\) is surjective and:

• with \(d_x,d'_{x'}\) the degrees in \(V,V'\), for all \(x'\in V'\), \(\displaystyle \sum _{x\in \rho ^{-1}(x')}d_x\ge c\, d'_{x'}\);

• for each edge \(e=xy\in E\) there is a path \(P(e)\) between \(\rho (x)\) and \(\rho (y)\) in \(E'\) such that

  • \(P(e)\) has at most \(\ell \) edges;

  • for each edge \(e'\in E'\), \(\displaystyle \sum _{e:\, e'\in P(e)}w_e\le m\, w_{e'}\).

Then

If \(f\) achieves the log-Sobolev constant \(\alpha \) of \(M\) (as in 416), then

For a graph \(G\) (with no boundary, or with Dirichlet or Neumann boundary conditions) the log-Sobolev constant \(\alpha \) and the first Laplacian eigenvalue \(\lambda _1\) satisfy

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\).

Let \(M\) be a real symmetric \(n\times n\) matrix with eigenvalues \(\mu _1\le \cdots \le \mu _n\). Then for \(1\le k\le n\),

In particular the stationary values of a Rayleigh quotient are exactly the eigenvalues of \(M\), and eigenfunctions are the corresponding stationary vectors.

For any graph \(G\),

For a connected graph \(G\),

For a connected graph \(G\), \(2h'_G\ge \lambda '_1\).

Suppose \(G\) is a regular graph on \(n\) vertices and \(G\) is not a complete graph. For \(S\subseteq V(G)\), the neighborhood \(N(S)\) satisfies

where \(\bar\lambda =\max _{i\ne 0}|1-\lambda _i|\).

Suppose \(G\) is not a complete graph. For \(S\subseteq V(G)\), the neighborhood \(N(S)\) satisfies

where \(\bar\lambda =\max _{i\ne 0}|1-\lambda _i|\).

Let \(f:S\cup \delta S\to \mathbb {R}\) satisfy (8.3) with eigenvalue \(\lambda \). Then:

• for \(x\in S\),  \(\displaystyle \mathcal{L}f(x):=\sum _{\substack {y\\ \{ x,y\} \in S^{*}}}\bigl(f(x)-f(y)\bigr)=\lambda f(x)\, d_x\);

• for \(x\in \delta S\),  \(\displaystyle \sum _{\substack {y\\ \{ x,y\} \in \partial S}}\bigl(f(x)-f(y)\bigr)=0\), i.e. \(f\) satisfies the Neumann condition \(f(x)=\dfrac {1}{d’_x}\sum _{\{ x,y\} \in \partial S}f(y)\);

• for any function \(h:S\cup \delta S\to \mathbb {R}\),  \(\displaystyle \sum _{x\in S}h(x)\, \mathcal{L}f(x) =\sum _{\{ x,y\} \in S^{*}}\bigl(h(x)-h(y)\bigr)\bigl(f(x)-f(y)\bigr)\).

The eigenvalues of \(\mathcal N_S\) are exactly the Neumann eigenvalues \(\lambda _{S,i}\). Moreover \(\mathcal N_S\) has \(0\) as an eigenvalue, and if \(S\) is connected it has exactly \(|S|-1\) positive eigenvalues.

Let \(z\) have \(d'_z\ge 1\) neighbors in \(S\), and let \(f\) be extended to \(z\) by the Neumann rule \(f(z)=\frac{1}{d'_z}\sum _{y\sim z,\, y\in S}f(y)\). Then

Let \(f\colon V\to \mathbb {R}\) and let \(P\) be a walk from \(x\) to \(y\) whose edge set \(P\) has \(|P|\) edges. Writing \(f^2(e)=(f(a)-f(b))^2\) for an edge \(e=\{ a,b\} \), we have

For a graph \(G\) on \(n\) vertices, suppose there is a set of \(\binom {n}{2}\) paths joining all pairs of vertices such that each edge of \(G\) is contained in at most \(m\) of the paths. Then

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

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\).

For real numbers \(b_1,\dots ,b_t\),

For \(a,b\ge 0\) and \(0{\lt}s\le 1\) one has \(a^{s}+b^{s}\ge (a+b)^{s}\), and more generally \(\sum _i a_i^{s}\ge \big(\sum _i a_i\big)^{s}\).

The bipartite Ramanujan graph \(X^{p,q}\) has \(q(q^2-1)\) vertices and girth \(4\log _p q-\log _p 4\); in particular the bipartite Ramanujan graphs on \(n\) vertices have girth about \(\tfrac 43\log _{k-1} n\).

The random walk on a weighted graph \(G\) is ergodic if and only if \(G\) is connected and non-bipartite, equivalently if and only if \(\lambda _1 {\gt} 0\) and \(\lambda _{n-1} {\lt} 2\).

For any function \(f : V(G) \to \mathbb {R}\), writing \(g = T^{1/2} f\),

where the numerator sum ranges over unordered adjacent pairs \(\{ u,v\} \).

For a \(k\)-regular graph \(G\) on \(n\) vertices,

If \(G\) is \(k\)-regular with adjacency matrix \(A\), then its normalized Laplacian satisfies

In particular this holds for any vertex-transitive graph.

For a finite group \(\mathcal H\), the (right) regular representation on \(\mathbb {C}[\mathcal H]\) decomposes as \(\bigoplus _\rho (\dim \rho )\, \rho \), the direct sum over the irreducible representations \(\rho \) of \(\mathcal H\), each occurring with multiplicity equal to its dimension. Consequently \(\sum _\rho (\dim \rho )^2=|\mathcal H|\).

For any permutation \(\pi \) of a connected graph \(G\) and any route set \(P\) realizing \(\pi \),

so \(rc(G)\ge \max _\pi \dfrac {\sum _v d(v,\pi (v))}{|E(G)|}\).

For every connected graph \(G\) and every permutation \(\pi \), \(rt(G,\pi )\) is finite; hence \(rt(G)\) is well defined.

The \(\sigma \) function can be written as

where \(W\) ranges over all symmetric matrices indexed by \(V(G)\) with \(W(u,v){\gt}0\) only for adjacent \(u,v\). Consequently \(\sigma (G)\le \vartheta (\bar G)\). Moreover, writing an acute orthonormal labeling as an assignment of unit vectors \(x_v\) with \(\langle x_u,x_v\rangle \ge 0\) for \(u=v\) or \(u\sim v\) and \(0\) otherwise, one has \(\sigma (G)=\vartheta '(G)=\min _{x,y}\max _v 1/\langle x_v,y\rangle ^2\) over acute orthonormal labelings.

The spectrum of \(G\) is the union (with multiplicity) of the spectra of its connected components.

The random walk on a weighted connected graph satisfies \(\mathbf{1}T P = \mathbf{1}T\), so its stationary distribution is \(\pi = \mathbf{1}T / \operatorname {vol}G\), i.e. \(\pi (v) = d_v/\operatorname {vol}G\).

Condition (A) of 341 is implied by condition (B): for all pairs of vertices \(u,v\in S\), every shortest path joining \(u\) and \(v\) is contained in \(S\).

The intersection of two strongly convex subgraphs of \(\Gamma \) is strongly convex.

For a graph \(G\) on \(n\) vertices, \(\sum _i \lambda _i \le n\), with equality if and only if \(G\) has no isolated vertices.

For reals \(x_0,\dots ,x_{n+1}\) and \(y_0,\dots ,y_{n+1}\),

and the last two terms vanish if \(x_0=y_n=0\) or \(y_0=x_{n+1}=0\).

Let \(T\) be the \((0,1)\times (0,1)\) torus and let \(\psi _1,\psi _2\) be the measure-preserving automorphisms \(\psi _1(x,y)=(x,y+2x)\), \(\psi _2(x,y)=(x+2y,y)\) (addition modulo \(1\)). If \(\phi \) is measurable on \(T\) with \(\int _T\phi =0\), then

Let \(\bar\lambda = \max _{i\ne 0}|1-\lambda _i|\). Then

and also

where the last sum ranges over unordered edges \(\{ x,y\} \).

If \(M\) is a real symmetric \(n\times n\) matrix with eigenvalues \(\mu _1,\dots ,\mu _n\), then for every \(k\ge 1\),

For the random walk on a weighted graph with weight matrix \(A\) (so \(A(u,v) = w(u,v)\)),

\(\Delta _{TV}(s) \le \tfrac 12 \Delta (s)\).

For positive reals \(a_1,\dots ,a_n\) with average \(a=\frac1n\sum _i a_i\),

Consequently \(\operatorname {var} G\le \operatorname {irr} G\).

For any nonempty \(X\subseteq V(G)\),

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\).

For a graph \(G\) and \(S\subseteq V(G)\), the vertex boundary \(\delta (S)=\{ x\notin S : x\sim y \text{ for some }y\in S\} \) satisfies

where \(\lambda =\dfrac {2\lambda _1}{\lambda _{n-1}+\lambda _1}\). In other words, \(G\) is a \(\lambda (2-\lambda )\)-expander.

For every graph \(G\), \(g_G\ge h_G\).

A vertex-transitive graph is regular: all vertices have a common degree \(k\).

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

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

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

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\),

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

Let \(\Gamma \) be a vertex-transitive graph on \(n\) vertices. Then every \(\mathrm{Aut}(\Gamma )\)-orbit \(E_i\) of edges satisfies \(|E_i|\ge n/2\).

For a weighted graph \(G\),

The function \(T^{1/2}\mathbf{1}\) (where \(\mathbf{1}\) is constant \(1\) on every vertex) is an eigenfunction of \(\mathcal{L}\) with eigenvalue \(0\), and \(0\) is the smallest eigenvalue of \(\mathcal{L}\).

The space of displacements of the Buckyball has dimension \(180=60\times 3\); as a representation of \(A_5\) it is the tensor product of the regular representation with the \(3\)-dimensional representation, and it decomposes into \(48=3\times 16\) irreducible constituents.

Any force matrix \(F\) invariant under \(A_5\) has at most \(46\) distinct eigenvalues, yielding four lines visible in the infrared spectrum and ten in the Raman spectrum.

Weight single bonds by \(1\) and double bonds by \(t\). Then the eigenvalues of the weighted adjacency matrix are the eigenvalues of \(\rho (a)+\rho (a^{-1})+t\, \rho (b)\) as \(\rho \) ranges over the irreducibles of \(A_5\); in closed form they are the roots of

• \((x^2+x-t^2+t-1)(x^3-tx^2-x^2-t^2x+2tx-3x+t^3-t^2+t+2)=0\), with multiplicity \(5\);

• \((x^2-x-t^2-1)(x^2+x-(t+1)^2)=0\), with multiplicity \(4\);

• \((x^2+(2t+1)x+t^2+t-1)(x^4-3x^3+(-2t^2+t-1)x^2+ (3t^2-4t+8)x+t^4-t^3+t^2+4t-4)=0\), with multiplicity \(3\);

• \(x-t-2=0\), with multiplicity \(1\).

For example, for the \(5\)-dimensional representation \(\rho _5\) (giving (a)) one has, with \(a=(1\, 2\, 3\, 4\, 5)\), \(b=(1\, 2)(3\, 4)\),

and \(\rho _5(a)+\rho _5(a^{-1})+t\rho _5(b)\) has characteristic polynomial \((x^2+x-t^2+t-1)(x^3-tx^2-x^2-t^2x+2tx-3x+t^3-t^2+t+2)\), which is factor (a).

Removing the six-dimensional space of rigid motions of the molecule (the Lie algebra of the Euclidean group: three translations and three rotations), the space of vibrational states is \(180-6=174\)-dimensional, and the number of distinct vibrational modes is at most \(48-2=46\).

Suppose \(G\) is a graph on \(n\) vertices with no boundary that has a covering vertex \(x_0\), i.e. \(x_0\) is adjacent to every other vertex, so \(d_{x_0}=n-1\). Then the spectral gap satisfies

where \(\delta _2\) denotes the second largest degree in \(G\).

The cycle \(C_n\), as the Cayley graph of \(\mathbb {Z}_n\) with generating set \(\{ 1,n-1\} \), has irreducible representations \(\rho _k(g)=e^{2\pi i k g/n}\), \(k=0,\dots ,n-1\), all one-dimensional, and its normalized Laplacian eigenvalues are

For a connected induced subgraph \(S\) with \(\partial S\ne \emptyset \),

Suppose \(G\) satisfies, for some fixed \(\alpha \) with \(0\le \alpha {\lt}1\),

Then the Cheeger constant satisfies \(h_G \ge \tfrac {1-\alpha }{2}\), and consequently

There are constants \(c,c'{\gt}0\) such that for every graph \(G\) on \(n\) vertices, \(\dfrac {\chi (G)}{\omega (G)}{\lt}\dfrac {cn}{(\log n)^2}\), and for every \(n\) there exists a graph on \(n\) vertices with \(\dfrac {\chi (G)}{\omega (G)}\ge \dfrac {c’n}{(\log n)^2}\). In particular \(\vartheta (G)\) and \(\sigma (G)\) can fail to estimate \(\omega (G)\) or \(\chi (G)\) within any constant factor.

For all sufficiently large \(n\) there exists a graph on \(n\) vertices whose maximum clique and whose maximum independent set both have size at most \(2\log n\). In particular such graphs exist, although no explicit description of one is known.

Let \(H\) be a graph on \(n\) vertices, each labelled by an element of a finite group \(\Gamma \), and consider the walk in which at each step one vertex \(v\) with label \(f\) may be relabelled \(gf\) or \(f^{-1}\), where \(g\) is the label of a neighbor of \(v\); assume the initial labels generate \(\Gamma \). Then, using Theorem 168, the mixing time toward a random generating set is at most \(c\, D\, n^{2}\), where \(c\) depends only on \(|\Gamma |\) and \(D\) is the diameter of \(H\).

Let \(\rho _{min},\rho _{max}\) be the smallest and largest eigenvalues of the adjacency matrix \(A\) of \(G\). Then \(\chi (G)\ge 1-\dfrac {\rho _{max}}{\rho _{min}}\).

For the intersection graph with isotropy group \(S_r\times S_{n-r}\), the pair \((S_n, S_r\times S_{n-r})\) is a Gelfand pair, and the space \(\mathcal F(v)=\{ f:V\to \mathbb {R}\} \) decomposes into \(\mathrm{Aut}\)-invariant pieces

each of which is an eigenspace of the adjacency operator.

Just as the eigenvalues of a (weighted) Cartesian product satisfy \(\lambda _{G\otimes H}=\tfrac 12(\lambda _G+\lambda _H)\), the log-Sobolev constants satisfy

In particular for the \(n\)-cube \(Q_n\) (which is an \(n\)-fold product of an edge) one obtains \(\alpha _{Q_n}=\lambda _1/2=1/n\), so the lazy random walk on \(Q_n\) converges in time of order \(n\log n\).

A graph of maximum degree \(k\) and diameter \(D\) has at most

vertices; that is, \(n(k,D)\le M(k,D)\).

The eigenvalues \(\rho _i\) of the Neumann random-walk transition matrix \(P\) are related to the Neumann eigenvalues by \(\rho _i=1-\lambda _{S,i}\). In particular \(\rho =\rho _1=1-\lambda _{S,1}=1-\lambda _S\).

Let \(n=|S|\) and let \(\lambda _i\) be the Dirichlet eigenvalues of \(S\). Then

Thus the partition function is reduced, up to the boundary factor \(e^{-cH(f_0)}\) and elementary constants, to the product of the Dirichlet eigenvalues, which by Theorem 331 counts rooted spanning forests.

The Petersen graph is distance transitive on \(10\) vertices with diameter \(D=2\). Its normalized Laplacian eigenvalues are

Let \(G\) be a random graph on \(n\) vertices with fixed edge density \(\rho \). Then, for fixed \(\alpha \),

where \(c\) depends only on \(\rho \) and \(\alpha \); one may take \(c = \alpha \sqrt{\rho \, H(\alpha )}\) with \(H\) the binary entropy function.

For a fixed volume \(m\), the edge boundary of \(X\subseteq V(Q_n)\) with \(\operatorname {vol}X=m\) is minimized when \(X\) is close to a Hamming ball; hence the \(n\)-cube \(Q_n\) has isoperimetric dimension \(\delta =n/\log n\) and isoperimetric constant \(c_\delta =1\). By Theorem 430,

For a punctured cube \(Q_n'\) (obtained by removing one vertex from \(Q_n\)) the isoperimetric dimension is virtually unchanged, so its (lazy) random walk also converges in time \(O(n\log n)\).

Let \(G\) be a weighted graph with transition matrix \(P(u,v)=w_{u,v}/d_u\), stationary distribution \(\pi (x)=d_x/\operatorname {vol}G\) where \(\operatorname {vol}G=\sum _x d_x\), and let \(\lambda \) be as in 400. Then the relative pointwise distance after \(s\) steps satisfies

For the \(n\)-cube \(Q_n\), \(rc(Q_n)\le 4\).

For graphs \(G,G'\), \(rt(G\times G')\le 2\, rt(G)+rt(G')\), and by symmetry

For the complete graph \(K_n\), \(rt(K_n)=2\); moreover every permutation of \(S_n\) is a product of at most two permutations, each a product of disjoint transpositions along edges of \(K_n\).

For the complete bipartite graph \(K_{n,n}\) with \(n\ge 3\), \(rt(K_{n,n})=4\).

For the \(m\times n\) grid \(P_m\times P_n\) with \(m\le n\), \(rt(P_m\times P_n)\le 2m+n\).

For the \(n\)-cube \(Q_n\), \(rt(Q_n)\le 2n-1\). Also \(rt(Q_n)\ge n\) (its diameter), with \(rt(Q_n)\ge n+1\) for \(n=2,3\).

For every connected graph \(G\), \(rt(G)\ge D(G)\), where \(D(G)\) is the diameter.

For the path \(P_n\) on \(n\) vertices, \(rt(P_n)=n\). Any permutation of \(P_n\) can be sorted in \(n\) steps by odd–even transposition sort: label consecutive edges \(e_1,\dots ,e_{n-1}\) and, on even (resp. odd) steps, interchange along the even edges \(e_{2k}\) (resp. odd edges \(e_{2k+1}\)).

For every tree \(T_n\) on \(n\) vertices, \(rt(T_n){\lt}3n\).

Let \(G\) have edge density \(\tfrac 12\) and, for \(s\ge 4\), let \(M(s)\) be any graph on \(s\) vertices; write \(N^{*}_G(M(s))\) for the number of labelled induced subgraphs of \(G\) isomorphic to \(M(s)\). Then the quasi-random properties are equivalent to

and quantitatively

In particular, if a quasi-random \(G\) of edge density \(\tfrac 12\) contains \((1+o(1))\tfrac {n^4}{16}\) labelled copies of \(C_4\), then \(G\) contains the expected number of copies of every fixed graph.

Let \(\rho _{max}\) be the largest eigenvalue of the adjacency matrix \(A\) of \(G\). Then \(\chi (G)\le 1+\rho _{max}\).

Let \(\Gamma \) be a Cayley graph with vertices labelled by a group \(\mathcal H\) and symmetric edge generating set \(\mathcal K\), of degree \(k=|\mathcal K|\). For an irreducible representation \(\rho \) of \(\mathcal H\) of dimension \(l\), the eigenvalues of \(\Gamma \) are exactly the eigenvalues of the \(l\times l\) matrix

as \(\rho \) ranges over all irreducible representations of \(\mathcal H\). Each eigenvalue of the \(\dim \rho \times \dim \rho \) block occurs with multiplicity \(\dim \rho \) in \(\Gamma \).

The Cheeger constant of \(G\) satisfies

where \(f\) ranges over all functions \(f:V\to \mathbb {R}\) not identically zero. Formally, \(h_G=\inf _f\sup _c \int |\nabla f|\big/\int |f-c|\).

Suppose \(\Gamma \) is a finite edge-transitive graph of diameter \(D\). Then the Cheeger constant \(h_\Gamma \) satisfies

For a connected graph \(G\),

Together with Lemma 72 this gives \(2h_G\ge \lambda _1{\gt}h_G^2/2\).

Suppose \(\Gamma \) is a finite vertex-transitive graph of diameter \(D\) and degree \(k\). Then the Cheeger constant satisfies

Suppose \(\Gamma \) is a finite vertex-transitive graph of diameter \(D\). Then

Since \(\operatorname {index}\Gamma \le k\) this strengthens Theorem 276. The term \(\operatorname {index}\Gamma \) cannot be deleted: there are Cayley graphs with \(h_\Gamma =c/(kD)\) (see Construction 278).

For any graph \(G\), \(\ \omega (G)\le \sigma (G)\).

Let \(G\) and \(G'\) be connected graphs with the same vertex set and eigenvalues \(\lambda _1,\lambda _1'\). Assume that for each edge \(\{ x,y\} \in E(G)\) there is a path \(P(x,y)\) in \(G'\) of length at most \(l\), that for each vertex \(v\) the degree \(d_v\) of \(v\) in \(G\) satisfies \(d_v\ge a\, d_v'\) (with \(d_v'\) its degree in \(G'\)), and that every edge of \(G'\) lies in at most \(m\) paths \(P(x,y)\). Then

Let \(G\) and \(G'\) be connected graphs with eigenvalues \(\lambda _1,\lambda _1'\), and suppose \(V(G)\) is embedded into \(V(G')\) by a map \(\varphi \colon V(G)\to V(G')\). Suppose that for fixed positive \(a,l,m\):

• each edge \(\{ x,y\} \in E(G)\) is associated with a path \(P_{x,y}\) joining \(\varphi (x)\) to \(\varphi (y)\) in \(G'\) of length at most \(l\);

• for each \(v\in V(G')\), \(\displaystyle \sum _{x\in \varphi ^{-1}(v)}d_x\ge a\, d_v'\) (with \(d_x,d_v'\) the degrees in \(G,G'\));

• each edge of \(G'\) lies in at most \(m\) of the paths \(P_{x,y}\).

Then \(\displaystyle \lambda _1'\ge \frac{a\lambda _1}{lm}\).

Let \(G\) and \(G'\) be connected regular graphs with the same vertex set, eigenvalues \(\lambda _1,\lambda _1'\) and degrees \(k,k'\) respectively. Assume that for each edge \(\{ x,y\} \in E(G)\) there is a path \(P(x,y)\) in \(G'\) joining \(x\) and \(y\) of length at most \(l\), and that every edge of \(G'\) lies in at most \(m\) of the paths \(P(x,y)\). Then

For the Neumann walk on the space of tables \(\mathcal{T}(\bar r,\bar c)\) satisfying

the least nontrivial Neumann eigenvalue \(\lambda _1\) of the induced subgraph \(S=\mathcal{T}\) satisfies

Let \(P\) be the natural Neumann walk on \(\mathcal{T}(\bar r,\bar c)\) with least nontrivial Neumann eigenvalue \(\lambda _1\), and let \(\Delta (t)\) denote its relative pointwise distance to the uniform stationary distribution after \(t\) steps. If

and

then \(\Delta (t){\lt}\epsilon \).

A harmonic eigenfunction for the contracted path \(P\) is an eigenfunction for the distance transitive graph \(\Gamma \) with the same eigenvalue.

In a weighted graph \(G\) with isoperimetric dimension \(\delta \) and isoperimetric constant \(c_\delta \), the random walk approaches stationarity in

for some absolute constant \(c''\), where \(\lambda =\lambda _1\) if \(1-\lambda _1\ge \lambda _{n-1}-1\) and \(\lambda =2\lambda _1/(\lambda _1+\lambda _{n-1})\) otherwise. More precisely \(\Delta (t)\le e^{-c}\) once \(t\ge \frac{c\log \operatorname {vol}G}{\lambda \delta }+\frac{c'}{\lambda }\).

In a weighted graph \(G\) with log-Sobolev constant \(\alpha \), we have \(\Delta (t)\le e^{2-c}\) whenever

In a weighted graph \(G\) with log-Sobolev constant \(\alpha \), we have \(\Delta _{TV}(t)\le \tfrac 12 e^{1-c}\) whenever

Let \(S\) be a convex subgraph of a lattice graph, embedded into a \(d\)-dimensional manifold \(M\) with convex boundary and distance function \(\mu \). Let \(\mathcal{K}\) be the set of edge generators and \(\epsilon = \min \{ \mu (x,gx): g\in \mathcal{K}\} \). In the first-order approximation of the discrete Laplacian \(\mathcal{L}\) by the continuous Laplace operator,

where \(\mathcal{K}^{*}\) contains exactly one of \(a,a^{-1}\) for each \(a\in \mathcal{K}\). Suppose \(C_1 I \le (a_{ij}) \le C_2 I\). Then the Neumann eigenvalue \(\lambda _1\) of \(S\) satisfies

where \(U\) is the volume of the Voronoi region, \(D(M)\) the diameter of \(M\), and \(c_0\) is an absolute constant satisfying \(c_0 \le C_0\min \{ C_1,C_2^{-1}\} \) for some absolute constant \(C_0\).

For a real symmetric operator \(M\) with eigenvalues \(\mu _0 \le \cdots \le \mu _{n-1}\) and orthonormal eigenvectors \(\phi _0,\dots ,\phi _{n-1}\), the \(k\)-th eigenvalue satisfies \(\mu _k = \min \{ \langle g, Mg\rangle /\langle g,g\rangle : g \ne 0,\ g \perp \phi _0,\dots ,\phi _{k-1}\} \), and \(\mu _{n-1} = \max _{g\ne 0}\langle g,Mg\rangle /\langle g,g\rangle \) (Rayleigh variational principle).

For any graph \(G\),

For a regular graph \(G\) with Laplacian eigenvalues \(\lambda _0=0\le \lambda _1\le \dots \le \lambda _{n-1}\),

where \(N_x=N(x)=\{ y:y\sim x\} \) and \(d_x=|N_x|\).

For an undirected graph \(G\) with \(e=|E(G)|\), replace each edge \(\{ u,v\} \) by the two directed edges \((u,v),(v,u)\). Suppose there is a set \(P\) of \(4e^2\) directed paths such that for each ordered pair of directed edges there is a directed path in \(P\) joining them, and each directed edge of \(G\) lies in at most \(m\) paths of \(P\). Then

For an undirected graph \(G\) with \(e=|E(G)|\), replace each edge \(\{ u,v\} \) by the two directed edges \((u,v),(v,u)\). Suppose there is a set \(P\) of \(4e^2\) directed paths such that for each ordered pair of directed edges there is a directed path in \(P\) joining them, each of length at most \(l\), and each directed edge of \(G\) lies in at most \(m\) paths of \(P\). Then

For an induced subgraph \(S\) in a graph \(G\) with \(\delta S\ne \emptyset \), the number of rooted spanning forests of \(S\) is

where \(\lambda _i\), \(1\le i\le |S|\), are the Dirichlet eigenvalues of the Laplacian of \(S\) in \(G\).

For a graph \(G\),

Let \(X,Y\) be two subsets of the vertex set \(V\) of a graph \(G\). Then

where \(\bar\lambda = \max _{i\neq 0}|1-\lambda _i|\).

Let \(X,Y\) be two subsets of the vertex set \(V\) of a graph \(G\). Then

where \(\bar\lambda = \max _{i\neq 0}|1-\lambda _i|\).

For a graph \(G\),

(The irregularity \(\operatorname {irr} G\) may be replaced by \(\operatorname {var} G\), using \(\)

Let \(G\) be a weighted graph with isoperimetric dimension \(\delta {\gt}2\), i.e. for every \(X\subseteq V(G)\) with \(\operatorname {vol}X\le \operatorname {vol}\bar X\) one has \(\sum _{x\in X,\, y\notin X}w_{x,y}\ge c_\delta (\operatorname {vol}X)^{(\delta -1)/\delta }\). If \(f\) is a harmonic eigenfunction with eigenvalue \(\lambda \), then

for some absolute constant \(c\).

In a distance transitive graph \(\Gamma \), let \(A_j\) be the \(n\times n\) matrix with \(A_j(x,y)=1\) if \(d(x,y)=j\) and \(0\) otherwise. For each harmonic eigenfunction \(f\) of the contracted path \(P\), the corresponding eigenvalue of \(A_j\) is

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

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

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

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

A distance transitive graph of diameter \(D\) has exactly \(D+1\) distinct eigenvalues.

The eigenvalues of a distance transitive graph \(\Gamma \) of diameter \(D\) are the eigenvalues of the weighted path \(P\) on \(D+1\) vertices of Construction 286.

The eigenvalues of a distance transitive graph \(\Gamma \) of diameter \(D\) have the same values as the eigenvalues of the weighted path \(P\) of \(D+1\) vertices obtained by contracting each \(V_i=\{ u:d(u,v)=i\} \), for a fixed vertex \(v\), to a single vertex. (The multiplicities in \(\Gamma \) and \(P\) differ; in \(P\) all eigenvalues are simple.)

For a distance transitive graph \(\Gamma \) on \(n\) vertices the multiplicity \(m(\lambda )\) of an eigenvalue \(\lambda \) is

where \(g\) is the corresponding eigenfunction of the weighted path \(P\) contracted from \(\Gamma \) about a fixed vertex \(v_0\).

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

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)\),

For an edge-transitive graph \(\Gamma \) with diameter \(D\) and degree \(k\),

Let \(G\) have isoperimetric dimension \(\delta {\gt}2\) and isoperimetric constant \(c_\delta \). The \(k\)-th eigenvalue \(\lambda _k\) of \(\mathcal{L}\) satisfies

where \(c_4=\frac{\delta }{2e}\, c_3^{-2/\delta }\) depends only on \(\delta \).

Suppose a weighted undirected graph \(G\) has isoperimetric dimension \(\delta {\gt}2\) and isoperimetric constant \(c_\delta \), and let \(S\) be an induced subgraph. The \(k\)-th Dirichlet or Neumann eigenvalue \(\lambda _k\) of \(S\) satisfies

where \(c_4\) is a constant depending only on \(\delta \).

For a vertex-transitive graph \(\Gamma \) with diameter \(D\) and degree \(k\),

This is inequality (7.1): it lets one bound eigenvalues purely from the degree and diameter, which is central to rapidly mixing Markov chains.

For a vertex-transitive graph \(\Gamma \) with diameter \(D\) we have

where \(\operatorname {index}\Gamma =\min _i \operatorname {vol}\Gamma /(2|E_i|)\) and \(E_i\) is the \(i\)-th equivalence class of edges under \(\mathrm{Aut}(\Gamma )\).

The diagonal Ramsey number satisfies

In particular there exist graphs on \(n\) vertices with no clique and no independent set of size \(2\log _2 n\) when \(n\) is sufficiently large.

For any graph \(G\) of edge density \(1/2\),

for an absolute constant \(c {\gt} 0\). Hence for graphs with \(\bar\lambda \sim 1/\sqrt k\) the eigenvalue upper bound \(\operatorname {disc}(G;\alpha ) \le c'\sqrt k\, \alpha n\) is within a constant factor of best possible.

Let \(S\) be a convex subgraph in an abelian homogeneous graph \(\Gamma \) with edge generating set \(\mathcal{K}\) of \(k\) generators, and let \(f\colon S\to \mathbb {R}\) be an eigenfunction with associated Dirichlet eigenvalue \(\lambda \). Then for all \(x\in S\), \(a\in \mathcal{K}\) and every \(\alpha {\gt}2\),

Let \(\Gamma \) be an invariant homogeneous graph with edge generating set \(\mathcal{K}\) of \(k\) generators, and suppose \(f\colon V(\Gamma )\to \mathbb {R}\) satisfies \(Lf(x)=\frac1k\sum _{a\in \mathcal{K}}\bigl(f(x)-f(ax)\bigr)=\lambda f(x)\). Then for all \(x\in V(\Gamma )\) and every \(\alpha {\gt}2\) (assuming \(f\) attains a maximum of the functional below, e.g. \(\Gamma \) finite),

Let \(S\) be a finite strongly convex subgraph in an abelian homogeneous graph \(\Gamma \) with edge generating set \(\mathcal{K}\) of \(k\) generators, and let \(f\colon S\to \mathbb {R}\) be an eigenfunction with associated Neumann eigenvalue \(\lambda \). Then for all \(x\in S\), \(a\in \mathcal{K}\) with \(ax\in S\), and every \(\alpha {\gt}2\),

Let \(S\) be an induced subgraph with boundary.

• For every \(t{\gt}0\), the Neumann eigenvalue \(\lambda _1\) of \(S\), with heat kernel \(H_t\), satisfies

  \[ \lambda _1 \; \ge \; \frac{1}{2t}\sum _{x\in S}\; \inf _{y\in S} \frac{H_t(x,y)\sqrt{d_x}}{\sqrt{d_y}} . \]

• For every \(t{\gt}0\), the Dirichlet eigenvalue \(\lambda '_1\) of \(S\), with Dirichlet heat kernel \(H'_t\), satisfies

  \[ \lambda '_1 \; \ge \; \frac{1}{2t}\sum _{x\in S}\; \inf _{y\in S} \frac{H'_t(x,y)\sqrt{d_x}}{\sqrt{d_y}} . \]

For a graph \(G\) with isoperimetric dimension \(\delta {\gt}2\) and isoperimetric constant \(c_\delta \), the eigenvalues \(0=\lambda _0\le \lambda _1\le \cdots \le \lambda _{n-1}\) of \(\mathcal{L}\) satisfy

where \(c_3\) is a constant depending only on \(\delta \).

For a weighted undirected graph \(G\) with isoperimetric dimension \(\delta {\gt}2\) and an induced subgraph \(S\), the Dirichlet or Neumann eigenvalues \(\lambda _i\) of \(S\) satisfy

where \(c_3\) is a constant depending only on \(\delta \).

Let \(\Gamma \) be a homogeneous graph with associated group \(\mathcal H\), isotropy group \(\mathcal I\), and edge generating set \(\mathcal K=\mathcal I\mathcal K\mathcal I\) (a union of double cosets), of degree \(k\). The eigenvalues of \(\Gamma \) are the eigenvalues of

as \(\rho \) ranges over the irreducible representations of \(\mathcal H\).

For any connected graph \(G\),

In a connected graph \(G\) with isoperimetric dimension \(\delta {\gt}1\) and isoperimetric constant \(c_\delta \), for an arbitrary function \(f:V(G)\to \mathbb {R}\) let \(m\) denote the largest value such that

Then

Let \(G\) be a weighted undirected graph with edge weights \(w_{u,v}\) having isoperimetric dimension \(\delta \) and isoperimetric constant \(c_\delta \). Let \(S\subseteq V(G)\) and let \(S^{*}\) be the set of edges with at least one endpoint in \(S\). Then any function \(f:S\cup \delta S\to \mathbb {R}\) satisfying either Dirichlet or Neumann boundary conditions satisfies

In an abelian homogeneous graph \(\Gamma \) with edge generating set \(\mathcal K\) of \(k\) generators, let \(S\) be a strongly convex subgraph and suppose \(f:S\cup \delta S\to \mathbb R\) satisfies the Dirichlet or Neumann boundary condition, achieves the log-Sobolev constant, and \(\sum _{x\in S}f^2(x)d_x=\operatorname {vol}S\). Then, with \(U=\sup _y|f(y)|\), for every \(x\in S\),

In an invariant homogeneous graph \(\Gamma \) with edge generating set \(\mathcal K\) of \(k\) generators, suppose \(f:V(\Gamma )\to \mathbb R\) achieves the log-Sobolev constant and satisfies \(\sum _x f^2(x)d_x=\operatorname {vol}G\). Then, with \(U=\sup _y|f(y)|\ge 1\), for every \(x\in V(\Gamma )\),

Let \(f\) satisfy 416 and achieve \(\alpha \), and suppose \(M\) has non-negative Ricci curvature. Then

For a graph \(G\), suppose \(f:V\to \mathbb R\) satisfies \(\sum _x f^2(x)d_x=\operatorname {vol}G\) and achieves the log-Sobolev constant \(\alpha \). Then, with \(L\) the combinatorial Laplacian \(Lf(x)=\sum _{y\sim x}(f(x)-f(y))\), for every vertex \(x\),

Suppose the heat kernel \(H_s=e^{-s\mathcal L}\) of a weighted graph \(G\) satisfies

for all \(f:V(G)\to \mathbb R\), with \(p=e^{\beta s}\) for some \(\beta {\gt}0\). Then the random walk satisfies \(\Delta (t)\le e^{2-c}\) whenever

where \(\lambda \) is as in 400.

Under the same hypothesis 408 (12.10) with \(p=e^{\beta s}\), the random walk on \(G\) satisfies \(\Delta _{TV}(t)\le \tfrac 12 e^{1-c}\) whenever

In a graph \(G\) with log-Sobolev constant \(\alpha \), the heat kernel \(H_t=e^{-t\mathcal L}\) satisfies

for every \(t{\gt}0\), with \(p=e^{4\alpha t}+1\), and every \(f:V(G)\to \mathbb R\).

Let \(S\) be a strongly convex subgraph of a connected abelian homogeneous graph \(G\), and suppose \(f:V\to \mathbb R\) satisfies the Dirichlet or Neumann boundary condition, achieves the log-Sobolev constant \(\alpha \), and \(\sum _{x\in S}f^2(x)d_x=\operatorname {vol}S\). Then

where \(U=\sup _z|f(z)|\), \(k\) is the degree, \(D\) is the diameter of \(S\), and \(\lambda _1\) is the first eigenvalue of the Laplacian of \(G\).

In a connected invariant homogeneous graph \(G=(V,E)\), suppose \(f:V\to \mathbb R\) satisfies the logarithmic Harnack inequality and \(\sum _x f^2(x)d_x=\operatorname {vol}G\). Then the log-Sobolev constant \(\alpha \) satisfies

where \(U=\sup _z|f(z)|\), \(k\) is the degree and \(D\) is the diameter of \(G\).

Let \(S\) be a strongly convex subgraph of a connected homogeneous invariant graph with isoperimetric dimension \(\delta \), and suppose \(f:V\to \mathbb R\) satisfies the Dirichlet or Neumann boundary condition, achieves the log-Sobolev constant, and \(\sum _{x\in S}f^2(x)d_x=\operatorname {vol}S\). Then

where \(U=\sup _z|f(z)|\), \(k\) is the degree, \(D\) is the diameter of \(S\), and \(\lambda _1\) is the first eigenvalue of the Laplacian of \(G\). Consequently a random walk on such a graph with bounded isoperimetric dimension converges in time of order \((\log \log n)\, kD^2\).

For a \(d\)-dimensional compact Riemannian manifold \(M\) with non-negative Ricci curvature, diameter \(D(M)\) and first Laplacian eigenvalue \(\lambda _1\),

In a connected invariant homogeneous graph \(\Gamma \) with edge generating set \(\mathcal K\) of \(k\) generators, if \(f:V(\Gamma )\to \mathbb R\) achieves the log-Sobolev constant and \(\sum _x f^2(x)d_x=\operatorname {vol}G\), then

where \(e\) is the base of the natural logarithm.

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\),

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\),

In a finite directed network with a source \(s\), a sink \(t\), and nonnegative capacities on the directed edges, the maximum value of an \(s\)–\(t\) flow equals the minimum total capacity of an \(s\)–\(t\) cut.

For a graph \(G\),

where \(f\) ranges over all \(f:V\to \mathbb {R}\) not identically zero.

Let \(S\) be a convex subgraph of an abelian homogeneous graph \(\Gamma \) of degree \(k\), and let \(D\) be the diameter of \(S\). Then the Neumann eigenvalue \(\lambda _S\) of \(S\) satisfies

For a \(k\)-regular graph \(G\) on \(n\) vertices, suppose there is a set \(P\) of \(\binom {n}{2}\) paths joining all pairs of vertices such that each path in \(P\) has length at most \(l\) and each edge of \(G\) is contained in at most \(m\) paths in \(P\). Then

The Cheeger constant of a weighted cartesian product satisfies

In particular, for two graphs,

Let \(G\) range over a family of graphs satisfying the almost-regular property \(P_r\) (i.e. \(\operatorname {irr} G=o(1)\)), and with edge density \(\rho \) bounded away from \(0\). Then the following three quasi-random properties are equivalent:

Equivalently, \(P_e+P_r\), \(P_{\mathrm{disc}}+P_r\) and \(P_{\mathrm{dev}}+P_r\) all coincide.

The properties \(P_1,\dots ,P_6\) of Definition 171 are mutually equivalent: any graph (family) satisfying one of them satisfies them all, in the sense that \(P(o(1)) \Rightarrow P'(o(1))\) for each pair.

There is a number \(R(k,\ell )\) such that any graph on \(n \ge R(k,\ell )\) vertices contains either a complete graph of size \(k\) or an independent set of size \(\ell \).

Let \(G\) be a regular graph on \(n\) vertices and \(l\ge \log n/\lambda _1\). For each \(v\in V\) independently, let \(W(v)\) be a random walk of length \(l\) starting at \(v\). Let \(I(v)\) be the number of other walks \(W(u)\) for which there exist a vertex \(x\) and indices \(0\le i,j\le l\) with \(|i-j|{\lt}5\) such that \(W(v)\) visits \(x\) at time \(i\) and \(W(u)\) visits \(x\) at time \(j\). Then almost surely there is no vertex \(v\) with \(I(v){\gt}100l\).

Let \(G\) be a graph on \(n\) vertices and suppose \(l\ge \log n/\lambda _1\). Suppose for each \(v\in V(G)\) there are \(d_v\) walks of length \(l\) starting at \(v\). For any edge \(q\) let \(I(q)\) be the total number of these walks containing \(q\). Then almost surely (with probability tending to \(1\) as \(n\to \infty \)) there is no edge \(q\) with \(I(q){\gt}10l\).

Suppose a random walk is associated with a weighted graph \(G\) (of total weight \(\mathrm{vol}\, G\)) with heat kernel \(H_t\). Then the relative pointwise distance of the random walk after \(t\) steps to its stationary distribution is bounded by

Consequently, choosing \(t=\frac1\lambda \log \frac{\mathrm{vol}\, G}{\epsilon \min _x d_x}\) gives \(\Delta (t)\le \epsilon \), where \(\lambda =\lambda _1\) is the spectral gap.

Let \(G\) be a regular graph on \(n\) vertices and let \(\sigma \) be a permutation of order two on \(V\) (a product of disjoint transpositions). Put \(l=\frac{10}{\lambda _1}\log n\). Then there is a system of \(n\) walks \(W(v)\), \(v\in V\), each of length \(2l\), such that both \(W(v)\) and \(W(\sigma (v))\) connect \(v\) and \(\sigma (v)\) and traverse the same edge set (in opposite directions), and such that, letting \(I(v)\) be the number of other walks \(W(u)\) for which there exist \(x\) and indices \(0\le i,j\le l\) with \(|i-j|{\lt}5\) so that \(W(v)\) visits \(x\) at time \(i\) and \(W(u)\) visits \(x\) at time \(2l-j\), one has \(I(v)\le 400l\) for all \(v\).

A real symmetric matrix is orthogonally diagonalizable; in particular its eigenvalues are real and it admits an orthonormal basis of eigenvectors. A positive semidefinite symmetric matrix has nonnegative eigenvalues.

For real numbers \(0{\lt}\alpha {\lt}1/\beta {\lt}1\), suppose an integer \(k\) satisfies

Then for any integer \(n\) there exists a \(k\)-regular bipartite graph with vertex set \(A\cup B\), \(|A|=|B|=n\), such that every subset \(X\subseteq A\) with \(|X|\le \alpha n\) has at least \(\beta |X|\) neighbors in \(B\). In fact almost all random \(k\)-regular bipartite graphs have this property.

Let \(G\) be a \(k\)-regular graph on \(n\) vertices and let \(\pi \) be a permutation of its vertices. Then there are paths \(P_x\) joining \(x\) to \(\pi (x)\) of length at most \(\frac{2}{\lambda _1}\log n\) such that each edge of \(G\) is contained in at most \(\frac{20}{k\lambda _1}\log n\) paths.

Let \(\sigma \) be a permutation of the vertex set of a regular graph \(G\) on \(n\) vertices. Then

For a weighted graph \(G\) we can choose a modified random walk \(P\) so that the relative pointwise distance satisfies

where \(\lambda = \lambda _1\) if \(2 \ge \lambda _{n-1} + \lambda _1\), and \(\lambda = \frac{2\lambda _1}{\lambda _{n-1}+\lambda _1}\) otherwise. In particular, after \(t \ge \frac{1}{\lambda }\log \frac{\operatorname {vol}G}{\epsilon \, \min _x d_x}\) steps, \(\Delta (t) \le \epsilon \).

For any graph \(G\),

Let \(G\) be a graph on \(n\) vertices and let \(A=\{ (x_i,y_i):x_i\in X,\ y_i\in Y\} \) be any assignment in which each vertex \(v\) occurs in \(X\) with multiplicity \(d_v\) and in \(Y\) with multiplicity \(d_v\). Then there are paths \(P_i\) joining \(x_i\) to \(y_i\), each of length at most \(\frac{20}{\lambda _1}\log n\), such that each edge of \(G\) is contained in at most \(\frac{20}{\lambda _1}\log n\) of the paths.

For any graph \(G\) containing at least one edge,

For a graph \(G\) with isoperimetric dimension \(\delta {\gt}2\) and isoperimetric constant \(c_\delta \), any function \(f:V(G)\to \mathbb {R}\) satisfies

where \(\gamma =\dfrac {2\delta }{\delta -2}\) and \(c_2=\sqrt{c_\delta }\, \dfrac {\delta -1}{2\delta }\).

Let \(G\) be a weighted undirected graph with edge weights \(w_{u,v}\) having isoperimetric dimension \(\delta {\gt}2\) and isoperimetric constant \(c_\delta \). Then any function \(f:V(G)\to \mathbb {R}\) satisfying either Dirichlet or Neumann boundary conditions satisfies

where \(\gamma =\frac{2\delta }{\delta -2}\) and \(c_2=\sqrt{c_\delta }\, \frac{\delta -1}{2\delta }\).

For a connected graph \(G\) with maximum degree \(d\),

Suppose \(G\) is vertex-transitive. Then a random walk after \(s\) steps converges to the uniform distribution in total variation (and \(\chi \)-squared) distance with

where \(\lambda _i\) ranges over the nontrivial eigenvalues of \(\mathcal{L}\).

Let \(\Gamma \) be a homogeneous graph with associated group \(\mathcal H\), isotropy group \(\mathcal I\), and edge generating set \(\mathcal K\). Suppose \(\rho \) is a representation of \(\mathcal H\) on \(X\) with \(A_{ae}=\rho (a)A_e\rho (a)^{-1}\), where \(ae\) denotes the edge \(\{ ab,ac\} \) and \(e=\{ b,c\} \). Then the spectrum of the vibrational Laplacian \(\mathcal{L}_X\) is the union, over the irreducible representations \(\gamma \) of \(\Gamma \), of the spectra of the operators

For a graph \(G\) with weight function \(w\),

where \(f\) ranges over all \(f:V\to \mathbb {R}\) not identically zero.

For graphs \(G_1,\dots ,G_k\) with the natural consistent weights,

where \(\lambda _G\) denotes the first eigenvalue \(\lambda _1\) of \(G\). In particular, for \(k=2\),