Menjumlahkan produk melalui jalur pendek dalam grafik pembentang
Membiarkan $\Gamma=(V,E)$ menjadi grafik derajat yang tidak berarah $d$. (Mengatakan$d$ adalah konstanta besar dan jumlah simpul $n=|V|$ jauh lebih besar.) Mari $W_0$ menjadi ruang fungsi $f:V\to \mathbb{C}$ dengan rata-rata $0$. Menganggap$\Gamma$ adalah grafik pembentang yang kuat, artinya, untuk $A$ operator kedekatan $Af(w) = \sum_{\{w,v\}\in E} f(v)$ dari $\Gamma$ terlarang untuk $W_0$, semua nilai eigen $A$ jauh lebih kecil dari $d$. Katakanlah mereka semua$\leq 2 \sqrt{d}$, yaitu grafik pada dasarnya adalah grafik Ramanujan.
Kemudian, menurut definisi, untuk semua $f\in W_0$ dan $\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.$$ Apakah mungkin untuk memberikan batas atas nontrivial $$\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|?$$ Asumsikan bahwa $f$ bernilai nyata dan $|f|_\infty=1$, jika itu membantu.
(Jika ya: bagaimana dengan jumlah produk yang lebih panjang $f(v_1) f(v_2) \dotsc f(v_k)$, lebih $v_1,\dotsc,v_k\in V$ seperti yang $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Menganggap$k$ dibatasi.
Jika tidak: hipotesis tambahan seperti apa yang dapat membantu?)
Jawaban
Saya tidak tahu tujuan Anda, tapi berikut beberapa perkiraan yang tidak-mungkin-tajam yang berhasil untuk semua orang $k$. Taruh$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ dan $\gamma$ menjadi akar positif dari $t^2-\rho t -\rho=0$. Satu memiliki$\gamma<\sqrt{2\rho}<1$ kapan $\rho<\frac{1}{2}$. Lalu untuk apa saja$f$ dengan $\sum f(v)=0$ dan $\|f\|_\infty\le1$, satu punya $$\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.$$
Bukti. Untuk$D:=\mathrm{diag}\,f \in B(\ell_2V)$ dan $B:=\frac{1}{d}AD$, LHS adalah $\frac{1}{|V|}|\langle B^{k-1}1_V,f\rangle|$. Berkenaan dengan dekomposisi ortogonal$\ell_2V={\mathbb C}1_V\oplus ({\mathbb C}1_V)^\perp$, salah satunya menulis $B$ sebagai matriks operator $B=\left[\begin{smallmatrix} 0 & b \\ c & d \end{smallmatrix}\right]$, dimana $\| b\|\le 1$, $\|c\|\le\rho$, dan $\|d\|\le\rho$. Oleh karena itu untuk$C:=\left[\begin{smallmatrix} 0 & 1 \\ \rho & \rho \end{smallmatrix}\right] \in M_2({\mathbb R})$ dengan nilai eigen $\gamma>0$ dan vektor eigen $\left[\begin{smallmatrix} 1 \\ \gamma \end{smallmatrix}\right]$, satu dapat $$\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.$$
Mungkin perlu dicatat bahwa bukti yang sama menunjukkan $$\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)}.$$