From one eigenvector to many, in a very local graph?

Question

Let $\Gamma$ be an undirected graph of bounded degree $d$ with $V = \{1,2,\dotsc,N\}$ as its set of vertices, and edges only between vertices that are at a distance $\leq M$ apart (where $M$ is much smaller than $N$). Let $\Delta$ be the graph Laplacian of $\Gamma$.

Define an inner product on functions $V\to \mathbb{C}$ by giving to $V$ the uniform probability measure, i.e., each vertex has measure $1/N$.

Let $f:V\to \mathbb{C}$ be such that $|f|_2^2=1$ and $\eta = |\langle f,\Delta f\rangle|$ is large. (For instance, $f$ could be an eigenvector with large eigenvalue.)

(a) If $|f(n)|=1$ for all $n$, then it follows easily that there is a large number of orthonormal vectors $w:V\to \mathbb{C}$ with $|\langle w, \Delta w\rangle|$ large: just take all $w$ of the form $w(n) = w_a(n) = f(n) e(a n/N)$ for $|a| \leq \eta N/10 M$, say.

(b) Under the weaker assumption that $|f(n)|\geq \epsilon$ for at least $\epsilon N$ elements $n\in V$, one can very likely obtain a similar conclusion. Here's a clumsy way: chop up $V$ into disjoint neighborhoods of size $100 M/\epsilon$ or so; then, for any neighborhood $U$ that is not too "poor" and does not have neighbors that are too "rich", it should be the case that $\langle w, \Delta w\rangle$ is large for the restriction $w=f|_U$. Is there a more elegant argument (perhaps along the lines of (a))?

(c) Somewhat orthogonal question: if no functions $f:V\to \mathbb{C}$ with $|f|_2^2=1$ and $\eta=\left|\langle f,\Delta f\rangle\right|$ large satisfy $|f(n)|\geq \epsilon$ for at least $\epsilon N$ elements $n\in V$, does it follow that there is a small subset $Y\subset V$ (with $|Y| = O(\epsilon N)$ elements, say) such that $\Delta|_{V\setminus Y}$ (defined as the operator $f\mapsto (\Delta f_{V\setminus Y})_{V\setminus Y}$) has no large eigenvalues? (Alternatively: if there are several functions $f_i:V\to \mathbb{C}$ with $|f_i|_2^2=1$ and $|\langle f,\Delta f\rangle|$ large such that, for many $n$, there is some $f_i$ such that $|f_i(n)|\geq \epsilon$, can we proceed as in (b) and obtain a large number of orthonormal $w$ such that $|\langle w, \Delta w\rangle|$ is large?

Answer 1

Let me show how to do (b), in a more general context than I set out in (b).

Let $f:V\to \mathbb{C}$ with $|f|_2=1$ and $|\langle f, \Delta f\rangle|\geq \alpha>0$.

Consider a partition of $V$ inducing an equivalence relation $\sim$. Define the linear operator $\Delta_\sim$ on functions $v:V\to \mathbb{C}$ by $$(\Delta_\sim v)(n) = v(n) - \frac{1}{d} \mathop{\sum_{n': \{n,n'\}\in E}}_{n'\sim n} v(n').$$ The graph Laplacian $\Delta$ thus equals $\Delta_\sim$ for $\sim$ corresponding to the trivial partition.

Clearly $$\begin{aligned}\left|\langle f, (\Delta_\sim-\Delta) f\rangle\right| &= \left|\frac{1}{d} \sum_n v(n) \mathop{\sum_{n': \{n,n'\}\in E}}_{n'\not\sim n} v(n')\right|\leq \frac{1}{d} \sum_n \mathop{\sum_{n': \{n,n'\}\in E}}_{n'\not\sim n} \frac{|v(n)|^2 + |v(n')|^2}{2} \\ &= \frac{1}{d} \sum_n \mathop{\sum_{n': \{n,n'\}\in E}}_{n'\not\sim n} |v(n)|^2 \leq \sum_{n\in \partial_\sim} |v(n)|^2,\end{aligned}$$ where $\partial_\sim\subset V$ is the set of all $n$ such that $n'\sim n$ for some edge $\{n,n'\}\in E$.

Consider partitions of $V$ into segments of the form $$\{1,2,\dotsc,a M\}, \{a M + 1,\dotsc, (a + 2 C M)\},\dotsc, \{a + 2 C k M+1,\dotsc, N\},\;\;\;\;\;\;\;\;\;\;(*)$$ with all segments being of length $2 C M$ (except possibly for the first and the last one, which may be shorter). In fact, consider such partitions only for $a=1,3,\dotsc, 2 C - 1$. For the corresponding equivalence relation $\sim_a$, $$\delta_{\sim_a} \subset \delta_a := \bigcup_{j=0}^{k}\; \{(2 C j + a-1) M + 1, (2 C j + a-1) M +2,\dotsc, (2 C (j+1) + a) M\}, $$ since all of our edges are of length $\leq M$. It is clear that $\delta_1,\delta_3,\dotsc,\delta_{2 C - 1}$ are disjoint. Hence, by pigeonhole, there is an $a\in \{1,3,\dotsc,2 C - 1\}$ such that $\sum_{n\in \delta_a} |v(n)|^2 \leq 1/C$. We choose that $a$ and work with the corresponding partition (*). Then $|\langle f,\Delta_\sim f\rangle|\geq (\alpha - 1/C)$. Let $C = \lceil 3/\alpha\rceil$, so that $|\langle f,\Delta_\sim f\rangle|\geq 2 \alpha/3$. Write $P=\{I\}$ for our partition into intervals $I$.

Let $S$ be the set of intervals $I\in P$ such that $|\langle f|_I,\Delta f|_I\rangle| \geq \frac{\alpha}{3} \left| f|_I\right|_2^2$. It is clear that $$\sum_{I\in P\setminus S} |\langle f|_I,\Delta f|_I\rangle| < \frac{\alpha}{3} \sum_{I\in P\setminus S} \left| f|_I \right|_2 \leq \frac{\alpha}{3} \sum_n |f(n)|^2 = \frac{\alpha}{3}$$ and so $\sum_{I\in S} |\langle f|_I,\Delta f|_I\rangle| > \alpha/3$. It remains to bound the size of $S$ from below.

Assume $|f|_\infty\leq K$. Since the $L^2\to L^2$ operator norm of $\Delta$ is $\leq 2$, we see that, for every $I\in S$, $$|\langle f|_I,\Delta f|_I\rangle| \leq 2 \left|f|_I\right|_2^2 \leq 2 K^2 \cdot \frac{2 C M}{N} \ll \frac{K^2}{\alpha} \frac{M}{N}.$$ Hence $$|S| \gg \frac{\alpha^2}{K^2} \frac{N}{M}.$$

Answer 2

Here is my self-answer to (c), based on my self-answer to (b).

For any $f:V\to \mathbb{C}$ with $|f|_2^2=1$ and $|\langle f,\Delta f\rangle|\geq \alpha>0$, we obtain, proceeding as in my self-answer to (b), that there is an interval of the form $$I = \{(2m-1)M + 1, (2m-1) M +2, \dotsc, (2m-1) M + 2 C M\}\cap [1,N]$$ such that $\left|\langle f|_I,\Delta f|_I\rangle\right|\geq \frac{\alpha}{2} \left| f|_I\right|_2^2$, where $C = \lceil 2/\alpha\rceil$.

Let $Y$ be the union of the set $\mathbf{I}$ of all such intervals for all such functions $f$. Then, for any function $f$ with $|f|_2^2=1$ and support on $V\setminus Y$, we know that $|\langle f,\Delta f\rangle|<\alpha$ (or else we would get a contradiction).

It is easy to see that we can choose a subset $\mathbf{I}'\subset \mathbf{I}$ consisting of $|\mathbf{I}'|\geq |Y|/4 C M$ disjoint intervals. For each $I\in \mathbf{I}'$, there exists, by construction, a function $g$ supported on $I$ with $|g|_2^2=1$ and $|\langle g,\Delta g\rangle|\geq \alpha/2$. Functions $g$ corresponding to different $I\in \mathbf{I}'$ are obviously orthogonal to each other.

Thus, for any $\epsilon>0$, we know that either $|Y|\leq \epsilon N$, or there are $\gg \epsilon \alpha N/M$ orthogonal functions $g$ with $|g|_2^2=1$ and $|\langle g,\Delta g\rangle| \geq \alpha/2$.