# 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"](https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_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]](https://arxiv.org/abs/cs/0405020), [[Bor15]](https://arxiv.org/abs/1502.04482), [[BC18]](https://arxiv.org/abs/1801.00876). In particular the first several pages of [[Bor15]](https://arxiv.org/abs/1502.04482) 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]](https://doi.org/10.1006/jnth.1996.0109).
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]](https://doi.org/10.1006/eujc.1996.0040) do). The analogous result that $d$-regular hypergraphs are w.h.p. almost Ramanujan was shown in [[DZ19]](https://arxiv.org/abs/1905.06487), by connecting $A$ with the adjacency matrix of random bipartite biregular graphs [[BDH18]](https://arxiv.org/abs/1804.07808).

A second way is sometimes called the "Friedman-Wigderson" approach [[FW89]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/hyp.pdf).
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 \dots \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)}$.
3. There's no unified way to talk about eigenvalues. For the first eigenvalue, you could use the operator norm of $A$: $\lambda_1 = \sup_{\|x^{(1)}\|_r = \dots \|x^{(r)}\|_r = 1} |A(x^{(1)}, \dots, x^{(r)})|$. Note that the original [[FW89]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/hyp.pdf) uses vector $2$-norm over $\mathbb{R}$, but [[Fri90]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/tree.pdf) notes that vector $r$-norm over $\mathbb{C}$ is more natural.
* Since $A$ is real, symmetric, and nonnegative, we can assume $x^{(1)} = \dots = x^{(r)}$ and that the vector is in $\mathbb{R}$: $\lambda_1 =\sup_{ x \in \mathbb{R}^n, \|x\|_r = 1} \left|\sum_{i_1, \dots, i_r} A_{i_1,\dots,i_r} x_{i_1} \dots x_{i_r} \right|$. this is discussed in [[Nik16]](https://arxiv.org/pdf/1605.08665.pdf), which quotes [[Qi13]](https://www.sciencedirect.com/science/article/pii/S0024379513002103), 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?)
4. You could define a second eigenvalue for $d$-regular hypergraphs as $\lambda_2 = \sup_{\|x^{(1)}\|_r = \dots \|x^{(r)}\|_r = 1} \left| A(x^{(1)}, \dots, x^{(r)}) - \frac{(r-1)! \cdot d}{n^{r-1}} (1 \otimes \dots \otimes 1 )(x^{(1)}, \dots, x^{(r)}) \right|$, where $(1 \otimes \dots \otimes 1)$ is the $r$-hypermatrix that is $1$ at every entry.
* [[Fri90]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/tree.pdf) finds the second eigenvalue of the infinite $d$-regular hypertree (again, actually the first eigenvalue because of technicalities with infinite graphs).
* [[LM15]](https://arxiv.org/abs/1512.02710) 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]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/tree.pdf). Importantly, [[LM15]](https://arxiv.org/abs/1512.02710) sorts out the right way to define $\lambda_1, \lambda_2$, using results of [[CD11]](https://arxiv.org/abs/1106.4856), [[Nik13]](https://arxiv.org/abs/1308.1654), and definitions of [[Lim06]](https://arxiv.org/abs/math/0607648), [[Qi06]](https://doi.org/10.1016/j.jsc.2005.05.007), [[Qi12]](https://arxiv.org/abs/1211.5642).
* Question: [[LM15]](https://arxiv.org/pdf/1512.02710.pdf) under Definition 2.1 quotes that we can take $x^{(1)} = \dots = x^{(r)}$ because $A - c(1 \otimes \dots \otimes 1)$ is symmetric, but I'm not sure how this proof works (!?) Maybe [[Fri11]](https://arxiv.org/pdf/1110.5689.pdf)?, see also [[FL18]](https://www.stat.uchicago.edu/~lekheng/work/nuclear.pdf), [[Lim06]](https://www.stat.uchicago.edu/~lekheng/work/camsap.pdf). The symmetric thing is sometimes refered to as "$r$-spectral norm" (but inconsistent whether it's $\mathbb{R}$ or $\mathbb{C}$).
5. This leads to my **primary** question: about the tightness of the [[LM15]](https://arxiv.org/abs/1512.02710) 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](https://drops.dagstuhl.de/opus/volltexte/2018/8386/pdf/LIPIcs-FSTTCS-2017-46.pdf)
* generalization to hypergraphs (for the Feng-Li approach): [thesis](https://home.adelphi.edu/~stormc/docs/cksThesis.pdf), [arxiv paper](https://arxiv.org/pdf/math/0608761.pdf). The walk is "vertex, edge, vertex, edge" where nonbacktracking means no $e,v,e$. extended beyond regular hypergraphs [here](https://arxiv.org/pdf/2203.07346.pdf)
* 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]](https://dl.acm.org/doi/10.1145/73007.73063) and [[FO05]](https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20089)
* 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]](https://arxiv.org/abs/1911.09063). 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](https://www.stat.uchicago.edu/~lekheng/work/people.html), 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]](https://arxiv.org/pdf/1905.06487.pdf) showing Ramanujan-ness, there seem to be some improvements:
* See [[Zhu's thesis]](https://www.proquest.com/openview/3a20d819d6153e436c33ba546260f9b2/1?pq-origsite=gscholar&cbl=18750&diss=y)
* This is an interesting related paper about generalizing Ihara-Bass for CSPs [[d'OT22]](https://arxiv.org/abs/2204.10881)

Other related adjacency matrix thoughts:
* For slightly denser graphs, we can get estimates on the second eigenvalue of the adjacncy tensor, see [[JO14]](https://dl.acm.org/doi/10.5555/2968826.2968986) 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]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/hyp.pdf), this is used in Keevash-Lenz-Mubayi etc; see the introduction of [[Coo20]](https://www.sciencedirect.com/science/article/abs/pii/S0024379520301348) 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](https://doi.org/10.1007/s00039-004-0461-z)
* [a recent summary of "Ramanujan"-ness from Winnie Li](https://royalsocietypublishing.org/doi/full/10.1098/rsta.2018.0441)
* [Zeta functions of these Ramanujan complexes](https://www.sciencedirect.com/science/article/pii/S0001870814000024?via%3Dihub)
* How does this relate to the [[Chu93]](https://mathweb.ucsd.edu/~fan/wp/hyperlap.pdf) approach?

### Some other questions (less important to me)
* Do there exist deterministic "Ramanujan" hypergraphs in the [[FW89]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/hyp.pdf) approach?
* We should actually check that the [[FW89]](https://www.cs.ubc.ca/~jf/pubs/web_stuff/hyp.pdf) 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