Sommes sur les produits sur des chemins courts dans un graphique d'expansion
Laisser$\Gamma=(V,E)$être un graphe non orienté de degré$d$. (Dire$d$est une grande constante et le nombre de sommets$n=|V|$est beaucoup plus grand.) Soit$W_0$être l'espace des fonctions$f:V\to \mathbb{C}$avec moyenne$0$. Présumer$\Gamma$est un graphe d'expansion fort, ce qui signifie que, pour$A$l'opérateur d'adjacence$Af(w) = \sum_{\{w,v\}\in E} f(v)$de$\Gamma$limité à$W_0$, toutes les valeurs propres de$A$sont considérablement plus petits que$d$. Dis qu'ils sont tous$\leq 2 \sqrt{d}$, c'est-à-dire que le graphe est fondamentalement un graphe de Ramanujan.
Alors, par définition, pour tout$f\in W_0$et$\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.$$Est-il possible de donner une borne supérieure non triviale sur$$\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|?$$Suppose que$f$est à valeur réelle et$|f|_\infty=1$, si ça aide.
(Si oui : qu'en est-il des sommes de produits plus longs ?$f(v_1) f(v_2) \dotsc f(v_k)$, plus de$v_1,\dotsc,v_k\in V$tel que$\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Présumer$k$délimité.
Si non : quel type d'hypothèse auxiliaire pourrait aider ?)
Réponses
Je ne connais pas votre objectif, mais voici une estimation peu précise qui fonctionne pour n'importe quel$k$. Mettre$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$et$\gamma$être la racine positive de$t^2-\rho t -\rho=0$. L'un a$\gamma<\sqrt{2\rho}<1$lorsque$\rho<\frac{1}{2}$. Alors pour tout$f$avec$\sum f(v)=0$et$\|f\|_\infty\le1$, on a$$\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.$$
Preuve. Pour$D:=\mathrm{diag}\,f \in B(\ell_2V)$et$B:=\frac{1}{d}AD$, le LHS est$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Par rapport à la décomposition orthogonale$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, on écrit$B$en tant que matrice d'opérateurs$B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, où$\| b\|\le 1$,$\|c\|\le\rho$, et$\|d\|\le\rho$. Donc pour$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$avec la valeur propre$\gamma>0$et le vecteur propre$\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, on obtient$$\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.$$
Il est probablement intéressant de noter que la même preuve montre$$\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)}.$$