Return to 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) = v(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?

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?

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) = v(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$ 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?

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) = v(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?