Arbitrary-dimensional expanders?

Question

---

Rephrasing expansion (slightly). Consider the following slightly tweaked version of the usual definition of a (spectral) expander graph.

(We write a weighted graph as $(V,\beta)$, where the weight $\beta$ is a real-valued function on two-element subsets of $V$. The adjacency operator of a weighted graph is defined in the usual way.)

A weighted graph $\Gamma=(V,\beta)$ is an weighted $\eta$-expander if the ($L^2$-to-$L^2$) operator norm of $\textrm{Ad}_\Gamma$ is $\leq \eta$.

... or, what is the same, if all the eigenvalues of $\textrm{Ad}_\Gamma$ have absolute value of $\leq \epsilon$. Or, equivalently, if, for all $f,g:V\to \mathbb{C}$, $$|\langle f,\textrm{Ad}_\Gamma g\rangle|\leq \eta |f|_2 |g|_2.$$

The usual definition of expander graph corresponds to this definition as follows: a regular graph $\Gamma$ of degree $D$ on $N$ vertices is a $\delta$-expander graph (that is, it has a spectral gap $\delta$) if, for $\frac{D}{N-1} K_N$ the complete graph with weight $\frac{D}{N-1}$ on every edge, the weighted graph $$\Gamma-\frac{D}{N-1} K_N$$ is a weighted $D (1-\delta)$-expander.

(The weighted version of the definition has several advantages, not the least one being that it works for non-regular graphs; it also works for graphs that have a "naïve model" that is not the complete graph.)

An alternative, weaker definition would just require that $$|\langle f,\textrm{Ad}_{\Gamma} g\rangle|\leq \eta$$ for all $f,g:V\to \mathbb{C}$ with $|f|_\infty, |g|_\infty\leq 1$. That is enough to imply combinatorial expansion "for large sets", and so it also implies topological and geometric expansion (for dimension $1$) in the sense of Gromov.

Instead of writing $\langle f,\textrm{Ad}_\Gamma g\rangle$, we can use the following notation: we define $\Lambda_\Gamma$ to be a linear function that maps a pair $(f,g)$ of functions $f,g:V\to \mathbb{R}$ to the number $\sum_{\{v_0,v_1\}\in E} \beta(\{v_0,v_1\})f(v_0) f(v_1)$. Then we want $|\Lambda_{\Gamma}(f,g)|\leq \eta$ whenever $|f|_2,|g|_2\leq 1$, or whenever $|f|_\infty,|g|_\infty\leq 1$.

---

Expansion in higher dimensions. Now let me try to generalize this definition to higher dimensions, in a way that is loosely inspired by Gromov's definition of higher-dimensional topological expanders and geometric expanders (which I learned about from Tali Kaufman's ICM talk, and can also be found in, say, Lubotzky's survey from the 2018 ICM, https://eta.impa.br/dl/PL002.pdf section 3.1), at least at the level of language; it is also motivated by applications.

For an abstract simplicial complex $X$, we denote by $X^{(d)}$ its set of $d$-dimensional simplices. For $f_0,f_1,\dotsc,f_d:V\to \mathbb{R}$ and $\beta:X^{(d)}\to \mathbb{R}$, let $$\Lambda_{X^{(d)}}(f_0,f_1,\dotsc,f_d) = \sum_{\{v_0,v_1,\dotsc,v_d\}\in X^{(d)}} \beta(\{v_0,v_1,\dotsc,v_d\}) f_0(v_0) f_1(v_1)\dotsb f_d(v_d).$$

An abstract simplicial complex $X$ with a weight function $\beta:X^{(d)}\to \mathbb{R}$ is a weighted $\eta$-expander in dimension $d$ if, for all $f_0,f_1,\dotsc,f_d:V\to \mathbb{R}$ with $|f_0|_\infty,\dotsc,|f_d|_{\infty}\leq 1$, $$|\Lambda_{X^{(d)}}(f_0,\dotsc,f_d)|\leq \eta.$$

Of course this property is interesting when $\eta$ is small compared to $$W_{X^{(d)}} = \left|\sum_{\{v_0,\dotsc,v_d\}\in X^{(d)}} \beta(\{v_0,\dotsc,v_d\})\right|.$$

Questions:

• How does this definition relate to existing definitions of high-dimensional expanders? Is a weighted $\eta$-expander with $\eta\leq \frac{1}{2} W_{X^{(d)}}$ a topological expander? What about when $\eta\leq \epsilon W_{X^{(d)}}$, $\epsilon$ small?
• What available techniques or strategies might there be for proving that a complex is a weighted $\eta$-expander?

I have used "arbitrary-dimensional" rather than "higher-dimensional" in the title because I am interested not just in the case $d\to \infty$, but in any $d$ -- say, $d=2$ or $d=3$ as much as $d$ very large.

Answer 1

For the second question, there is the iterated Cauchy-Schwarz method, where you Cauchy-Schwarz to eliminate one or more of the $f_i$ variables and then repeat this process until all the $f_i$ are gone, then estimate the remaining sum by algebraic means. An example of this sort of argument in an algebraic case where the vertices of the graph are finite fields is in Tao's paper Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets .

If the hypergraph has some symmetry, one can interweave these Cauchy-Schwarz steps with changes-of-variables that take advantage of this symmetry. An example of this argument in an algebraic case is Proposition 2.2 of Geren and Sanders's paper Monochromatic sums and products, although this proves a weaker version of expansion.

If the hypergraph has a lot of symmetry, one can do a more subtle argument involving Gowers norms of the $f_i$s, breaking them up into simpler functions, and induction, as in Peluse's paper On the polynomial Szemerédi theorem in finite fields .

However, a weakness of all these results in the finite field setting compared to the classical notion of expanders is that the number of $d$-dimensional simplices is quadratic in the number of vertices, rather than linear in the case of classical expander graphs. As the dimension grows from $3$ to $4$ to arbitrarily large, expansion becomes a more interesting/difficult/powerful notion even keeping the number of simplices fixed at quadratic, but it still might not be the analogue you're looking for of the graph case.

(The fact that these are quadratic exactly is probably not essential, and is more a reflection of natural ways of defining a hypergraph in the finite field context. It's more relevant to say the first method may be suitable for a number of simplices at least $|V|^{d/2+\delta}$, the second for a number of simplices at least $V^{ d/2}$, and the third for a number of simplices much less than $V^{d/2}$, but each progressively using more and more symmetry.)