확장 그래프에서 짧은 경로의 제품 합계

Question

허락하다 $\Gamma=(V,E)$ 방향이없는 정도의 그래프 $d$. (말하다$d$ 큰 상수이고 정점의 수 $n=|V|$ 훨씬 큽니다.) $W_0$ 기능의 공간 $f:V\to \mathbb{C}$ 평균으로 $0$. 취하다$\Gamma$ 강력한 확장 그래프입니다. 즉, $A$ 인접 연산자 $Af(w) = \sum_{\{w,v\}\in E} f(v)$ 의 $\Gamma$ 제한 $W_0$, 모든 고유 값 $A$ 보다 상당히 작습니다 $d$. 모두라고$\leq 2 \sqrt{d}$즉, 그래프는 기본적으로 Ramanujan 그래프입니다.

그런 다음 정의에 따라 $f\in W_0$ 과 $\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.$$ 사소하지 않은 상한선을 지정할 수 있습니까? $$\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|?$$ 그것을 가정 $f$ 실제 가치이며 $|f|_\infty=1$, 도움이되는 경우.

(있는 경우 : 더 긴 제품의 합계는 어떻습니까? $f(v_1) f(v_2) \dotsc f(v_k)$, 이상 $v_1,\dotsc,v_k\in V$ 그런 $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? 취하다$k$ 경계.

그렇지 않다면 : 어떤 종류의 보조 가설이 도움이 될 수 있습니까?)

Answer 1

나는 당신의 목적을 모르지만, 여기에 어느 누구에게나 효과가있을 것 같지 않은 예리한 추정치가 있습니다. $k$. 놓다$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ 과 $\gamma$ 의 긍정적 인 뿌리 $t^2-\rho t -\rho=0$. 하나는$\gamma<\sqrt{2\rho}<1$ 언제 $\rho<\frac{1}{2}$. 그런 다음$f$ 와 $\sum f(v)=0$ 과 $\|f\|_\infty\le1$, 하나는 $$\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.$$

증명. 에 대한$D:=\mathrm{diag}\,f \in B(\ell_2V)$ 과 $B:=\frac{1}{d}AD$, LHS는 $\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. 직교 분해와 관련하여$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, 하나는 쓴다 $B$ 연산자 행렬로 $B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, 어디 $\| b\|\le 1$, $\|c\|\le\rho$, 및 $\|d\|\le\rho$. 따라서$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$ 고유 값으로 $\gamma>0$ 및 고유 벡터 $\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, 하나는 $$\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.$$

동일한 증거가 $$\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)}.$$