Are random regular hypergraphs almost Ramanujan?

Problem summary

First, the analogy to graphs.

1. A
   $n$-vertex graph can be associated with an adjacency matrix
   $A$ such that for all
   $i,j\in [n]$,
   $A_{ij}$ is
   $1$ if there is an edge
   $\{i,j\}$ and
   $0$ otherwise.
2. For
   $d$-regular graphs, the maximum eigenvalue of
   $A$ is always
   ${\lambda }_1=d$.
3. The second eigenvalue is lower bounded as
   ${\lambda }_2\ge 2\sqrt{d-1}\pm o_n(1)$, which is the achieved on the infinite
   $d$-regular tree (in fact this is the largest well-defined eigenvalue because of technicalities about infinite-sized graphs). The bound is known as the "Alon-Boppana bound".
4. Graphs which have
   ${\lambda }_2$ close to this lower bound are called "almost Ramanujan"; graphs that saturate the lower bound are called "Ramanujan" graphs. Famously, random
   $d$-regular graphs are w.h.p. almost Ramanujan: [Fri04], [Bor15], [BC18]. In particular the first several pages of [Bor15] are quite clear.

When we consider (

$r$-uniform) hypergraphs, there are at least two ways to consider eigenvalues. The first way is sometimes called the "Feng-Li" approach [FL96].

1. Feng and Li consider a matrix
   $A$ such that for all
   $i,j\in [n]$,
   $A_{ii}=0$, and
   $A_{ij}$ equals the number of hyperedges containing both
   $i$ and
   $j$. Notice that
   $A$ is related to the adjacency matrix of the factor graph (a bipartite graph with
   $|V|+|E|$ nodes), by looking at non-backtracking walks of length
   $2$.
2. For
   $d$-regular hypergraphs (here we mean that each node participates in
   $d$ hyperedges), the maximum eigenvalue of
   $A$ is always
   ${\lambda }_1=d(r-1)$.
3. Feng and Li show the second eigenvalue is lower bounded as
   ${\lambda }_2\ge r-2+2\sqrt{(d-1)(r-1)}\pm o_n(1)$, as a kind of generalization of the Alon-Boppana bound.
4. We could call graphs with
   ${\lambda }_2$ near or at this lower bound "almost Ramanujan" or "Ramanujan" (and in fact, [LS96] do). The analogous result that
   $d$-regular hypergraphs are w.h.p. almost Ramanujan was shown in [DZ19], by connecting
   $A$ with the adjacency matrix of random bipartite biregular graphs [BDH18].

A second way is sometimes called the "Friedman-Wigderson" approach [FW89].

1. Consider a
   $r$-hypermatrix
   $A$ such that
   $A_{i_1,\dots ,i_r}$ is
   $1$ if there is an edge
   $\{i_1,\dots ,i_r\}$ and
   $0$ otherwise. It's sometimes helpful to think about a functional
   $A:{\mathbb{C}}^n\times \cdots \times {\mathbb{C}}^n\to \mathbb{C}$ so that
   $A(x^{(1)},\dots ,x^{(r)})=\sum _{i_1,\dots ,i_r}{A}_{i_1,\dots ,i_r}{x}_{i_1}^{(1)}\dots x_{i_r}^{(r)}$.
2. There's no unified way to talk about eigenvalues. For the first eigenvalue, you could use the operator norm of
   $A$:
   ${\lambda }_1=\underset{\Vert x^{(1)}{\Vert }_r=\dots \Vert x^{(r)}{\Vert }_r=1}{sup}|A(x^{(1)},\dots ,x^{(r)})|$. Note that the original [FW89] uses vector
   $2$-norm over
   $\mathbb{R}$, but [Fri90] notes that vector
   $r$-norm over
   $\mathbb{C}$ is more natural.
   • Since
     $A$ is real, symmetric, and nonnegative, we can assume
     $x^{(1)}=\cdots =x^{(r)}$ and that the vector is in
     $\mathbb{R}$:
     ${\lambda }_1=\underset{x\in {\mathbb{R}}^n,\Vert x{\Vert }_r=1}{sup}|\sum _{i_1,\dots ,i_r}{A}_{i_1,\dots ,i_r}{x}_{i_1}\dots x_{i_r}|$. this is discussed in [Nik16], which quotes [Qi13], which quotes a paper on multilinear forms.
   • For
     $d$-regular hypergraphs (again, we mean that each node participates in
     $d$ hyperedges),
     ${\lambda }_1=(r-1)!\cdot d$. You can work this out by noting that there are
     $\frac{d}{r}\cdot n$ hyperedges. (Wait, how do I actually prove this is optimal?)
3. You could define a second eigenvalue for
   $d$-regular hypergraphs as
   ${\lambda }_2=\underset{\Vert x^{(1)}{\Vert }_r=\dots \Vert x^{(r)}{\Vert }_r=1}{sup}|A(x^{(1)},\dots ,x^{(r)})-\frac{(r-1)!\cdot d}{n^{r-1}}(1\otimes \cdots \otimes 1)(x^{(1)},\dots ,x^{(r)})|$, where
   $(1\otimes \cdots \otimes 1)$ is the
   $r$-hypermatrix that is
   $1$ at every entry.
   • [Fri90] finds the second eigenvalue of the infinite
     $d$-regular hypertree (again, actually the first eigenvalue because of technicalities with infinite graphs).
   • [LM15] show that a generalization of Alon-Boppana holds here as well, with
     ${\lambda }_2\ge \frac{r!}{r-1}\sqrt[r]{(d-1)(r-1)}\pm o_n(1)$ as in [Fri90]. Importantly, [LM15] sorts out the right way to define
     ${\lambda }_1,{\lambda }_2$, using results of [CD11], [Nik13], and definitions of [Lim06], [Qi06], [Qi12].
   • Question: [LM15] under Definition 2.1 quotes that we can take
     $x^{(1)}=\cdots =x^{(r)}$ because
     $A-c(1\otimes \cdots \otimes 1)$ is symmetric, but I'm not sure how this proof works (!?) Maybe [Fri11]?, see also [FL18], [Lim06]. The symmetric thing is sometimes refered to as "
     $r$-spectral norm" (but inconsistent whether it's
     $\mathbb{R}$ or
     $\mathbb{C}$).
4. This leads to my primary question: about the tightness of the [LM15] bound. Are random
   $d$-regular hypergraphs "almost Ramanujan"? It seems like the ideas from the graph case (Friedman, Bordenave) may directly transfer over.

next steps

Can we extend the Ihara-Bass connection to tensors?

• Ihara and others studied zeta functions (functions in complex analysis where the coefficients "count" things) applied to graphs; Bass showed that the zeta function is related to the adjacency matrix
  $A$
• proof of Ihara-Bass formula that is combinatorial and skips the non-backtracking matrix
• generalization to hypergraphs (for the Feng-Li approach): thesis, arxiv paper. The walk is "vertex, edge, vertex, edge" where nonbacktracking means no
  $e,v,e$. extended beyond regular hypergraphs here
• I guess the frustrating part about the operator norm of the tensor means that the "walk" involves the entire hyperedge; it's not just a walk from
  $i$ to
  $j$ but a walk from
  $i$ to (r-1) other points all at once.

Could we go a step earlier, and show that the two definitions of Ramanujan-ness are related?

• For example, maybe the Feng-Li matrix is related to the Friedman-Wigderson trensor, or at least the "second eigenvalues" are related.
• What if we assumed that all hyperedges overlapped on at most one vertex (so the matrix is 0-1 valued). Then it feels like the hypertree is the universal cover for both of the objects…

We should probably summarize the "types" of eigenvalues (E-eigenvalues, N-eigenvalues, etc) somewhere so we don't get confused.

• There is a 2-norm vs r-norm distinction.
• There is a
  $\lambda \in \mathbb{C}$ vs
  $\lambda \in \mathbb{R}$ distinction.
• Differently, there is a
  $v\in \mathbb{C}$ vs
  $\mathbb{R}$ distinction!

Can we prove any bound on the spectral gap? Even if it's not optimal?

• i don't know what the "simple" arguments are to be honest, how did the graph literature develop? (An expander person will know this better); maybe [FKS89] and [FO05]
• Strangely enough, I think some of the state-of-the-art is by the same Zhu that proved a bunch of things about hypergraphs in the matrix form: [ZZ19]. I don't fully undertand this work though.

We should figure out the

$r$-spectral norm (over

$\mathbb{C}$) vs operator norm of the tensor, is there a difference?

• We could ask Lekheng Lim, he's at UChicago and knows a lot about tensor norms and so on.

undertanding related work

What do we know about the adjacency matrix case? Since [DZ19] showing Ramanujan-ness, there seem to be some improvements:

• See [Zhu's thesis]
• This is an interesting related paper about generalizing Ihara-Bass for CSPs [d'OT22]

Other related adjacency matrix thoughts:

• For slightly denser graphs, we can get estimates on the second eigenvalue of the adjacncy tensor, see [JO14] although I find it a little hard to parse.
• There is related work using vectors in
  $\mathbb{R}$, and using a weird notion of "regular" presented in [FW89], this is used in Keevash-Lenz-Mubayi etc; see the introduction of [Coo20] for some references.

There's yet another definition of Ramanujan hypergraphs using "simplicial complexes" and "buildings" from Winnie Li. Is this useful?

• the original paper
• a recent summary of "Ramanujan"-ness from Winnie Li
• Zeta functions of these Ramanujan complexes
• How does this relate to the [Chu93] approach?

Some other questions (less important to me)

• Do there exist deterministic "Ramanujan" hypergraphs in the [FW89] approach?
• We should actually check that the [FW89] proofs of expander mixing lemmas and related work still hold when we switch to vector
  $r$-norm over
  $\mathbb{C}$ (instead of vector
  $2$-norm over
  $\mathbb{R}$.)

---

I emailed one of the authors Nov 2023:

​​​​I am reading this paper [1] of yours, where you claim (at the bottom of page 3):
​​​​> If φ is symmetric (and W = W1 = · · · = Wt), then it is easy to see that ‖φ‖ is attained
​​​​with x1 = · · · = xt

​​​​I do not understand how to prove this for t > 2. Could you help me?

​​​​Thank you,
​​​​Kunal

​​​​[1] https://arxiv.org/abs/1512.02710

Response:

​​​​Mon, Nov 6, 2:20 AM

​​​​to Kunal
​​​​Thanks for your interest. I am sorry that I cannot give a proof now, it seems that it is quoted from one of the references. 

​​​​Best regards
​​​​Li