**Setting.** Let $G(n,p)$ denote the usual Erdős-Renyi (random) graphs. For each such graph there is an associated Laplacian matrix $L = D - A$ where $D$ collects the degrees on the diagonal and $A$ is the adjacency matrix. This matrix has eigenvectors $v_1, \dots v_n$ (ordered with respect to increasing eigenvalue) and we assume the eigenvectors are all normalized in $\ell^2(\mathbb{R}^n)$. 


----------


**Localization.** One natural question is whether any of these eigenvectors can be localized and this is often measured in the sense of $\| v_i\|_{\ell^{\infty}}$ being 'large', one entry being unusually big. One does not expect this to be the case and it's interesting to try to quantify this notion (and I think there are many papers about this). However, there is dual version: we know from Hölder that 
$$\| v_i\|_{\ell^1} \leq \sqrt{n} \cdot \|v\|_{\ell^2} = \sqrt{n}$$ 
with equality only attained for the flat vector. So the $\ell^1-$norm can also serve as a measure of localization: the more localized a vector is, the smaller it will be.
When I plot the value of $\|v_i\|_{\ell^1}$ for all the eigenvectors $i=1,2,\dots,n$, I get the following amusing curve.


[![][1]][1]

This picture shows $\|v_i\|_{\ell^1}$ for $i=1,\dots, 5000$ for a random realization of $G(n, p)$ for $n=5000$ and $p=0.4$. Knowing where in the spectrum an eigenvector lies seems to narrow down what its $\ell^1$-norm can be. There also seems to be a concentration phenomenon: the picture is pretty much the same for each random realization. Here's a second example for a random realization of $G(n, p)$ for $n=5000$ and $p=0.01$. 

[![][2]][2]

The eigenvectors corresponding to the smallest eigenvalues seem to be localized in vertices that have unusually few neighbors and eigenvectors corresponding to the largest eigenvectors seem to be localized in vertices having unusually many neighbors — thus one would perhaps some concentration in the edges and that would also explain why the curve is largest in the middle and symmetric. But I am surprised to see such a nice curve that seems to go **uniformly** through the entire spectrum.



**Question 1:** Is this known or does it follow from known results? Is there a good heuristic why this might be true?

Another interesting question is about the maximum of $\| v_i\|_{\ell^2}$ which seems to be assumed somewhere in the middle. 

**Question 2:** What can be said about
$$ 0 \leq \max_{1 \leq i \leq n}\frac{  \| v_i\|_{\ell^1}}{\sqrt{n}} \leq 1?$$
Numerically it seems to be somewhere around 0.8. If we assume that the entries of a typical flat eigenvector behave like i.i.d. Gaussians, then a first guess would be that this ratio should be somewhere around $\mathbb{E} |X|$ where $X \sim \mathcal{N}(0,1)$. We have  $\mathbb{E} |X| = \sqrt{2/\pi} \sim 0.79788$. Maybe a coincidence?

**Background:** A couple of years ago, Alex Cloninger and I played with the problem of trying to find structure in Laplacian eigenvectors. We found a method that worked pretty well in nice settings — we then tried to see what it would find on Erdős-Renyi random graphs (which seemed a natural test case: the eigenvectors should be mostly random and not particularly structured). Somehow our method picked out the edge and we didn't know why until we found this $\ell^1$ anomaly. It's mentioned in the paper ([arXiv][3]) but we never got a chance to ask a lot of people about it. 


  [1]: https://i.sstatic.net/exxyW.jpg
  [2]: https://i.sstatic.net/N1hIM.jpg
  [3]: https://arxiv.org/abs/1804.09816