Somas sobre produtos em caminhos curtos em um gráfico expansor

Aug 17 2020

Deixar$\Gamma=(V,E)$Seja um grafo não direcionado de grau$d$. (Dizer$d$é uma grande constante e o número de vértices$n=|V|$é muito maior.) Deixe$W_0$seja o espaço de funções$f:V\to \mathbb{C}$com média$0$. Presumir$\Gamma$é um gráfico expansor forte, o que significa que, para$A$o operador de adjacência$Af(w) = \sum_{\{w,v\}\in E} f(v)$do$\Gamma$restrito a$W_0$, todos os autovalores de$A$são consideravelmente menores do que$d$. Diga que eles são todos$\leq 2 \sqrt{d}$, ou seja, o grafo é basicamente um grafo de Ramanujan.

Então, por definição, para todo$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.$$É possível dar um limite superior não trivial para$$\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|?$$Assuma isso$f$tem valor real e$|f|_\infty=1$, se isso ajudar.

(Se sim: e as somas de produtos mais longos$f(v_1) f(v_2) \dotsc f(v_k)$, sobre$v_1,\dotsc,v_k\in V$de tal modo que$\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Presumir$k$limitado.

Se não: que tipo de hipótese auxiliar pode ajudar?)

Respostas

3 NarutakaOZAWA Aug 24 2020 at 04:34

Não sei seu objetivo, mas aqui está uma estimativa não muito precisa que funciona para qualquer$k$. Colocar$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$e$\gamma$ser a raiz positiva de$t^2-\rho t -\rho=0$. Um tem$\gamma<\sqrt{2\rho}<1$quando$\rho<\frac{1}{2}$. Então para qualquer$f$com$\sum f(v)=0$e$\|f\|_\infty\le1$, um tem$$\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. Por$D:=\mathrm{diag}\,f \in B(\ell_2V)$e$B:=\frac{1}{d}AD$, o LHS é$\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Com relação à decomposição ortogonal$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, um escreve$B$como uma matriz de operador$B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, Onde$\| b\|\le 1$,$\|c\|\le\rho$, e$\|d\|\le\rho$. daí para$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$com o autovalor$\gamma>0$e o autovetor$\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, um recebe$$\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.$$

Provavelmente vale a pena notar que a mesma 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)}.$$