Sumas sobre productos sobre caminos cortos en un gráfico de expansión

Aug 17 2020

Dejar$\Gamma=(V,E)$ser un grafo no dirigido de grado$d$. (Decir$d$es una constante grande y el número de vértices$n=|V|$es mucho más grande.) Deje$W_0$ser el espacio de funciones$f:V\to \mathbb{C}$con promedio$0$. Asumir$\Gamma$es un gráfico de expansión fuerte, lo que significa que, para$A$el operador de adyacencia$Af(w) = \sum_{\{w,v\}\in E} f(v)$de$\Gamma$prohibido para$W_0$, todos los valores propios de$A$son considerablemente más pequeños que$d$. Di que son todos$\leq 2 \sqrt{d}$, es decir, el gráfico es básicamente un gráfico de Ramanujan.

Entonces, por definición, para todo$f\in W_0$y$\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.$$¿Es posible dar un límite superior no trivial en$$\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|?$$Asumir que$f$es de valor real y$|f|_\infty=1$, si ayuda.

(En caso afirmativo: ¿qué pasa con las sumas de productos más largos$f(v_1) f(v_2) \dotsc f(v_k)$, sobre$v_1,\dotsc,v_k\in V$tal que$\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Asumir$k$encerrado.

Si no: ¿qué tipo de hipótesis auxiliar podría ayudar?)

Respuestas

3 NarutakaOZAWA Aug 24 2020 at 04:34

No conozco su propósito, pero aquí hay una estimación no muy precisa que funciona para cualquier$k$. Poner$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$y$\gamma$ser la raíz positiva de$t^2-\rho t -\rho=0$. Uno tiene$\gamma<\sqrt{2\rho}<1$cuando$\rho<\frac{1}{2}$. Entonces para cualquier$f$con$\sum f(v)=0$y$\|f\|_\infty\le1$, uno tiene$$\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.$$

Prueba. Para$D:=\mathrm{diag}\,f \in B(\ell_2V)$y$B:=\frac{1}{d}AD$, el lado izquierdo es$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Con respecto a la descomposición ortogonal$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, uno escribe$B$como matriz de operadores$B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, dónde$\| b\|\le 1$,$\|c\|\le\rho$, y$\|d\|\le\rho$. Por lo tanto para$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$con el valor propio$\gamma>0$y el vector propio$\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, uno obtiene$$\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.$$

Probablemente valga la pena señalar que la misma prueba muestra$$\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)}.$$