3
$\begingroup$

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with average $0$. Assume $\Gamma$ is a strong expander graph, meaning that, for $A$ the adjacency operator $Af(w) = \sum_{\{w,v\}\in E} f(v)$ of $\Gamma$ restricted to $W_0$, all the eigenvalues of $A$ are considerably smaller than $d$. Say they are all $\leq 2 \sqrt{d}$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for all $f\in W_0$ and $\sum_{v\in V} |f(v)|^2\leq n$, $$\left|\sum_{v_1,v_2\in V: \{v_1,v_2\}\in E} f(v_1) \overline{f(v_2)}\right| \leq 2\sqrt{d} \cdot n.$$ Is it possible to give a nontrivial upper bound on $$\left|\sum_{v_1,v_2,v_3\in V: \{v_1,v_2\},\{v_2,v_3\}\in E} f(v_1) f(v_2) f(v_3)\right|?$$ Assume that $f$ is real-valued and $|f|_\infty=1$, if it helps.

(If yes: what about sums of longer products $f(v_1) f(v_2) \dotsc f(v_k)$, over $v_1,\dotsc,v_k\in V$ such that $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assume $k$ bounded.

If no: what sort of auxiliary hypothesis might help?)

$\endgroup$
  • 2
    $\begingroup$ Let's begin with the trivial upper bound $$|\sum f(v_1)f(v_2)f(v_3)|=|\sum_{v_2} (Af)(v_2)f(v_2)(Af)(v_2)| \le \|f\|_\infty\|Af\|_2^2,$$ where $(Af)(v)=\sum_{w: \{w,v\}\in E}f(v)$. $\endgroup$ – Narutaka OZAWA Aug 18 at 3:00
3
$\begingroup$

I don't know your purpose, but here's some not-probably-sharp estimate that works for any $k$. Put $\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ and $\gamma$ to be the positive root of $t^2-\rho t -\rho=0$. One has $\gamma<\sqrt{2\rho}<1$ when $\rho<\frac{1}{2}$. Then for any $f$ with $\sum f(v)=0$ and $\|f\|_\infty\le1$, one has $$\frac{1}{|V|\cdot d^{k-1}}\left|\sum_{v_1,v_2,\ldots,v_k : \{v_i,v_{i+1}\}\in E} f(v_1)\cdots f(v_k)\right| \le \gamma^k.$$

Proof. For $D:=\mathrm{diag}\,f \in B(\ell_2V)$ and $B:=\frac{1}{d}AD$, the LHS is $\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. With respect to the orthogonal decomposition $\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, one writes $B$ as an operator matrix $B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, where $\| b\|\le 1$, $\|c\|\le\rho$, and $\|d\|\le\rho$. Hence for $C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$ with the eigenvalue $\gamma>0$ and the eigenvector $\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, one gets $$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle| \le \left[\begin{smallmatrix} 0 & 1 \end{smallmatrix}\right] C^{k-1} \left[\begin{smallmatrix} 1 \\ 0 \end{smallmatrix}\right] \le \left[\begin{smallmatrix} 0 & 1 \end{smallmatrix}\right] C^{k-1} \left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]=\gamma^k.$$

It's probably worth noting that the same proof shows $$\frac{1}{|V|}\sum_{v_1\in V}\left|\frac{1}{d^{k-1}}\sum_{v_2,\ldots,v_k : \{v_i,v_{i+1}\}\in E} f_1(v_1)\cdots f_k(v_k)\right|^2 \le 2\gamma^{2(k-1)}.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.