0
$\begingroup$

Given a $d$-regular graph $G=(V,E)$ with $|V| =n$. We know that the smallest eigenvalue of the normalized laplacian matrix of $G$ is $0$. I have seen the formulation of the second smallest eigenvalue $\lambda_2$ in terms of the rayleigh quotient. However, the below paper mentions it in a way which I am not aware of.

How to derive the below (or similar) formulation of $\lambda_2$? Or am I horribly wrong in my interpretation?

$\lambda_2 = \min\limits_{\overline{v} \in \mathbb{R}^n, ||\overline{v}||=1} \dfrac{\mathbb{E}_{(u,v) \in E} ||\overline{u}-\overline{v}||^2}{\mathbb{E}_{u,v \in V} ||\overline{u}-\overline{v}||^2}$

Source : Proof of Theorem 7.1 (Section 7) of https://arxiv.org/pdf/1205.2234.pdf

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you explain the notation? What do the $\Bbb E$ stand for and what is the $\bar u$? $\endgroup$
    – M. Winter
    Mar 28, 2020 at 8:18
  • $\begingroup$ For each vertex $u \in V$, $\overline{u}$ is a vector of unit length in $\mathbb{R}^n$. $\endgroup$
    – avocado
    Mar 28, 2020 at 12:13
  • $\begingroup$ And $\mathbb{E}$ denotes the expectation. For eg, the numerator can be written of as, $\sum_{(u, v) \in E} 1/|E| \cdot ||\overline{u}-\overline{v}||^2$ and the denomiator as, $\sum_{u, v \in V} 1/|V|^2 \cdot ||\overline{u}-\overline{v}||^2$. $\endgroup$
    – avocado
    Mar 28, 2020 at 12:20
  • $\begingroup$ Then there is still something off. You cannot use $\bar v$ as a bound variable in the $\min$ and the sum (in the expectation value) at the same time. Also, which vector is $\bar u$ exactly? This seems not well defined to me. $\endgroup$
    – M. Winter
    Mar 28, 2020 at 15:28
  • $\begingroup$ I just checked the paper, and the formula there is different from what you wrote. First, the minimum is over all assignments of unit vectors to vertices (if I understand $\bar u$ as you explained). Second, the expectation value in the denominator is not over $V$ but over some other set $\mathcal P_1$ from some "bisection", whatever that means. $\endgroup$
    – M. Winter
    Mar 29, 2020 at 8:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.