Return to Answer

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

Added in edit: I realize that I was writing about a matrix with independent centered entries; the Laplacian matrix does not fall in that framework, although its no gap delocalization is treated (with weaker bounds) in Eldan et als work, reference 9 in the cited paper of Rudelson-Vershunin. In particular, for $p\in (0,1)$ independent of $n$, it shows that for the second eigenvector, the $l_1$ norm is bounded below by $\sqrt{n}/(\log n)^C$. I suspect their method works for other eigenvectors.

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

Added in edit: I realize that I was writing about a matrix with independent centered entries; the Laplacian matrix does not fall in that framework, although the no gap delocalization for the normalized Laplacian is treated (with weaker bounds) in Eldan et als work, reference 9 in the cited paper of Rudelson-Vershynin. In particular, for $p\in (0,1)$ independent of $n$, it shows that for the second eigenvector (and some other near the edge), the $l_1$ norm is bounded below by $\sqrt{n}/(\log n)^C$. I suspect their method works for other eigenvectors.

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

Added in edit: I realize that I was writing about a matrix with independent centered entries; the Laplacian matrix does not fall in that framework, although its no gap delocalization is treated (with weaker bounds) in Eldan's work, reference 9 in the cited paper of Rudelson-Vershunin.

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

Added in edit: I realize that I was writing about a matrix with independent centered entries; the Laplacian matrix does not fall in that framework, although its no gap delocalization is treated (with weaker bounds) in Eldan et als work, reference 9 in the cited paper of Rudelson-Vershunin. In particular, for $p\in (0,1)$ independent of $n$, it shows that for the second eigenvector, the $l_1$ norm is bounded below by $\sqrt{n}/(\log n)^C$. I suspect their method works for other eigenvectors.

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

The following does not decide on whether the infimum is $0$, but it does give a rough bound.

Let $v$ be a normalized eigenvector. Suppose $\|v\|_1<n^{\alpha}$ for some $\alpha<1/2$. Let $I=\{i: |v_i|<n^{-\beta}\}$ with $\beta>\alpha$ t.b.d. By the no-gap delocalization property of Rudelson-Vershynin (see https://arxiv.org/pdf/1506.04012.pdf), with high probability, for al such vectors, $$C(|I|/n)^{12}\leq \sum_{i\in I} |v_i|^2\leq n^{-\beta} \sum_{i\in I} |v_i|\leq n^{\alpha-\beta}.$$ (I am simplifying a bit, out of laziness; in reality you have to make sure $I$ is not too small, but the argument still goes through. See the difference between Theorem 1.3 and 1.5 there.) Therefore, $$|I|\leq n\cdot (n^{(\alpha-\beta)})^{1/12}.$$ Thus, if $\alpha<\beta$ then $|I|/n\to 0$. That is, the cardinality of the set of coordinates larger than $n^{-\beta}$ is larger than (say) $n/2$. But then, $$n^{\alpha}\geq \sum_i |v_i|\geq \sum_{i\notin I} |v_i|\geq n^{1-\beta}/2.$$ Thus, we get that $\alpha\geq 1-\beta$. Since $\beta$ is arbitrary subject to the constraint $\beta>\alpha$, it follows that $\alpha>1/2$, which contradicts $\alpha<1/2$.

Added in edit: I realize that I was writing about a matrix with independent centered entries; the Laplacian matrix does not fall in that framework, although its no gap delocalization is treated (with weaker bounds) in Eldan's work, reference 9 in the cited paper of Rudelson-Vershunin.