एक विस्तारक ग्राफ में कम पथ पर उत्पादों पर रकम
लश्कर $\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$के सभी eigenvalues $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.$$ क्या एक 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|?$$ मान लो की $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$। किसी के पास$\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)}.$$