By definition \(H_t = \sum _i e^{-\lambda _i t} I_i\), and the projection \(I_i\) onto the one-dimensional eigenspace spanned by the orthonormal eigenfunction \(\phi _i\) has matrix entries \(I_i(x,y) = \phi _i(x)\phi _i(y)\). Summing over \(i\) gives the stated formula.

The stated identity is the entrywise form of the matrix product \(H_s\, H_{t-s} = H_t\). Since \(H_s = e^{-s\mathcal{L}}\) and \(H_{t-s} = e^{-(t-s)\mathcal{L}}\) are exponentials of the same matrix \(\mathcal{L}\), they commute and \(e^{-s\mathcal{L}}e^{-(t-s)\mathcal{L}} = e^{-t\mathcal{L}} = H_t\).

(i) is immediate since \(H_0=I\).

(ii) Consider the all-ones vector \(\mathbf1\). The vector \(T^{1/2}\mathbf1\) (with entries \(\sqrt{d_y}\)) is, up to normalization, the eigenfunction \(\phi _0\) of \(\mathcal{L}\) with eigenvalue \(\lambda _0=0\); hence \(H_t\) fixes it:

The second equality follows from the symmetry \(H_t(x,y)=H_t(y,x)\).

(iii) Differentiating \(F = H_t f = e^{-t\mathcal{L}}f\) gives \(\partial _t F = -\mathcal{L}\, e^{-t\mathcal{L}}f = -\mathcal{L}F\).

(iv) Every eigenfunction \(\phi _i\) satisfies the imposed boundary condition (Neumann: \(\mathcal{L}\phi _i\) vanishes on \(\delta S\); Dirichlet: \(\phi _i\) vanishes on \(\delta S\)). Since \(F(\cdot ,t)\) is a linear combination of the \(\phi _i\), it inherits the same boundary condition.

(v) Writing \(\mathcal{L}=T^{-1/2}(T-A)T^{-1/2}\) and expanding,

Reorganizing this vertex sum as a sum over the edges of \(S^{*}\) and using the Neumann or Dirichlet condition of (iv) to discard boundary contributions gives \(\sum _{\{ x,y\} \in S^{*}}\bigl(F(x,t)/\sqrt{d_x}-F(y,t)/\sqrt{d_y}\bigr)^2\).

Let \(\mathcal{A} = I-\mathcal{L} = T^{-1/2}AT^{-1/2}\). Since the adjacency matrix \(A\) and the degrees are nonnegative, every entry of \(\mathcal{A}\) is nonnegative. For \(t\ge 0\) the series \(e^{t\mathcal{A}} = \sum _{k\ge 0}\frac{(t\mathcal{A})^k}{k!}\) therefore has all entries nonnegative. Because

and \(e^{-t}{\gt}0\), all entries of \(H_t\) are nonnegative.

Differentiate the left-hand side in \(t\):

Reorganize this edge sum into a vertex sum. Under the Neumann condition the boundary vertices contribute \(0\) because \(\mathcal{L}F=0\) there (Lemma 365(iv)); under the Dirichlet condition the boundary vertices contribute \(0\) because \(F=0\) there. Using the self-adjointness of \(\mathcal{L}\), in either case the expression equals

where we used \(\partial _t F = -\mathcal{L}F\) (Lemma 365(iii)). Hence the left-hand side is non-increasing in \(t\); evaluating at \(t=0\), where \(F(x,0)=f(x)\) (Lemma 365(i)), gives the claim.

We prove (i); (ii) is identical using the Dirichlet data. Fix \(f:S\cup \delta S\to \mathbb {R}\), set \(F(x,t)=(H_t f)(x)\), and define

Expanding the square and using \(\sum _y H_t(x,y)f(y)=F(x,t)\) together with Lemma 365(ii) (\(\sum _y H_t(x,y)\sqrt{d_y}=\sqrt{d_x}\)),

Summing over \(x\in S\) and using Lemma 365(ii) again (\(\sum _x H_t(x,y)\sqrt{d_x}=\sqrt{d_y}\)),

Since \(F(x,0)=f(x)\) (Lemma 365(i)), this equals

using \(\partial _s F=-\mathcal{L}F\) (Lemma 365(iii)). By Lemma 365(v),

By Fact 1 (Lemma 367) the integrand is bounded by its value at \(s=0\), so

In the other direction, writing \(H_t(x,y)\sqrt{d_xd_y}=\bigl(H_t(x,y)\sqrt{d_x/d_y}\bigr)d_y\) and pulling out the infimum,

The last step uses the choice \(c=F(x,t)/\sqrt{d_x}\) and Lemma 366, which guarantees each infimum \(\inf _{y}H_t(x,y)\sqrt{d_x/d_y}\ge 0\). Combining (10.5) and (10.6),

The left-hand side is the Rayleigh quotient of \(f\) (with the harmonic normalization); its infimum over all \(f\) is exactly the Neumann eigenvalue \(\lambda _1\). Since the inequality holds for every \(f\), we obtain \(\lambda _1 \ge \frac{1}{2t}\sum _{x\in S}\inf _{y\in S}H_t(x,y)\sqrt{d_x}/\sqrt{d_y}\), which is (i). The Dirichlet case (ii) is identical, using the Dirichlet conditions throughout Lemma 365.

Apply Theorem 368(i) with \(S=G\) and let \(t\to 0\). Since \(H_t = I - t\mathcal{L} + O(t^2)\) and \(\mathcal{L}(x,y) = -1/\sqrt{d_x d_y}\) for adjacent \(x\ne y\), we have for such pairs

Consider the term \(x=x_0\) of \(\sum _{x}\inf _{y}H_t(x,y)\sqrt{d_x}/\sqrt{d_y}\). As \(x_0\) is adjacent to every \(y\ne x_0\),

while the diagonal term (\(y=x_0\)) is \(H_t(x_0,x_0)=1+O(t)\), which is larger. Hence \(\inf _{y}H_t(x_0,y)\sqrt{d_{x_0}}/\sqrt{d_y} = \min _{y\ne x_0}\frac{t}{d_y}+O(t^2) = \frac{t}{\delta _2}+O(t^2)\), where \(\delta _2=\max _{y\ne x_0}d_y\) is the second largest degree. By Lemma 366 the remaining terms of the sum are nonnegative, so

Letting \(t\to 0\) gives \(\lambda _1\ge \frac{1}{2\delta _2}\). (For example, for \(G=P_3\) this yields \(\lambda _1\ge \frac12\) against the true value \(1\), and for \(G=K_n\) it yields \(\lambda _1\ge \frac{n}{2(n-1)}\) against the true value \(\frac{n}{n-1}\); both are off by a factor of \(2\).)

The diameter of \(M\) and the graph diameter of \(S\) are related by \(D(M)\le \epsilon \, D(S)\), since each edge of \(S\) corresponds to a generator of length at most \(\epsilon \) times a unit step. Substituting \(D(M)^2\le \epsilon ^2 D^2(S)\) into Theorem 373 gives \(\lambda _1\ge c_0 r\epsilon ^2/(d^2\epsilon ^2 D^2(S)) = c_0 r/(d^2 D^2(S))\).

We induct on \(N\). For \(N=1\) the assertion is clear. Assume it holds in all dimensions less than \(N\). It suffices to bound the distance from an arbitrary point \(\bar x=(x_1,\dots ,x_N)\) in the fundamental domain generated by the \(v_i\) to the nearest lattice point. Let \(\bar x_0\) be the orthogonal projection of \(\bar x\) onto whichever of (a) the hyperplane generated by \(v_1,\dots ,v_{N-1}\), or (b) a translate of the hyperplane generated by \(v_N\), is closer; these are two bounding hyperplanes of the fundamental domain, so \(d(\bar x,\bar x_0)\le \tfrac 12\| v_N\| \). By the induction hypothesis there is a lattice point \(v\) (in the sublattice on the chosen hyperplane) with \(d(\bar x_0,v)\le \tfrac 12\bigl(\sum _{i=1}^{N-1}\| v_i\| ^2\bigr)^{1/2}\). Hence

as claimed.

The upper bound is clear since the Voronoi regions of the points of \(S\) lie in \(M\) and have disjoint interiors. For the lower bound, consider the contracted copy \((1-\delta )M\), with the origin at the center of the ball \(B(cRN)\subset M\). Let \(L\) be any bounding hyperplane of \(M\) and \((1-\delta )L\) its contracted copy. Take \(x\in (1-\delta )M\), and suppose there were a lattice point \(y\in V(\Gamma )\setminus S\) with \(x\) in the Voronoi region of \(y\). Since \(B(cRN)\subset M\), the contraction pushes the boundary inward by at least \(\delta \, cRN\), so \(R {\gt} d(x,y)\ge \gamma \ge c\delta RN\). This is a contradiction if we take \(\delta =\frac{1}{cN}\). Consequently, for \(\delta =\frac1{cN}\), every \(x\in (1-\delta )M\) lies in the closure of the Voronoi region of a lattice point of \(S\), whence \(|S|\, \mathrm{vol}\, U\ge \mathrm{vol}\, (1-\delta )M\) and

the last inequality holding because \(cN\ge 2\).

Each edge generator corresponds to \(g = x_{ij}-x_{i'j}-x_{ij'}+x_{i'j'}\), and

Summing \(\sum _{g\in \mathcal{K}^{*}}\partial ^2/\partial g^2\) yields an operator \(Q\) whose coefficients are \((m-1)(n-1)\) on each diagonal entry \((x_{ij},x_{ij})\), \(-(m-1)\) on entries \((x_{ij},x_{i'j})\), \(-(m-1)\) on entries \((x_{ij},x_{ij'})\), and \(1\) on entries \((x_{ij},x_{i'j'})\). This \(Q\) has two distinct eigenvalues: \(mn\) with multiplicity \((m-1)(n-1)\) and \(0\) with multiplicity \(m+n-1\). When restricted to \(M\) (the subspace \(\sum _j x_{ij}=r_i,\ \sum _i x_{ij}=c_j\)), all eigenvalues equal \(mn\). Hence \((a_{ij})\) has all eigenvalues equal to

so \(C_1=C_2=8\) and \(c_0=\tfrac 1{100}\min \{ 8,\tfrac 18\} =\tfrac 1{800}\).

Place the problem in the framework of Theorem 373. The manifold \(M\) is the set of real \(mn\)-tuples with \(\sum _j x_{ij}=r_i\) and \(\sum _i x_{ij}=c_j\), so \(\dim M = N := (m-1)(n-1)\). The lattice graph \(\Gamma \) has as vertices all integer points, with \(|\mathcal{K}|=\binom {m}{2}\binom {n}{2}\) basic moves; the convex subgraph is \(S=\mathcal{T}=\cap _{i,j}\{ T\in \Gamma :x_{ij}\ge 0\} \), and the convex polytope \(M=\cap _{i,j}\{ \bar x:x_{ij}{\gt}-\tfrac 12\} \). Each edge of \(\Gamma \) has length \(2\), so \(R\le N^{1/2}\) by Lemma 376.

To apply Lemma 377 we find a large ball in \(M\). Let \(s_0=\min \{ \min _i r_i/n,\ \min _j c_j/m\} \) be the smallest line-sum average. Assuming without loss of generality \(s_0=r_1/m\), build \(T_0\) recursively: set all entries of the first row equal to \(s_0\) and subtract \(s_0\) from each \(c_j\) to form \(c'_j=c_j-s_0\); the remaining \((m-1)\times n\) table has row sums \(r_2,\dots ,r_m\) and column sums \(c'_1,\dots ,c'_n\), whose line-sum averages are still at least \(s_0\). Continuing, one obtains a table \(T_0\) (with rational entries) all of whose entries are at least \(s_0\); hence a ball \(B(s_0)\) of radius \(s_0\) centered at \(T_0\) lies in \(M\). Thus if \(s_0{\gt}cN^{3/2}\) then by Theorem 373 (with \(\epsilon ^2=4\) from the edge length \(2\), \(d=N\), \(c_0=\tfrac 1{800}\) from Lemma 378) and (10.17),

Finally, \(\mathrm{diam}\, M {\lt} 2\min \{ (\sum _i r_i^2)^{1/2},(\sum _j c_j^2)^{1/2}\} \), so \((\mathrm{diam}\, M)^2 {\lt} 4\min \{ \sum _i r_i^2,\sum _j c_j^2\} \). Substituting this, \(c_0=\tfrac 1{800}\) and \(N=(m-1)(n-1)\), and loosening \(4^{1/c}\le 4e^{1/c}\), gives

which is (10.16); the hypothesis \(s_0{\gt}cN^{3/2}\) is exactly \(\min \{ \min _i r_i/n,\min _j c_j/m\} {\gt}c(m-1)^{3/2}(n-1)^{3/2}\).

The relative pointwise distance is controlled by the Neumann eigenvalue:

Hence \(\Delta (t){\lt}\epsilon \) whenever

Now \(|\mathcal{T}|\le \min \{ \prod _i r_i^{\, n},\prod _j c_j^{\, m}\} \), so \(\ln (|\mathcal{T}|/\epsilon )\le \ln \tfrac 1\epsilon + \min \{ n\sum _i\ln r_i, m\sum _j\ln c_j\} \). Combining this with the eigenvalue bound (10.16) of Theorem 379, which gives \(2/\lambda _1 {\lt} 6400\, e^{1/c}(m-1)^2(n-1)^2\min \{ \sum r_i^2,\sum c_j^2\} \le 6400\, e^{1/c}m^2 n^2\min \{ \sum r_i^2,\sum c_j^2\} \), we obtain that the stated lower bound (10.22) on \(t\) suffices for \(\Delta (t){\lt}\epsilon \).

Let \(P=T^{-1}A\) be the transition probability matrix, so that \(P = T^{-1/2}(I-\mathcal{L})T^{1/2}\) and \(P^s = T^{-1/2}\sum _i(1-\lambda _i)^s I_i\, T^{1/2}\). The \(i=0\) term is the stationary projection \(p_0=I_0\). Using \(1-\lambda _i\le e^{-\lambda _i}\) and \(\lambda _i\ge \lambda =\lambda _1\) for \(i\ne 0\),

Let \(\pi (x)=d_x/\mathrm{vol}\, G\) be the stationary distribution and let \(\psi _x\) be the indicator of the vertex \(x\). Then

where we used \((1-\lambda _i)^t\le e^{-\lambda _i t}\), the identity \(\sum _i e^{-\lambda _i t}I_i = H_t\), and \(T^{-1/2}\psi _x=\psi _x/\sqrt{d_x}\). Finally, with \(t=\frac1\lambda \log \frac{\mathrm{vol}\, G}{\epsilon \min _x d_x}\), the bound \(H_t(x,y)\le e^{-\lambda t}\) yields \(\Delta (t)\le \epsilon \).