Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

Question

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower bound of $O(1/n)$ for the 2nd eigenvalue of the binary tree. I found a proof of this fact here: https://www.cs.cmu.edu/~glmiller/Publications/Papers/GuMi94-tr.pdf (lemma 3.8), but I could not prove it using the methods suggested in the lecture. Could someone help me understand this?

Answer 1

This question is still unanswered. I'll write the outline of a solution.

Rewrite $T_n$ as a sum of weighted graphs $T_{i,j}$, $i < j$, where $(i,j) \in K_n$ and $T_{i,j}$ contains the (weighted) edges of the path from $i$ to $j$ in $T_n$. In each of the summands, the weight of a given edge $(i,j)$ is $\frac{1}{paths(i,j)}$ where $paths_{n}(i,j)$ denotes the number of paths from $i$ to $j$ in $T_n$, so we indeed have $T_n = \sum_{i<j}T_{i,j}$.

We can get the prerequisite lower bound by noticing that $cn < paths_{n}(i,j) < qn^2$ for some fixed $c,q$. This gives us $G_{i,j} \leq O(1) T_{i,j}$ by Lemma 4.7.2. So $K_n \leq \sum T_{i,j} \leq n^2 T_n$ and this gives us the required lower bound.