ผลรวมของผลิตภัณฑ์ในเส้นทางสั้น ๆ ในกราฟตัวขยาย
ปล่อย $\Gamma=(V,E)$ เป็นกราฟองศาที่ไม่มีทิศทาง $d$. (พูด$d$ เป็นค่าคงที่ขนาดใหญ่และจำนวนจุดยอด $n=|V|$ มีขนาดใหญ่กว่ามาก) $W_0$ เป็นพื้นที่ของฟังก์ชัน $f:V\to \mathbb{C}$ ด้วยค่าเฉลี่ย $0$. สมมติ$\Gamma$ เป็นกราฟตัวขยายที่แข็งแกร่งซึ่งหมายความว่าสำหรับ $A$ ตัวดำเนินการ adjacency $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$. หนึ่งมี$\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$ และ eigenvector $\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)}.$$