Somme su prodotti su percorsi brevi in un grafico espansore
Permettere$\Gamma=(V,E)$essere un grafico non orientato di grado$d$. (Dire$d$è una grande costante e il numero di vertici$n=|V|$è molto più grande.) Let$W_0$essere lo spazio delle funzioni$f:V\to \mathbb{C}$con la media$0$. Assumere$\Gamma$è un forte grafico di espansione, il che significa che, per$A$l'operatore di adiacenza$Af(w) = \sum_{\{w,v\}\in E} f(v)$di$\Gamma$limitato a$W_0$, tutti gli autovalori di$A$sono notevolmente più piccoli di$d$. Diciamo che sono tutti$\leq 2 \sqrt{d}$, cioè, il grafico è fondamentalmente un grafico di Ramanujan.
Quindi, per definizione, per tutti$f\in W_0$e$\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.$$È possibile dare un limite superiore non banale$$\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|?$$Supponiamo che$f$è a valore reale e$|f|_\infty=1$, se aiuta.
(Se sì: per quanto riguarda le somme di prodotti più lunghi$f(v_1) f(v_2) \dotsc f(v_k)$, Sopra$v_1,\dotsc,v_k\in V$tale che$\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assumere$k$delimitato.
Se no: che tipo di ipotesi ausiliaria potrebbe aiutare?)
Risposte
Non conosco il tuo scopo, ma ecco una stima non probabilmente precisa che funziona per chiunque$k$. Mettere$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$e$\gamma$essere la radice positiva di$t^2-\rho t -\rho=0$. Uno ha$\gamma<\sqrt{2\rho}<1$quando$\rho<\frac{1}{2}$. Quindi per qualsiasi$f$insieme a$\sum f(v)=0$e$\|f\|_\infty\le1$, uno ha$$\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.$$
Prova. Per$D:=\mathrm{diag}\,f \in B(\ell_2V)$e$B:=\frac{1}{d}AD$, l'LHS è$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Rispetto alla scomposizione ortogonale$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, scrive uno$B$come matrice di operatori$B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, dove$\| b\|\le 1$,$\|c\|\le\rho$, e$\|d\|\le\rho$. Quindi per$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$con l'autovalore$\gamma>0$e l'autovettore$\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, si ottiene$$\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.$$
Probabilmente vale la pena notare che la stessa prova mostra$$\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)}.$$