Суммирует продукты по коротким путям в расширительном графе
Позволять $\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$. Надо$\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)}.$$