= Solution
Let $N=|V_n|$. Since the degrees lie between $1$ and $\Delta$,
$$
\pi_{\min}\geq\frac1{\Delta N}.
$$
The <Generalized Cheeger inequality> and $\Phi_*(u)\geq\Phi_*(c)\geq\alpha$ for $u\leq c$ give
$$
\Lambda(u)\geq\frac{\alpha^2}{2}
\qquad(\pi_{\min}\leq u\leq c).
$$
For all larger $u$, part (a) gives $\Lambda(u)\geq1/t_{\mathrm{rel}}$. Split the supplied spectral-profile integral at $c$ to obtain
$$
\begin{aligned}
t_{\mathrm{mix}}(\varepsilon)
&\leq2\int_{4\pi_{\min}}^{4/\varepsilon}\frac{du}{u\Lambda(u)}\\
&\lesssim_{\alpha,c,\Delta}
\log\frac1{\pi_{\min}}+t_{\mathrm{rel}}\log\frac1\varepsilon\\
&\lesssim\log N+t_{\mathrm{rel}}\log(1/\varepsilon).
\end{aligned}
$$
Solved by gpt-5.6-sol high.
Back to article page
