Skip to main content
edited tags
Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126
added 15 characters in body
Source Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with average $0$. Assume $\Gamma$ is a strong expander graph, meaning that, for $A$ the adjacency operator $Af(w) = \sum_{\{w,v\}\in E} f(v)$ of $\Gamma$ restricted to $W_0$, all the eigenvalues of $A$ are considerably smaller than $d$. Say they are all $\leq 2 \sqrt{d}$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for all $f\in W_0$ and $\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.$$ Can one sayIs it possible to give a nontrivial upper bound on $$\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|?$$ Assume that $f$ is real-valued and $|f|_\infty=1$, if it helps.

(If yes: what about sums of longer products $f(v_1) f(v_2) \dotsc f(v_k)$, over $v_1,\dotsc,v_k\in V$ such that $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assume $k$ bounded.

If no: what sort of auxiliary hypothesis might help?)

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with average $0$. Assume $\Gamma$ is a strong expander graph, meaning that, for $A$ the adjacency operator $Af(w) = \sum_{\{w,v\}\in E} f(v)$ of $\Gamma$ restricted to $W_0$, all the eigenvalues of $A$ are considerably smaller than $d$. Say they are all $\leq 2 \sqrt{d}$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for $f\in W_0$ and $\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.$$ Can one say a nontrivial upper bound on $$\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|?$$ Assume that $f$ is real-valued and $|f|_\infty=1$, if it helps.

(If yes: what about sums of longer products $f(v_1) f(v_2) \dotsc f(v_k)$, over $v_1,\dotsc,v_k\in V$ such that $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assume $k$ bounded.

If no: what sort of auxiliary hypothesis might help?)

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with average $0$. Assume $\Gamma$ is a strong expander graph, meaning that, for $A$ the adjacency operator $Af(w) = \sum_{\{w,v\}\in E} f(v)$ of $\Gamma$ restricted to $W_0$, all the eigenvalues of $A$ are considerably smaller than $d$. Say they are all $\leq 2 \sqrt{d}$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for all $f\in W_0$ and $\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.$$ Is it possible to give a nontrivial upper bound on $$\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|?$$ Assume that $f$ is real-valued and $|f|_\infty=1$, if it helps.

(If yes: what about sums of longer products $f(v_1) f(v_2) \dotsc f(v_k)$, over $v_1,\dotsc,v_k\in V$ such that $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assume $k$ bounded.

If no: what sort of auxiliary hypothesis might help?)

Source Link
H A Helfgott
  • 20.2k
  • 3
  • 43
  • 126

Sums over products over short paths in an expander graph

Let $\Gamma=(V,E)$ be an undirected graph of degree $d$. (Say $d$ is a large constant and the number of vertices $n=|V|$ is much larger.) Let $W_0$ be the space of functions $f:V\to \mathbb{C}$ with average $0$. Assume $\Gamma$ is a strong expander graph, meaning that, for $A$ the adjacency operator $Af(w) = \sum_{\{w,v\}\in E} f(v)$ of $\Gamma$ restricted to $W_0$, all the eigenvalues of $A$ are considerably smaller than $d$. Say they are all $\leq 2 \sqrt{d}$, i.e., the graph is basically a Ramanujan graph.

Then, by definition, for $f\in W_0$ and $\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.$$ Can one say a nontrivial upper bound on $$\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|?$$ Assume that $f$ is real-valued and $|f|_\infty=1$, if it helps.

(If yes: what about sums of longer products $f(v_1) f(v_2) \dotsc f(v_k)$, over $v_1,\dotsc,v_k\in V$ such that $\{v_1,v_2\},\dotsc,\{v_{k-1},v_k\}\in E$? Assume $k$ bounded.

If no: what sort of auxiliary hypothesis might help?)