# 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

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up