拡張グラフの短いパスでの製品の合計
しましょう $\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}$つまり、グラフは基本的にラマヌジャングラフです。
次に、定義上、すべての人にとって $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$ 跳ねる。
いいえの場合：どのような補助仮説が役立つ可能性がありますか？）
回答
私はあなたの目的を知りませんが、ここにいくつかのおそらく鋭くない見積もりがあります $k$。プット$\rho=\frac{1}{d}\|A|_{({\mathbb C}1)^\perp}\|$ そして $\gamma$ の正のルートになる $t^2-\rho t -\rho=0$。1つは持っています$\gamma<\sqrt{2\rho}<1$ いつ $\rho<\frac{1}{2}$。その後、任意の$f$ と $\sum f(v)=0$ そして $\|f\|_\infty\le1$、1つは $$\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$、1つ書く $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]$、1つが取得します $$\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)}.$$