Genişletici bir grafikte kısa yollar üzerinden ürünlerin toplamları

Question

İzin Vermek $\Gamma=(V,E)$ yönsüz bir derece grafiği olmak $d$. (Söyle$d$ büyük bir sabittir ve köşe sayısıdır $n=|V|$ çok daha büyüktür.) $W_0$ fonksiyon alanı olmak $f:V\to \mathbb{C}$ ortalama ile $0$. Varsaymak$\Gamma$ güçlü bir genişletici grafiktir, yani $A$ bitişiklik operatörü $Af(w) = \sum_{\{w,v\}\in E} f(v)$ nın-nin $\Gamma$ sınırlı $W_0$, tüm özdeğerleri $A$ daha küçük $d$. Onların hepsi olduğunu söyle$\leq 2 \sqrt{d}$yani grafik temelde bir Ramanujan grafiğidir.

Sonra, tanımı gereği herkes için $f\in W_0$ ve $\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.$$ Önemsiz bir üst sınır vermek mümkün mü $$\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|?$$ Varsayalım ki $f$ gerçek değerlidir ve $|f|_\infty=1$, eğer yardımı dokunursa.

(Evet ise: daha uzun ürünlerin toplamları ne olacak? $f(v_1) f(v_2) \dotsc f(v_k)$, bitmiş $v_1,\dotsc,v_k\in V$ öyle ki $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Varsaymak$k$ sınırlı.

Hayır ise: ne tür yardımcı hipotezler yardımcı olabilir?)

Answer 1

Amacınızı bilmiyorum, ancak işte muhtemelen kesin olmayan bazı tahminler $k$. Koymak$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ ve $\gamma$ pozitif kökü olmak $t^2-\rho t -\rho=0$. Birinde var$\gamma<\sqrt{2\rho}<1$ ne zaman $\rho<\frac{1}{2}$. O zaman herhangi biri için$f$ ile $\sum f(v)=0$ ve $\|f\|_\infty\le1$, birinde var $$\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.$$

Kanıt. İçin$D:=\mathrm{diag}\,f \in B(\ell_2V)$ ve $B:=\frac{1}{d}AD$, LHS $\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Ortogonal ayrışma ile ilgili olarak$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, biri yazıyor $B$ operatör matrisi olarak $B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, nerede $\| b\|\le 1$, $\|c\|\le\rho$, ve $\|d\|\le\rho$. Dolayısıyla$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$ özdeğer ile $\gamma>0$ ve özvektör $\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, biri alır $$\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.$$

Muhtemelen aynı kanıtın $$\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)}.$$