Try   HackMD

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 \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)}\).
  2. 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] 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)} = \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], 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 = \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] 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)} = \dots = x^{(r)}\) because \(A - c(1 \otimes \dots \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.

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

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?

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