Eleonora Andreotti^a , Raffaella Mulas^b

aDivision of Vehicle Safety, Department of Mechanics and Maritime Sciences, Chalmers University of Technology, SE-412 96 Goteborg, Sweden ¨

mulas@mis.mpg.de

The spectral theory of the normalized Laplacian for chemical hypergraphs is further investigated. The signless normalized Laplacian is introduced and it is shown that its spectrum for classical hypergraphs coincides with the spectrum of the normalized Laplacian for bipartite chemical hypergraphs. Furthermore, the spectra of special families of hypergraphs are established.

Keywords: Hypergraphs, Spectral Theory, Signless normalized Laplace Operator

Mathematics Subject Classification: 05C50

DOI: 10.5614/ejgta.2022.10.2.11

1. Introduction

In this work we bring forward the study of the normalized Laplacian that has been established for chemical hypergraphs: hypergraphs with the additional structure that each vertex in a hyperedge is either an input, an output or both (in which case we say that it is a catalyst for that hyperedge). Chemical hypergraphs have been introduced in [19] with the idea of modeling chemical reaction networks and related ones, such as metabolic networks. In this model, each vertex represents a chemical element and each hyperedge represents a chemical reaction. Furthermore, in [24], chemical hypergraphs have been used for modeling dynamical systems with high order interactions. In this model, vertices represent oscillators while hyperedges represent the interactions on which the dynamics depends.

Received: 8 July 2021, Revised: 6 July 2022, Accepted: 17 July 2022.

^bMax Planck Institute for Mathematics in the Sciences, Inselstr. 22, 04103 Leipzig, Germany

The spectrum of the normalized Laplacian L reflects many structural properties of the network and several theoretical results on the eigenvalues have been established in [19, 23, 26]. Furthermore, as shown in [23], by defining the vertex degree in a way that it does not take catalysts into account, studying the spectrum of L for chemical hypergraphs is equivalent to studying the spectrum of the oriented hypergraphs introduced in [28] by Reff and Rusnak, in which catalysts are not included. Therefore, without loss of generality we can work on oriented hypergraphs. Here, in particular, we focus on the bipartite case and we show that the spectrum of the normalized Laplacian for bipartite chemical hypergraphs coincides with the spectrum of the signless normalized Laplacian that we introduce for classical hypergraphs. Furthermore, we establish the spectra of the signless normalized Laplacian for special families of such classical hypergraphs.

Classical hypergraphs are widely used in various disciplines. For instance, they offer a valid model for transport networks [2], neural networks (in whose context they are often called neural codes) [11, 15, 10, 9, 20, 12, 13, 25], social networks [34], epidemiology networks [6] and communication networks [33], just to mention some examples. It is worth noting that a simplicial complex S is a particular case of hypergraph with the additional constraint that, if a hyperedge belongs to S, then also all its subsets belong to S. Simplicial complexes are also widely present in applications. On the one hand, their more precise structure allows for a deeper theoretical study, compared to general hypergraphs. On the other hand, the constraints of simplicial complexes can be translated as constraints on the model, and this is not always convenient. Consider, for instance, a collaboration network that represents coauthoring of research papers: in this case, the fact that authors A, B and C have written a paper all together does not imply that A, B and C have all written single author papers, nor that A and B have written a paper together without C. In this case, a hypergraph would give a better model than a simplicial complex.

Structure of the paper. In Section 2 we introduce the basic definitions which are needed throughout the paper, while in Section 3 we introduce and discuss twin vertices. In Section 4 we prove new properties of bipartite oriented hypergraphs and we show that, from the spectral point of view, these are equivalent to classical hypergraphs with no input/output structure. Finally, in Section 5 we investigate the spectra of new hypergraph structures that we introduce with the idea of generalizing well known graph structures.

2. Basic definitions

Definition 2.1 ([28, 19]). An oriented hypergraph is a pair Γ = (V, H) such that V is a finite set of vertices and H is a set such that every element h in H is a pair of disjoint elements (hin, hout) (input and output) in P(V), where we write P(V) for the power set of V. The elements of H are called the oriented hyperedges. Changing the orientation of a hyperedge h means exchanging its input and output, leading to the pair (hout, hin).

Definition 2.2. Given h = (hin, hout) ∈ H, we say that hin1 and hout are the orientation sets of h. Two vertices i and j are co-oriented in h if they belong to the same orientation sets of h; we say that they are anti-oriented in h if they belong to different orientation sets of h.

From now on, we fix an oriented hypergraph Γ = (V, H) on N vertices v1, . . . , v^N and M hyperedges h1, . . . , hM. For simplicity, we assume that Γ has no isolated vertices.

Remark 2.1. Simple graphs can be seen as oriented hypergraphs such that #hin = #hout = 1 for each h ∈ H, that is, each edge has exactly one input and one output.

Definition 2.3. The underlying hypergraph of Γ is Γ ′ := (V, H′ ) where

\[\mathcal{H}' := \{ (h_{in} \cup h_{out}, \emptyset) : h = (h_{in}, h_{out}) \in \mathcal{H} \}.\]

Definition 2.4 ([23]). The degree of a vertex v is

\[deg(v) := \# hyperedges containing v.\]

Similarly, the cardinality of a hyperedge h is

\[#h := #\{h_{in} \cup h_{out}\}.\]

Definition 2.5 ([19, 26]). The normalized Laplace operator associated to Γ is the N × N matrix

\[L := \operatorname{Id} - D^{-1}A,\]

where Id is the N × N identity matrix, D is the diagonal degree matrix and A is the adjacency matrix defined by Aii := 0 for each i = 1, . . . , n and

\[A_{ij} := \#\{ \text{hyperedges in which } v_i \text{ and } v_j \text{ are anti-oriented} \}\]
- \(\#\{ \text{hyperedges in which } v_i \text{ and } v_j \text{ are co-oriented} \}\)

for i ̸= j.

We define the spectrum of Γ as the spectrum of L. As shown in [19, 26], this spectrum is given by N real, nonnegative eigenvalues whose sum is N. We denote them by

\[\lambda_1 \leq \ldots \leq \lambda_N\].

Definition 2.6. We say that two vertices vⁱ and v^j are adjacent, denoted vⁱ ∼ v^j , if they are contained at least in one common hyperedge.

Remark 2.2. Consider a graph Γ and let Γ ′ be its underlying hypergraph. Then, the adjacency matrix A of Γ and the adjacency matrix A′ of Γ ′ are such that A′ = −A, while the degree matrices of Γ and Γ ′ coincide. Therefore, the normalized Laplacians of Γ and Γ ′ are

\[L=\operatorname{Id}-D^{-1}A \qquad \text{ and } \qquad L'=\operatorname{Id}+D^{-1}A=2\cdot\operatorname{Id}-L,\]

respectively. Hence, λ is an eigenvalue for L if and only if 2 − λ is an eigenvalue for L ′ .

Definition 2.7. Let Γ be an oriented hypergraph and let Γ ′ be its underlying hypergraph. The signless normalized Laplacian of Γ is the normalized Laplacian of Γ ′ .

3. Twin vertices

Definition 3.1 ([26]). Two vertices vⁱ and v^j are duplicate if Aik = Ajk for all k. In particular, in this case, Aij = Aji = Aii = 0.

In [26] it is shown that nˆ duplicate vertices produce the eigenvalue 1 with multiplicity at least nˆ − 1. Similarly, in this section we discuss twin vertices.

Definition 3.2. We say that two vertices vⁱ and v^j are twins if they belong exactly to the same hyperedges, with the same orientations. In particular, Aij = − deg(vi) = − deg(v^j ) and Aik = Ajk for all k ̸= i, j.

Remark 3.1. While duplicate vertices are known also for graphs, twin vertices cannot exist for graphs, since in this case one assumes that each edge has one input and one output.

We now generalize the notions of duplicate vertices and twin vertices by defining duplicate families of twin vertices.

Definition 3.3. Let Γ = (V, H) be an oriented hypergraph. We say that a family of vertices V¹ ⊔ · · · ⊔ V^l ⊂ V is a l-duplicate family of t-twin vertices if

• For each α ∈ {1, . . . , l}, #V^α = t and the t vertices in V^α are twins to each other;
• For each α, β ∈ {1, . . . , l} with α ̸= β, for each vⁱ ∈ V^α and for each v^j ∈ Vβ, we have that Aij = 0 and Aik = Ajk for all vertices v^k that are not in the l-family, i.e. v^k ∈ V \V1⊔· · ·⊔V^l .

Proposition 3.1. If Γ contains a l-duplicate family of t twins, then:

• t is an eigenvalue with multiplicity at least l − 1;
• 0 is an eigenvalue with multiplicity at least l(t − 1).

Proof. In order to show that t is an eigenvalue with multiplicity at least l−1, consider the following l − 1 functions. For α = 2, . . . , l, let f^α : V → R such that f^α := 1 on V1, f^α := −1 on V^α and f^α := 0 otherwise. Then,

• For each vⁱ ∈ V1,

\[Lf_{\alpha}(v_i) = 1 - \frac{1}{\deg v_i} \sum_{v_i \neq v_j \in \mathcal{V}_1} -\deg v_i = 1 + t - 1 = t \cdot f_{\alpha}(v_i);\]

• For each v^j ∈ Vα,

\[Lf_{\alpha}(v_j) = -1 - \frac{1}{\deg v_j} \sum_{v_j \neq v_i \in \mathcal{V}_{\alpha}} \deg v_j = -1 - (t - 1) = t \cdot f_{\alpha}(v_j);\]

• For each \(v_k \in \mathcal{V} \setminus \mathcal{V}_1 \sqcup \mathcal{V}_{\alpha}\),

\[Lf_{\alpha}(v_k) = -\frac{1}{\deg v_k} \left( \sum_{v_i \in \mathcal{V}_1} A_{ik} - \sum_{v_j \in \mathcal{V}_{\alpha}} A_{jk} \right) = 0 = t \cdot f_{\alpha}(v_k).\]

Therefore, \(f_{\alpha}\) is an eigenfunction for t. Furthermore, the functions \(f_2, \ldots, f_l\) are linearly independent. Therefore, t is an eigenvalue with multiplicity at least l-1.

Similarly, in order to prove that 0 is eigenvalue with multiplicity at least l(t-1), let \(\mathcal{V}_{\alpha}=\{v_1^{\alpha},\ldots,v_t^{\alpha}\}\) and consider the l(t-1) functions \(g_j^{\alpha}:\mathcal{V}\to\mathbb{R}\) defined as follows, for \(\alpha=1,\ldots,l\) and \(j=2,\ldots,t\). Let \(g_j^{\alpha}(v_1^{\alpha}):=1\), \(g_j^{\alpha}(v_j^{\alpha}):=-1\) and \(g_j^{\alpha}:=0\) otherwise. Then, since \(g:\mathcal{V}\to\mathbb{R}\) is an eigenfunction for 0 if and only if

\[\sum_{v \in h_{in}} g(v) = \sum_{w \in h_{out}} g(w) \quad \forall h = (h_{in}, h_{out}) \in H\]

(as shown in [19], Equation (5)), it is clear that each \(g_j^{\alpha}\) is an eigenfunction for 0. Since, furthermore, these are l(t-1) linearly independent functions, 0 has multiplicity at least l(t-1).

Proposition 3.2. If \(\Gamma\) has \(\hat{n}\) vertices that are twins to each other, 0 is an eigenvalue with multiplicity at least \(\hat{n} - 1\). Furthermore, if \(v_i\) and \(v_j\) are twin vertices and f is an eigenfunction for L with eigenvalue \(\lambda \neq 0\), then \(f(v_i) = f(v_j)\).

Proof. The first claim follows from Proposition 3.1, by taking t = 1.

Now, assume that \(v_i\) and \(v_j\) are twin vertices and let f be an eigenfunction for L with eigenvalue \(\lambda \neq 0\). Then,

\[\lambda f(v_i) = Lf(v_i) = f(v_i) + f(v_j) - \frac{1}{\deg v_i} \left( \sum_{k \neq i,j} A_{ik} f(v_k) \right) = Lf(v_j) = \lambda f(v_j).\]

Since \(\lambda \neq 0\), this implies that \(f(v_i) = f(v_i)\).

4. Bipartite hypergraphs

Definition 4.1 ([19]). We say that an oriented hypergraph \(\Gamma\) is bipartite if one can decompose the vertex set as a disjoint union \(\mathcal{V} = \mathcal{V}_1 \sqcup \mathcal{V}_2\) such that, for every hyperedge h of \(\Gamma\), either h has all its inputs in \(\mathcal{V}_1\) and all its outputs in \(\mathcal{V}_2\), or vice versa (Figure 1).

We now give the definition of vertex-bipartite hypergraph that, as we shall see in Lemma 4.1 below, coincides with the definition of bipartite hypergraph.

Definition 4.2. We say that an oriented hypergraph \(\Gamma\) is vertex-bipartite if one can decompose the hyperedge set as a disjoint union \(\mathcal{H} = \mathcal{H}_1 \sqcup \mathcal{H}_2\) such that, for every vertex v of \(\Gamma\), either v is an input only for hyperedges in \(\mathcal{H}_1\) and it is an output only for hyperedges in \(\mathcal{H}_2\), or vice versa.

Figure 1. A bipartite hypergraph with \(V_1 = \{v_1, v_2, v_3\}\) and \(V_2 = \{v_4, v_5, v_6\}\).

Lemma 4.1. Up to changing the orientation of some hyperedges, a hypergraph is bipartite if and only if it is vertex-bipartite.

Proof. Assume that \(\Gamma\) is bipartite. Up to changing the orientation of some hyperedges, we can assume that the vertex set has a decomposition \(\mathcal{V} = \mathcal{V}_1 \sqcup \mathcal{V}_2\) such that each hyperedge h has all its inputs in \(\mathcal{V}_1\) and all its outputs in \(\mathcal{V}_2\). Therefore, every vertex in \(\mathcal{V}_1\) is an input only for hyperedges in \(\mathcal{H}\), and every vertex in \(\mathcal{V}_2\) is only an output for hyperedges in \(\mathcal{H}\). It follows that the decomposition of the hyperedge set as \(\mathcal{H} = \mathcal{H} \sqcup \emptyset\) gives a vertex-bipartition.

Now, assume that \(\Gamma\) is vertex-bipartite, with \(\mathcal{H} = \mathcal{H}_1 \sqcup \mathcal{H}_2\). Assume, by contradiction, that \(\Gamma\) is not bipartite. Then, up to changing the orientation of some hyperedges, there exist two vertices \(v, w \in \mathcal{V}\) and two hyperedges \(h_1, h_2 \in \mathcal{H}\) such that:

• 1. \(h_1\) has both v and w as inputs;
• 2. \(h_2\) has v as input and w as output.

The fact that v is an input in both \(h_1\) and \(h_2\) implies that \(h_1\) and \(h_2\) are in the same \(\mathcal{H}_i\). On the other hand, the fact that w is an input for \(h_1\) and an output for \(h_2\) implies that \(h_1\) and \(h_2\) do not belong to the same \(\mathcal{H}_i\). This brings to a contradiction. Therefore, \(\Gamma\) is bipartite.

Proposition 4.1. If \(\Gamma\) is bipartite, then it is isospectral to its underlying hypergraph, therefore, in particular, also to every other bipartite hypergraph that has the same underlying hypergraph as \(\Gamma\).

Proof. Since \(\Gamma\) is bipartite, up to switching (without loss of generality) the orientations of some hyperedges we can assume that all the inputs are in \(V_1\) and all the outputs are in \(V_2\), with \(V = V_1 \sqcup V_2\). Furthermore, by Lemma 49 in [19], we can move a vertex from \(V_1\) to \(V_2\) or vice versa, by letting it be always an output or always an input, without affecting the spectrum. In particular, if we move all vertices to \(V_1\), we obtain the underlying hypergraph of \(\Gamma\).

Remark 4.1. As a consequence of Proposition 4.1, without loss of generality we can always assume that a bipartite hypergraph \(\Gamma\) has only inputs, when studying the spectrum of the normalized Laplacian. In this case,

• \(A_{ij} = -\#\{h \in \mathcal{H} : v_i, v_j \in \mathcal{H}\}\) for each \(i \neq j\);
• \(\sum_{i} A_{ij} = -\sum_{h\ni v_i} (\#h-1)\), for each \(v_i \in \mathcal{V}\).

From here on we work on a hypergraph \(\Gamma = (\mathcal{V}, \mathcal{H})\) that has only inputs. Therefore, we focus on the signless normalized Laplacian of classical hypergraphs.

Figure 2. A 5-hyperflower with 3 twins.

5. Families of hypergraphs

5.1. Hyperflowers

We now introduce and study hyperflowers: hypergraphs in which there is a set of nodes, the core, that is well connected to the other vertices, and a set of peripheral nodes such that each of them is contained in exactly one hyperedge. Hyperflowers are therefore a generalization of star graphs [4].

Definition 5.1. A (l, r)-hyperflower with t twins (Figure 2) is an hypergraph Γ = (V, H) whose vertex set can be written as V = U ⊔ W, where:

• U is a set of t · l nodes v11, . . . , v1^l , . . . , vt1, . . . , vtl which are called peripheral;
• There exist r disjoint sets of vertices h1, . . . , h^r ∈ P(W) \ {∅} such that

\[\mathcal{H} = \{h | h = h_i \cup \bigcup_{z=1}^t v_{zj} \text{ for } i = 1, \dots, r \text{ and } j = 1, \dots, l\}.\]

If t = 1, we simply say that Γ is a (l, r)-hyperflower.

If r = 1, we simply say that Γ is a l-hyperflower with t twins.

Remark 5.1. The (l, r)-hyperflowers in Definition 5.1 are a particular case of the hyperstars in [2], that also include weights and non-disjoint sets h1, . . . , hr. Here we choose to study the particular structure of (l, r)-hyperflowers (and their generalizations with twins) because the strong symmetries of these structures allows for a deeper study of the spectrum.

Proposition 5.1. The spectrum of the (l, 2)-hyperflower on N nodes is given by:

• 0, with multiplicity N − l − 1;

• 1, with multiplicity \(\geq l-1\);
• \(\lambda_N > 1\);
• \(\lambda_{N-1} = N \lambda_N l + 1 \ge 1\).

In the particular case in which #h is constant for each \(h \in \mathcal{H}\), \(\lambda_N = \frac{N-l}{2} + 1\) and \(\lambda_{N-1} = \frac{N-l}{2}\).

Proof. By [26, Corollary 3.5], 1 is an eigenvalue with multiplicity at least l-1. Now, the N-l vertices \(v_{l+1},\ldots,v_N\) form two classes of twin vertices that generate the eigenvalue 0 with multiplicity at least N-l-2. In particular, there exist N-l-2 linearly independent corresponding eigenfunctions \(f_i:\mathcal{V}\to\mathbb{R}\) such that \(f_i(v)=1\) for some \(v\notin\{v_1,\ldots,v_l\}\), \(f_i(w)=-1\) for a given w twin of v, and \(f_i=0\) otherwise. If we let \(g(v_j):=1\) for each \(j=1,\ldots,l,\) \(g(v_1'):=-1\) for exactly one \(v_1'\in h_1\) and \(g(v_2'):=-1\) for exactly one \(v_2'\in h_2\), it's easy to see that g is also an eigenfunction of 0. Furthermore, the \(f_i\)'s and g are all linearly independent, which implies that 0 has multiplicity at least N-l-1.

Now, by [23, Theorem 3.1], \(\lambda_N \geq \frac{\sum_{h \in \mathcal{H}} \# h}{|\mathcal{H}|} > 1\). We have therefore listed already N-1 eigenvalues and there is only one eigenvalue \(\lambda\) missing. Since \(\sum_{i=1}^N \lambda_i = N\), we have that \(\lambda = N - \lambda_N - l + 1\). In particular, since by [23, Theorem 3.1] \(\lambda_N \leq \max_{h \in \mathcal{H}} \# h\) with equality if and only if # h is constant, and \(\max_{h \in \mathcal{H}} \# h \leq N - l\), we have that

\[\lambda = N - \lambda_N - l + 1 > 1\],

with equality if and only if #h is constant and equal to N-l, that is, if and only if \(\#h_1 = \#h_2 = 1\). Hence, \(\lambda = \lambda_{N-1}\) and we have that \(\lambda_{N-1} = 1\) if and only if \(\#h_1 = \#h_2 = 1\).

In general, if #h is constant for each \(h \in \mathcal{H}\), then by [23, Theorem 3.1] \(\lambda_N = \#h = \frac{N-l}{2} + 1\) and therefore \(\lambda_{N-1} = \frac{N-l}{2}\).

Proposition 5.2. Let \(\Gamma\) be an (l,r)-hyperflower with peripheral vertices \(v_1, \ldots, v_l\). Let \(\hat{\Gamma} := (\hat{\mathcal{V}}, \hat{\mathcal{H}})\) be the (1,r)-hyperflower defined by

\[\hat{\mathcal{V}} := \mathcal{V} \setminus \{v_2, \dots, v_l\}\] and \(\hat{\mathcal{H}} := \{h \in \mathcal{H} : v_2, \dots, v_l \notin h\}.\)

Then, the spectrum of \(\Gamma\) is given by:

• The N-l+1 eigenvalues of \(\hat{\Gamma}\), with multiplicity;
• 1, with multiplicity at least l-1.

Proof. By [26, Corollary 3.5], adding \(v_2, \ldots, v_l\) to \(\hat{\Gamma}\) produces the eigenvalue 1 with multiplicity l-1. Therefore, it is left to show that, if \(\lambda\) is an eigenvalue of \(\hat{\Gamma}\), then \(\lambda\) is also an eigenvalue of \(\Gamma\). Let L and A be the Laplacian and the adjacency matrix on \(\Gamma\), respectively, and let \(\hat{L}\) and \(\hat{A}\) be

the Laplacian and the adjacency matrix on \(\hat{\Gamma}\), respectively. Let also \(\hat{f}\) be an eigenfunction for \(\hat{\Gamma}\) corresponding to the eigenvalue \(\lambda\). Then,

\[\hat{L}\hat{f}(v_k) = \hat{f}(v_k) - \frac{1}{\deg_{\hat{\Gamma}} v_k} \sum_{v_i \in \hat{\mathcal{V}} \setminus \{v_k\}} \hat{A}_{ik} \hat{f}(v_i) = \lambda \cdot \hat{f}(v_k), \quad \text{for all } v_k \in \hat{\mathcal{V}}.\]

Now, let \(f: \mathcal{V} \to \mathbb{R}\) be such that \(f:=\hat{f}\) on \(\hat{\mathcal{V}}\) and \(f(v_2):=\cdots:=f(v_l):=\hat{f}(v_1)\). Then,

\[Lf(v_1) = f(v_1) - \frac{1}{\deg v_1} \sum_{v_i \in \hat{\mathcal{V}} \setminus \{v_1\}} A_{i1} f(v_i) = \hat{f}(v_1) - \frac{1}{\deg_{\hat{\Gamma}} v_1} \sum_{v_i \in \hat{\mathcal{V}} \setminus \{v_1\}} \hat{A}_{i1} \hat{f}(v_i)\]\[= \hat{L} \hat{f}(v_k) = \lambda \cdot \hat{f}(v_1) = \lambda \cdot f(v_1).\]

Similarly, for \(j \in 2, \ldots, l\),

\[Lf(v_j) = f(v_j) - \frac{1}{\deg v_j} \sum_{v_i \in \hat{\mathcal{V}} \setminus \{v_1\}} A_{ij} f(v_i) = \hat{f}(v_1) - \frac{1}{\deg_{\hat{\Gamma}} v_1} \sum_{v_i \in \hat{\mathcal{V}} \setminus \{v_1\}} \hat{A}_{i1} \hat{f}(v_i) = \lambda \cdot \hat{f}(v_1) = \lambda \cdot f(v_j).\]

Furthermore, for each \(v_k \in \mathcal{V} \setminus \{v_1, \dots, v_l\}\), we have that

• \(\deg_{\hat{\Gamma}}(v_k) = 1\) while \(\deg(v_k) = l\);
• For each \(v_{k'} \in \mathcal{V} \setminus \{v_1, \dots, v_l, v_k\}\) such that \(\hat{A}_{kk'} \neq 0\), \(\hat{A}_{kk'} = -1\) while \(A_{kk'} = -l\);
• \(\hat{A}_{k1} = A_{k1} = -1\), and \(A_{kj} = -1\) for each \(j \in 2, ..., l\).

Therefore, for for each \(v_k \in \mathcal{V} \setminus \{v_1, \dots, v_l\}\),

\[Lf(v_k) = f(v_k) - \frac{1}{\deg v_k} \left( \sum_{k'} A_{kk'} f(v_{k'}) + \sum_{j=1}^l A_{kj} f(v_j) \right)\] \[= \hat{f}(v_k) - \frac{1}{l} \left( \sum_{k'} (-l) \hat{f}(v_{k'}) + (-1) \sum_{j=1}^l \hat{f}(v_1) \right)\] \[= \hat{f}(v_k) + \sum_{k'} \hat{f}(v_{k'}) + \hat{f}(v_1)\] \[= \hat{L}\hat{f}(v_k) = \lambda \cdot \hat{f}(v_k) = \lambda \cdot f(v_k).\]

This proves that \(\lambda\) is an eigenvalue for L, and f is a corresponding eigenfunction.

Remark 5.2. Proposition 5.2 tells us that, in order to know the spectrum of a (l,r)-hyperflower, we can study the spectrum of the (1,r)-hyperflower obtained by deleting l-1 peripheral vertices and the hyperedges containing them, and then add l-1 1's to the spectrum.

Proposition 5.3. The spectrum of the l-hyperflower with t twins is given by:

• 0, with multiplicity N-l;
• t, with multiplicity l-1;
• \(\lambda_N = N tl + t\).

Proof. Since all hyperedges have cardinality N-tl+t, by [23, Theorem 3.1] we have that \(\lambda_N=N-tl+t\). Furthermore, by Proposition 3.1, t is an eigenvalue with multiplicity at least l-1. Since, clearly, N-tl+t>t, we have listed l eigenvalues whose sum is N. It follows that 0 has multiplicity N-l.

5.2. Complete hypergraphs

Definition 5.2 ([26]). We say that \(\Gamma = (\mathcal{V}, \mathcal{H})\) is the c-complete hypergraph, for some \(c \geq 2\), if \(\mathcal{V}\) has cardinality N and \(\mathcal{H}\) is given by all possible \(\binom{N}{c}\) hyperedges of cardinality c.

Proposition 5.4. The spectrum of the c-complete hypergraph is given by:

• \(\frac{N-c}{N-1}\), with multiplicity N-1;
• c, with multiplicity 1.

Proof. By [23, Theorem 3.1], \(\lambda_N = c\). Now, observe that each vertex v has degree \(d := \binom{N-1}{c-1}\), while \(a := A_{ij} = -\binom{N-2}{c-2}\) is constant for all \(i \neq j\). Therefore, \(\frac{a}{d} = -\frac{c-1}{N-1}\) and

\[Lf(v) = f(v) - \frac{a}{d} \left( \sum_{w \neq v} f(w) \right) = f(v) + \frac{c-1}{N-1} \left( \sum_{w \neq v} f(w) \right), \quad \forall v \in \mathcal{V}.\]

Now, for each \(i=2,\ldots,N\), let \(f_i(v_1):=1\), \(f_i(v_i):=-1\) and \(f_i:=0\) otherwise. Then,

• \(Lf_i(v_1) = 1 \frac{c-1}{N-1} = \frac{N-c}{N-1} \cdot f_i(v_1),\)
• \(Lf_i(v_i) = -1 + \frac{c-1}{N-1} = \frac{N-c}{N-1} \cdot f_i(v_i)\), and
• \(Lf_i(v_j) = 0 = \frac{N-c}{N-1} \cdot f_i(v_j)\) for all \(j \neq 1, i\).

Therefore, the \(f_i\)'s are N-1 linearly independent eigenfunctions for \(\frac{N-c}{N-1}\). This proves the claim.

Example 5.1. Proposition 5.4 tells us that the signless spectrum of the complete graph on N nodes is given by \(\frac{N-2}{N-1}\), with multiplicity N-1, and 2 with multiplicity 1. By Remark 2.2, this is equivalent to saying that the spectrum of the complete graph is given by \(\frac{N}{N-1}\), with multiplicity N-1, and 0 with multiplicity 1. This is a well known result (see [8]) and Proposition 5.4 generalizes it.

Figure 3. A 3-lattice.

5.3. Lattice Hypergraphs

Lattice graphs, also called grid graphs, are well known both in graph theory and in applications [5, 3, 1, 7, 17, 18, 27, 29, 14, 31]. For instance, they model topologies used in transportation networks, such as the Manhattan street network, and crystal structures used in crystallography. These structures and their spectra are also widely used in statistical mechanics, in the study of ASEP, TASEP and SSEP models [21, 32, 30], which have applications in the Ising model, (lattice) gas and which also describe the movement of ribosomes along the mRNA [16]. In this section we generalize the notion of lattice graph to the case of hypergraphs.

Definition 5.3. Given l ∈ N^≥2, we define the l-lattice as the hypergraph Γ = (V, H) on l ² nodes and 2l hyperedges that can be drawn so that:

• The vertices form a l × l grid, and
• The hyperedges are exactly the rows and the columns of the grid (Figure 3).

Proposition 5.5. The spectrum of the l-lattice is given by:

• 0, with multiplicity l ² − 2l + 1;
• l 2 , with multiplicity 2(l − 1);
• l, with multiplicity 1.

Proof. By [23, Theorem 3.1], λ^{l 2} = l. Furthermore, by [19, Corollay 33], since the maximum number of linearly independent hyperedges is 2l − 1, this implies that 0 is an eigenvalue with multiplicity l ² − 2l + 1.

Now, observe that deg v = 2 for each v and

\[A_{ij} = \begin{cases} -1, & \text{if } v_i \sim v_j; \\ 0, & \text{otherwise,} \end{cases}\]

for all \(i \neq j\). Therefore,

\[Lf(v) = f(v) + \frac{1}{2} \left( \sum_{w \sim v} f(w) \right), \quad \text{for all } v \in \mathcal{V}.\] (1)

Fix a row of the l-lattice given by the vertices \(w_1, \ldots, w_l\). For \(i = 1, \ldots, l-1\), let \(f_i : \mathcal{V} \to \mathbb{R}\) be 1 on the neighbors of \(w_i\) with respect to the row, -1 on the neighbors of \(w_i\) with respect to its column, and 0 otherwise. Then, by (1), it is easy to check that \(f_i\) is an eigenfunction for \(\frac{l}{2}\). Since the \(f_i\)'s are linearly independent, this proves the claim.

5.4. Hypercycles

Definition 5.4. Fix N and \(l \in \{2, ..., \frac{N}{2}\}\). We say that \(\Gamma = (\mathcal{V}, \mathcal{H})\) is the l-hypercycle on N nodes (Figure 4) if \(\mathcal{V} = \{v_1, ..., v_N\}\), \(\mathcal{H} = \{h_1, ..., h_N\}\) and

\[h_i = \{v_i, \dots, v_{i+l-1}\},\\]

where we let \(v_{N+i} := v_i\) for each i = 1, ..., N.

Theorem 5.2. The eigenvalues of the l-hypercycle are

\[\lambda_i = 1 + \frac{\sum_{r=1}^{N} m(r) \cdot \cos\left(\frac{2\pi i r}{N}\right)}{l}, \quad for \ i = 1, \dots, N,\]

where \(m: \{0, \dots, N\} \to \mathbb{Z}\) is such that:

• m(r) := l r for all \(r \in \{1, \dots, l-1\}\)
• m(N-k) := m(k) = l k for all \(k \in \{1, ..., l-1\}\)
• m := 0 otherwise.

Proof. By construction, all vertices have degree l. Therefore, by [26, Remark 2.17], proving the claim is equivalent to proving that the eigenvalues of the adjacency matrix are

\[\mu_i = -\sum_{r=1}^N m(r) \cdot \cos\left(\frac{2\pi i r}{N}\right), \quad \text{for } i = 1, \dots, N.\]

Observe that the adjacency matrix can be written as

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Therefore,

\[A = -\begin{bmatrix} m(0) & m(N-1) & m(N-2) & \cdots & m(1) \\ m(1) & m(0) & m(N-1) & \cdots & m(2) \\ m(2) & m(1) & m(0) & \cdots & m(3) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ m(N-1) & m(N-2) & m(N-3) & \cdots & m(0) \end{bmatrix}\]

where

• m(r) := l r for all \(r \in \{1, \dots, l-1\}\)
• \(m(N-k) := m(k) = l-k \text{ for all } k \in \{1, \dots, l-1\}\)
• m := 0 otherwise.

Hence, A is a (symmetric) circulant matrix. By [22], the eigenvalues of A are

\[\mu_i = -\sum_{r=1}^N m(r) \cdot \cos\left(\frac{2\pi i r}{N}\right), \quad \text{for } i = 1, \dots, N.\]

This proves the claim.

Acknowledgement

We are grateful to the anonymous referee for the helpful comments.

Figure 4. The 3-hypercycle on 6 nodes.

References

• [1] B.D. Acharya and M.K. Gill, On the index of gracefulness of a graph and the gracefulness of two-dimensional square lattice graphs, Indian J. Math. 23 (1981), 81–94.
• [2] E. Andreotti, Spectra of hyperstars, Australas. J. Comb. 82 (2022), 74–94.
• [3] E. Andreotti, A. Bazzani, S. Rambaldi, N. Guglielmi, and P. Freguglia, Modeling traffic fluctuations and congestion on a road network, Advances in Complex Systems 18 (2015).
• [4] E. Andreotti, D. Remondini, G. Servizi, and A. Bazzani, On the multiplicity of Laplacian eigenvalues and Fiedler partitions, Linear Algebra and its Applications 544 (2018), 206–222.
• [5] M. Asllani, D.M. Busiello, T. Carletti, D. Fanelli, and G. Planchon, Turing instabilities on cartesian product networks, Scientific Reports 5 (2015).
• [6] A. Bod ´ o, G.Y. Katona, and P.L. Simon, SIS epidemic propagation on hypergraphs, ´ Bull. Math. Biol. 78(4) (2016), 713–735.
• [7] T.Y. Chang, Domination Numbers of Grid Graphs, PhD thesis, Tampa, FL: University of South Florida, 1992.
• [8] F. Chung, Spectral graph theory, American Mathematical Society, (1997).
• [9] C. Curto, What can topology tell us about the neural code?, Bull. Amer. Math. Soc. 54 (2017), 63–78.
• [10] C. Curto, E. Gross, J. Jeffries, K. Morrison, Z. Rosen M. Omar, A. Shiu, and N. Youngs, What makes a neural code convex?, SIAM J. Appl. Algebra Geom. 1 (2016), 222–238.
• [11] C. Curto, V. Itskov, A. Veliz-Cuba, and N. Youngs, The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes, Bull. Math. Biol. 75(9) (2013), 1571–1611.

• [12] M.K. Franke and M. Hoch, Investigating an algebraic signature for max intersection-complete codes, Texas A&M Mathematics REU, 2017.
• [13] M.K. Franke and S. Muthiah, Every neural code can be realized by convex sets, Adv. Appl. Math. 99 (2018), 83–93.
• [14] L.R. Fuentes, I.J. Dejter, and C.A. Araujo, Rainbow perfect domination in lattice graphs, Electron, J. Graph Theory Appl. 6(1) (2018), 95–112.
• [15] C. Giusti and V. Itskov, A no-go theorem for one-layer feedforward networks, Neural Comput. 26 (2014), 2527–2540.
• [16] A.A. Gritsenko, M. Hulsman, M.J.T. Reinders, and D. de Ridder, Unbiased quantitative models of protein translation derived from ribosome profiling data, PLoS Computational Biology 11 (2015).
• [17] A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter. Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982), 676–686.
• [18] H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S.I. Minato, Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions, TCS Technical Report. No. TCS-TR-A-13-64. Hokkaido University Division of Computer Science., 2013.
• [19] J. Jost and R. Mulas, Hypergraph Laplace operators for chemical reaction networks, Advances in Mathematics 351 (2019), 870–896.
• [20] C. Lienkaemper, A. Shiu, and Z. Woodstock, Obstructions to convexity in neural codes, Adv. Appl. Math. 85 (2017), 31–59.
• [21] K. Mallick, Some exact results for the exclusion process, Journal of Statistical Mechanics: Theory and Experiment, 01 (2011), P01024.
• [22] J. Montaldi, Notes on circulant matrices, Manchester Institute for Mathematical Sciences School of Mathematics, (2012).
• [23] R. Mulas, Sharp bounds for the largest eigenvalue, Math. notes 109 (2021), 102–109.
• [24] R. Mulas, C. Kuehn, and J. Jost, Coupled dynamics on hypergraphs: Master stability of steady states and synchronization, Phys. Rev. E 101 (2020), 062313.
• [25] R. Mulas and N.M. Tran, Minimal embedding dimensions of connected neural codes, Journal of Algebraic Statistics 11(1) (2020), 99–106.
• [26] R. Mulas and D. Zhang, Spectral theory of Laplace Operators on oriented hypergraphs, Discrete Math. 344(6) (2021), 112372.

• [27] V. Reddy and S. Skiena, Frequencies of large distances in integer lattices, Technical Report, Department of Computer Science. Stony Brook, NY: State University of New York, Stony Brook, 1989.
• [28] N. Reff and L. Rusnak, An oriented hypergraphic approach to algebraic graph theory, Linear Algebra and its Applications 437 (2012), 2262–2270.
• [29] T.G. Schmalz, G.E. Hite, and D.J. Klein, Compact self-avoiding circuits on two-dimensional lattices, J. Phys. A: Math. Gen. 17 (1984), 445–453.
• [30] G. M. Schutz, Fluctuations in stochastic interacting particle systems, In ¨ Part of the Springer Proceedings in Mathematics & Statistics book series (PROMS, Vol. 282), 2017.
• [31] A. Shabbir, C.T. Zamfirescu, and T.I. Zamfirescu, Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1(1) (2013), 56–76.
• [32] G.H. Shirdel and A. Mortezaee, Determining the robustness of an interdependent network with a hypergraph model, Electron. J. Graph Theory Appl. 8(1) (2020), 113–122.
• [33] E.R. Speer, The Two Species Totally Asymmetric Simple Exclusion Process, pages 91–102, Springer US, Boston, MA, 1994.
• [34] Z.K. Zhang and C. Liu, A hypergraph model of social tagging networks, J. Stat. Mech. 10 (2010), P10005.