The Largest Laplacian and Signless Laplacian H-Eigenvalues of a Uniform Hypergraph

Introduction

In this paper, we study the largest Laplacian and signless Laplacian H-eigenvalues of a uniform hypergraph. The largest Laplacian and signless Laplacian H-eigenvalues refer to respectively the largest H-eigenvalue of the Laplacian tensor and the largest H-eigenvalue of the signless Laplacian tensor. This work is motivated by the classic results for graphs . Please refer to for recent developments on spectral hypergraph theory and the essential tools from spectral theory of nonnegative tensors.

This work is a companion of the recent study on the eigenvectors of the zero Laplacian and signless Laplacian eigenvalues of a uniform hypergraph by Hu and Qi . For the literature on the Laplacian-type tensors for a uniform hypergraph, which becomes an active research frontier in spectral hypergraph theory, please refer to and references therein. Among others, Qi , and Hu and Qi respectively systematically studied the Laplacian and signless Laplacian tensors, and the Laplacian of a uniform hypergraph. These three notions of Laplacian-type tensors are more natural and simpler than those in the literature.

The rest of this paper is organized as follows. Some definitions on eigenvalues of tensors and uniform hypergraphs are presented in the next section. The class of hyperstars is introduced. We discuss in Section 3 the largest Laplacian H-eigenvalue of a $k$-uniform hypergraph. We show that when $k$ is even, the largest Laplacian H-eigenvalue has a tight lower bound that is strictly larger than the maximum degree. Extreme hypergraphs in this case are characterized, which are the hyperstars. When $k$ is odd, a tight lower bound is exactly the maximum degree. However, we are not able to characterize the extreme hypergraphs in this case. Then we discuss the largest signless Laplacian H-eigenvalue in Section 4. Tight lower and upper bounds for the largest signless Laplacian H-eigenvalue of a connected hypergraph are given. Extreme hypergraphs are characterized as well. For the lower bound, the extreme hypergraphs are hyperstars; and for the upper bound, the extreme hypergraphs are complete hypergraphs. The relationship between the largest Laplacian H-eigenvalue and the largest signless Laplacian H-eigenvalue is discussed in Section 5. The largest Laplacian H-eigenvalue is always less than or equal to the largest signless Laplacian H-eigenvalue. When the hypergraph is connected, the equality holds here if and only if $k$ is even and the hypergraph is odd-bipartite. This result can help to find the largest Laplacian H-eigenvalue of an even-uniform hypercycle. Some final remarks are made in the last section.

Preliminaries

Some definitions of eigenvalues of tensors and uniform hypergraphs are presented in this section.

In this subsection, some basic definitions on eigenvalues of tensors are reviewed. For comprehensive references, see and references therein. Especially, for spectral hypergraph theory oriented facts on eigenvalues of tensors, please see .

It is seen that H-eigenvalues are real numbers . By , we have that the number of H-eigenvalues of a real tensor is finite. By , we have that all the tensors considered in this paper have at least one H-eigenvalue. Hence, we can denote by $\lambda(\mathcal{T})$ (respectively $\mu(\mathcal{T})$) as the largest (respectively smallest) H-eigenvalue of a real tensor $\mathcal{T}$.

For a subset $S\subseteq[n]$, we denoted by $|S|$ its cardinality, and $\mbox{sup}(\mathbf{x}):=\{i\in[n]\;|\;x_{i}\neq 0\}$ its support.

2 Uniform Hypergraphs

In this subsection, we present some essential concepts of uniform hypergraphs which will be used in the sequel. Please refer to for comprehensive references.

In this paper, unless stated otherwise, a hypergraph means an undirected simple $k$-uniform hypergraph $G$ with vertex set $V$, which is labeled as $[n]=\{1,\ldots,n\}$, and edge set $E$. By $k$-uniformity, we mean that for every edge $e\in E$, the cardinality $|e|$ of $e$ is equal to $k$. Throughout this paper, $k\geq 3$ and $n\geq k$. Moreover, since the trivial hypergraph (i.e., $E=\emptyset$) is of less interest, we consider only hypergraphs having at least one edge (i.e., nontrivial) in this paper.

For a subset $S\subset[n]$, we denoted by $E_{S}$ the set of edges $\{e\in E\;|\;S\cap e\neq\emptyset\}$. For a vertex $i\in V$, we simplify $E_{\{i\}}$ as $E_{i}$. It is the set of edges containing the vertex $i$, i.e., $E_{i}:=\{e\in E\;|\;i\in e\}$. The cardinality $|E_{i}|$ of the set $E_{i}$ is defined as the degree of the vertex $i$, which is denoted by $d_{i}$. Two different vertices $i$ and $j$ are connected to each other (or the pair $i$ and $j$ is connected), if there is a sequence of edges $(e_{1},\ldots,e_{m})$ such that $i\in e_{1}$, $j\in e_{m}$ and $e_{r}\cap e_{r+1}\neq\emptyset$ for all $r\in[m-1]$. A hypergraph is called connected, if every pair of different vertices of $G$ is connected. Let $S\subseteq V$, the hypergraph with vertex set $S$ and edge set $\{e\in E\;|\;e\subseteq S\}$ is called the sub-hypergraph of $G$ induced by $S$. We will denote it by $G_{S}$. A hypergraph is regular if $d_{1}=\cdots=d_{n}=d$. A hypergraph $G=(V,E)$ is complete if $E$ consists of all the possible edges. In this case, $G$ is regular, and moreover $d_{1}=\cdots=d_{n}=d={n-1\choose k-1}$. In the sequel, unless stated otherwise, all the notations introduced above are reserved for the specific meanings.

For the sake of simplicity, we mainly consider connected hypergraphs in the subsequent analysis. By the techniques in , the conclusions on connected hypergraphs can be easily generalized to general hypergraphs.

The following definition for the Laplacian tensor and signless Laplacian tensor was proposed by Qi .

Let $G=(V,E)$ be a $k$-uniform hypergraph. The adjacency tensor of $G$ is defined as the $k$-th order $n$-dimensional tensor $\mathcal{A}$ whose $(i_{1}\ldots i_{k})$-entry is:

Let $\mathcal{D}$ be a $k$-th order $n$-dimensional diagonal tensor with its diagonal element $d_{i\ldots i}$ being $d_{i}$, the degree of vertex $i$, for all $i\in[n]$. Then $\mathcal{L}:=\mathcal{D}-\mathcal{A}$ is the Laplacian tensor of the hypergraph $G$, and $\mathcal{Q}:=\mathcal{D}+\mathcal{A}$ is the signless Laplacian tensor of the hypergraph $G$.

In the following, we introduce the class of hyperstars.

Let $G=(V,E)$ be a $k$-uniform hypergraph. If there is a disjoint partition of the vertex set $V$ as $V=V_{0}\cup V_{1}\cup\cdots\cup V_{d}$ such that $|V_{0}|=1$ and $|V_{1}|=\cdots=|V_{d}|=k-1$, and $E=\{V_{0}\cup V_{i}\;|\;i\in[d]\}$, then $G$ is called a hyperstar. The degree $d$ of the vertex in $V_{0}$, which is called the heart, is the size of the hyperstar. The edges of $G$ are leaves, and the vertices other than the heart are vertices of leaves.

It is an obvious fact that, with a possible renumbering of the vertices, all the hyperstars with the same size are identical. Moreover, by Definition 2.1, we see that the process of renumbering does not change the H-eigenvalues of either the Laplacian tensor or the signless Laplacian tensor of the hyperstar. The trivial hyperstar is the one edge hypergraph, its spectrum is very clear . In the sequel, unless stated otherwise, a hyperstar is referred to a hyperstar having size $d>1$. For a vertex $i$ other than the heart, the leaf containing $i$ is denoted by $le(i)$. An example of a hyperstar is given in Figure 1.

The notions of odd-bipartite and even-bipartite even-uniform hypergraphs are introduced in .

Let $k$ be even and $G=(V,E)$ be a $k$-uniform hypergraph. It is called odd-bipartite if either it is trivial (i.e., $E=\emptyset$) or there is a disjoint partition of the vertex set $V$ as $V=V_{1}\cup V_{2}$ such that $V_{1},V_{2}\neq\emptyset$ and every edge in $E$ intersects $V_{1}$ with exactly an odd number of vertices.

An example of an odd-bipartite hypergraph is given in Figure 2.

The Largest Laplacian H-Eigenvalue

This section presents some basic facts about the largest Laplacian H-eigenvalue of a uniform hypergraph. We start the discussion on the class of hyperstars.

Some properties of hyperstars are given in this subsection.

The next proposition is a direct consequence of Definition 2.3.

Let $G=(V,E)$ be a hyperstar of size $d>0$. Then except for one vertex $i\in[n]$ with $d_{i}=d$, we have $d_{j}=1$ for the others.

By Theorem 4 of , we have the following lemma.

Let $G=(V,E)$ be a $k$-uniform hypergraph with its maximum degree $d>0$ and $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be its Laplacian tensor. Then $\lambda(\mathcal{L})\geq d$.

When $k$ is even and $G$ is a hyperstar, Lemma 3.1 can be strengthened as in the next proposition.

Let $k$ be even and $G=(V,E)$ be a hyperstar of size $d>0$ and $\mathcal{L}=\mathcal{D}-\mathcal{A}$ be its Laplacian tensor. Then $\lambda(\mathcal{L})>d$.

Thus, if $\mathbf{x}$ is an H-eigenvector of $\mathcal{L}$ corresponding to an H-eigenvalue $\lambda$, then we must have

Let $f(\lambda):=(1-\lambda)^{k-1}(\lambda-d)+d$. We have that

Consequently, $f(\lambda)=0$ does have a root in the interval $(d,d+1)$. Hence $\mathcal{L}$ has an H-eigenvalue $\lambda>d$. The result follows. $\Box$

The next lemma characterizes H-eigenvectors of the Laplacian tensor of a hyperstar corresponding to an H-eigenvalue which is not one .

Proof. Suppose that the H-eigenvalue is $\lambda\neq 1$. By the definition of eigenvalues, we have that for the vertex $j$ other than the heart and the vertex $i$,

Since $\lambda\neq 1$, we must have that $x_{j}=0$.

With a similar proof, we get the other conclusion by contradiction, since $h\in le(i)$ for all vertices $i$ of leaves and $\mathbf{x}\neq 0$. $\Box$

The next lemma characterizes the H-eigenvectors of the Laplacian tensor of a hyperstar corresponding to the largest Laplacian H-eigenvalue.

(I). We first prove that for every leaf $e\in E$, $|y_{t}|$ is a constant for all $t\in e\setminus\{1\}$.

For an arbitrary but fixed leaf $e\in E$, suppose that $|y_{i}|=\max\{|y_{j}|\;|\;j\in e\setminus\{1\}\}$ and $|y_{s}|=\min\{|y_{j}|\;|\;j\in e\setminus\{1\}\}$. If $|y_{i}|=|y_{s}|$, then we are done. In the following, suppose on the contrary that $|y_{i}|>|y_{s}|$. Then, we have

By the definitions of $|y_{i}|$ and $|y_{s}|$, we have $y_{1}\prod_{j\in e\setminus\{1,i\}}|y_{j}|<y_{1}\prod_{j\in e\setminus\{1,s\}}|y_{j}|$. On the other hand, we have $(\lambda(\mathcal{L})-1)|y_{i}|^{k-1}>(\lambda(\mathcal{L})-1)|y_{s}|^{k-1}$. Hence, a contradiction is derived. Consequently, for every leaf $e\in E$, $|y_{t}|$ is a constant for all $t\in e\setminus\{1\}$.

(II). We next show that all the numbers in this set

When $k$ is even, suppose that $y_{i}<0$ for some $i$. Then

Thus, an odd number of vertices in $le(i)$ takes negative values. By (2), we must have that there exists some $i\in e$ such that $y_{i}<0$ for every $e\in E$. Otherwise, $(\lambda(\mathcal{L})-1)y_{i}^{k-1}>0$, together with $-y_{1}\prod_{j\in le(i)\setminus\{1,i\}}y_{j}<0$, would lead to a contradiction. Hence, all the numbers in this set

When $k$ is odd, suppose that $y_{i}<0$ for some $i$. Then

Thus, an positive even number of vertices in $le(i)$ takes negative values. Thus, if there is some $s\in le(i)$ such that $y_{s}>0$, then

Since $s\in le(i)$, we have $le(i)=le(s)$ and $i\in le(s)$. Hence, $y_{1}\prod_{j\in le(s)\setminus\{1,s\}}y_{j}>0$. A contradiction is derived. By (3), we must have that there exists some $i\in e$ such that $y_{i}<0$ for every $e\in E$. Consequently, $y_{j}<0$ for all $j\neq 1$. Hence, all the numbers in this set

(III.) We construct the desired vector $\mathbf{z}$.

If the product $\prod_{j\in e\setminus\{1\}}y_{j}$ is a constant for every leaf $e\in E$, then take $\mathbf{z}=\mathbf{y}$ and we are done. In the following, suppose on the contrary that the set

and $z_{1}=y_{1}$. Note that $|z_{2}|=\cdots=|z_{n_{2}}|$, since $|y_{j}|^{k-1}=\alpha_{t}$ for all $j\in e_{t}\setminus\{1\}$ and $e_{t}\in E$. Then

For any $i\neq 1$ with $i\in e_{s}$ for some $s$, we have

By Definition 2.1, $\mathbf{z}$ is an H-eigenvector of $\mathcal{L}$ corresponding to $\lambda(\mathcal{L})$ with the requirement. The result follows. $\Box$

The next corollary follows directly from the proof of Lemma 3.3.

However, in Section 3.3, we will show that $\mbox{sup}(\mathbf{z})$ is a singleton which is the heart.

The next lemma is useful, which follows from a similar proof of [16, Theorem 5].

Let $k$ be even and $G=(V,E)$ be a $k$-uniform hypergraph. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then

The next lemma is an analogue of Corollary 3.1 for $k$ being even.

Suppose, without loss of generality, that $1$ is the heart. By Lemma 3.2, without loss of generality, suppose that $\mbox{sup}(\mathbf{x})=[n]$. If $x_{1}>0$, then let $\mathbf{y}=-\mathbf{x}$, and otherwise let $\mathbf{y}=\mathbf{x}$.

Suppose that $y_{i}<0$ for some $i$ other than $y_{1}$. Then

Thus, a positive even number of vertices in $le(i)$ other than $1$ takes negative values. Hence, all the values in this set

Here, the second equality follows from the fact that $\prod_{j\in le(i)\setminus\{1,i\}}y_{j}<0$ in this situation. Moreover,

Consequently, $\mathbf{z}$ is the desired H-eigenvector. $\Box$

The next theorem gives the largest Laplacian H-eigenvalue of a hyperstar for $k$ being even.

Let $k$ be even and $G=(V,E)$ be a hyperstar of size $d>0$. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})$ is the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$.

Let $f(\lambda):=(1-\lambda)^{k-1}(\lambda-d)+d$. Then, $f^{\prime}(\lambda)=(1-\lambda)^{k-2}((k-1)(d-\lambda)+1-\lambda)$. Hence, $f$ is strictly decreasing in the interval $(d,+\infty)$. Moreover, $f(d+1)<0$. Consequently, $f$ has a unique real root in the interval $(d,d+1)$ which is the maximum. Thus, by Proposition 3.2, we must have $\mbox{sup}(\mathbf{x})=[n]$. The result follows. $\Box$

The next corollary is a direct consequence of Theorem 3.1.

Let $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ be two hyperstars of size $d_{1}$ and $d_{2}>0$, respectively. Let $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ be the Laplacian tensors of $G_{1}$ and $G_{2}$ respectively. If $d_{1}>d_{2}$, then $\lambda(\mathcal{L}_{1})>\lambda(\mathcal{L}_{2})$.

When $k$ is even, the proofs of Lemmas 3.3 and 3.5, and Theorem 3.1 actually imply the next corollary.

2 Even-Uniform Hypergraphs

In this subsection, we present a tight lower bound for the largest Laplacian H-eigenvalue and characterize the extreme hypergraphs when $k$ is even.

The next theorem gives the lower bound, which is tight by Theorem 3.1.

Let $k$ be even and $G=(V,E)$ be a $k$-uniform hypergraph with the maximum degree being $d>0$. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})$ is not smaller than the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$.

Proof. Suppose that $d_{s}=d$, the maximum degree. Let $G^{\prime}=(V^{\prime},E^{\prime})$ be a $k$-uniform hypergraph such that $E^{\prime}=E_{s}$ and $V^{\prime}$ consisting of the vertex $s$ and the vertices which share an edge with $s$. Let $\mathcal{L}^{\prime}$ be the Laplacian tensor of $G^{\prime}$. We claim that $\lambda(\mathcal{L})\geq\lambda(\mathcal{L}^{\prime})$.

Obviously, $\sum_{i\in[n]}x_{i}^{k}=\sum_{j\in[m]}y_{j}^{k}=1$. Moreover,

Here the inequality follows from the fact that $\sum_{t\in e}x_{t}^{k}-k\prod_{w\in e}|x_{w}|\geq 0$ by the arithmetic-geometric mean inequality. Thus, by the characterization (4) (Lemma 3.4), we get the conclusion since $\lambda(\mathcal{L})\geq\mathcal{L}\mathbf{x}^{k}$.

Moreover, $\sum_{j\in[m]}y_{j}^{k}\leq\sum_{t\in\bar{V}}z_{t}^{k}=1$. By (4) and the fact that $\lambda(\bar{\mathcal{L}})>0$ (Theorem 3.1), we see that

Consequently, $\lambda(\mathcal{L})\geq\lambda(\bar{\mathcal{L}})$. By Theorem 3.1, $\lambda(\bar{\mathcal{L}})$ is the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$. Consequently, $\lambda(\mathcal{L})$ is no smaller than the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$. $\Box$

By the proof of Theorem 3.2, the next theorem follows immediately.

Let $k$ be even, and $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$ be two $k$-uniform hypergraphs. Suppose that $\mathcal{L}$ and $\mathcal{L}^{\prime}$ be the Laplacian tensors of $G$ and $G^{\prime}$ respectively. If $V\subseteq V^{\prime}$ and $E\subseteq E^{\prime}$, then $\lambda(\mathcal{L})\leq\lambda(\mathcal{L}^{\prime})$.

The next lemma helps us to characterize the extreme hypergraphs with respect to the lower bound of the largest Laplacian H-eigenvalue.

The next theorem is the main result of this subsection, which characterizes the extreme hypergraphs with respect to the lower bound of the largest Laplacian H-eigenvalue.

Let $k\geq 4$ be even and $G=(V,E)$ be a $k$-uniform connected hypergraph with the maximum degree being $d>0$. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})$ is equal to the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$ if and only if $G$ is a hyperstar.

Proof. By Theorem 3.1, only necessity needs a proof. In the following, suppose that $\lambda(\mathcal{L})$ is equal to the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$. Suppose that $d_{s}=d$ as before.

Define $G^{\prime}$ and $\bar{G}$ as in Theorem 3.2. Actually, let $G^{\prime}=(V^{\prime},E^{\prime})$ be the $k$-uniform hypergraph such that $E^{\prime}=E_{s}$ and $V^{\prime}$ consisting of the vertex $s$ and the vertices which share an edge with $s$. Let $\mathcal{L}^{\prime}$ be the Laplacian tensor of $G^{\prime}$. Fix the vertex $s$, and for every edge $e\in E_{s}$, number the rest $k-1$ vertices as $\{(e,2),\ldots,(e,k)\}$. Let $\bar{G}=(\bar{V},\bar{E})$ be the $k$-uniform hypergraph such that $\bar{V}:=\{s,(e,2),\ldots,(e,k),\;\forall e\in E_{s}\}$ and $\bar{E}:=\{\{s,(e,2),\ldots,(e,k)\}\;|\;e\in E_{s}\}$.

With the same proof as in Theorem 3.2, by Lemma 3.4, we have that inequality in (7) is an equality if and only if $|\bar{V}|=m$. Since otherwise $\sum_{j\in[m]}y_{j}^{k}<\sum_{t\in\bar{V}}z_{t}^{k}=1$, which together with $\lambda(\bar{\mathcal{L}})>0$ and (4) implies that $\lambda(\mathcal{L}^{\prime})>\lambda(\bar{\mathcal{L}})$. Hence, if $\lambda(\mathcal{L})$ is equal to the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$, then $G^{\prime}$ is a hyperstar. In this situation, the inequality in (6) is an equality if and only if $G^{\prime}=G$. The sufficiency is clear.

For the necessity, suppose that $G^{\prime}\neq G$. Then there is an edge $\bar{e}\in E$

either containing both vertices in $[m]$ and vertices in $[n]\setminus[m]$, since $G$ is connected,

or containing only vertices in $[m]\setminus\{s\}$.

If $\prod_{w\in\bar{e}}x_{w}<0$, then we get a contradiction since $\lambda(\mathcal{L}^{\prime})$ is equal to the unique real root of the equation $(1-\lambda)^{k-1}(\lambda-d)+d=0$ in the interval $(d,d+1)$. In the following, we assume that $\prod_{w\in\bar{e}}x_{w}>0$. We have two cases:

$x_{w}>0$ or $x_{w}<0$ for all $w\in\bar{e}$,

$x_{b}>0$ for some $b\in\bar{e}$ and $x_{c}<0$ for some $c\in\bar{e}$.

Note that $|e_{a}\cap\bar{e}|\leq k-2$ for all $a\in[q]$. For an arbitrary but fixed $a\in[q]$, define $\{f_{1},f_{2}\}:=\{f\in e_{a}\setminus\{s\}\;|\;x_{f}<0\}$.

(III). The proof for the case $f_{2}\in\bar{e}$ and $f_{1}\notin\bar{e}$ is similar.

Thus, $G=G^{\prime}$ is a hyperstar. $\Box$

Theorems 3.2 and 3.4 generalize the classical result for graphs .

3 Odd-Uniform Hypergraphs

In this subsection, we discuss odd-uniform hypergraphs. Note that there does not exist an analogue of Lemma 3.4 for $k$ being odd. Hence it is difficult to characterize the extreme hypergraphs for the lower bound of the largest H-eigenvalue of the Laplacian tensor.

Let $k$ be odd and $G=(V,E)$ be a hyperstar of size $d>0$. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})=d$.

Proof. The case for $d=1$ follows by direct computation, since in this case, for all $i\in[k]$

If $\lambda(\mathcal{L})>1$, then $x_{i}^{k}=x_{j}^{k}$ for all $i,j\in[k]$. Since $k$ is odd and $x\not=0$, we have $x_{i}=x_{j}\not=0$ for all $i,j\in[k]$. This implies that $0<\lambda(\mathcal{L})-1=-1<0$, a contradiction.

Suppose on the contrary that $\mbox{sup}(\mathbf{x})\neq\{1\}$. By Lemma 3.2 and Corollary 3.1, without loss of generality, we assume that $\mbox{sup}(\mathbf{x})=[n]$ and $\mathbf{x}$ is of the following form

Hence, we must have $\lambda(\mathcal{L})<d$. This is a contradiction. Hence, $\lambda(\mathcal{L})=d$. $\Box$

When $k$ is odd, Theorem 3.5, together with Lemma 3.1, implies that the maximum degree is a tight lower bound for the largest Laplacian H-eigenvalue.

We now give a lower bound for the largest Laplacian H-eigenvalue of a $3$-uniform complete hypergraph.

Let $G=(V,E)$ be a $3$-uniform complete hypergraph. Let $\mathcal{L}$ be the Laplacian tensor of $G$ and $n=2m$ for some positive integer $m$. Then $\lambda(\mathcal{L})\geq{n-1\choose 2}+m-1$, which is strictly larger than $d={n-1\choose 2}$, the maximum degree of $G$.

Thus, for any $p=2,\cdots,m$, we have that

Similarly, for any $p\in\{m+1,\ldots,2m\}$, we have that

Thus, $\mathbf{x}$ is an H-eigenvector of $\mathcal{L}$ corresponding to the H-eigenvalue ${n-1\choose 2}+m-1$. $\Box$

Let $k\geq 3$ be odd and $G=(V,E)$ be a $k$-uniform connected hypergraph with the maximum degree being $d>0$. Let $\mathcal{L}$ be the Laplacian tensor of $G$. Then $\lambda(\mathcal{L})$ is equal to $d$ if and only if $G$ is a hyperstar.

The Largest Signless Laplacian H-eigenvalue

In this section, we discuss the largest signless Laplacian H-eigenvalue of a $k$-uniform hypergraph. Since the signless Laplacian tensor $\mathcal{Q}$ is nonnegative, the situation is much clearer than the largest Laplacian H-eigenvalue.

The next proposition gives bounds on $\lambda(\mathcal{Q})$.

Let $G=(V,E)$ be a $k$-uniform hypergraph with maximum degree being $d>0$, and $\mathcal{A}$ and $\mathcal{Q}$ be the adjacency tensor and the signless Laplacian tensor of $G$ respectively. Then

Proof. The first inequality follows from [17, Corollary 12]. For the second, by [17, Theorem 11], we have that

Consequently, the second inequality follows. $\Box$

Let $G=(V,E)$ be a $k$-uniform regular connected hypergraph with degree $d>0$, and $\mathcal{Q}$ be its signless Laplacian tensor. Then, $\lambda(\mathcal{Q})=2d$.

Proof. Note that the vector of all ones is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $2d$. Since $\mathcal{Q}$ is weakly irreducible ([15, Lemma 3.1]), the result follows from [9, Lemmas 2.2 and 2.3]. $\Box$

The next proposition gives a tight upper bound of the largest signless Laplacian H-eigenvalues and characterizes the extreme hypergraphs.

Let $G=(V,E)$ be a $k$-uniform hypergraph and $G^{\prime}$ be a sub-hypergraph of $G$. Let $\mathcal{Q}$ and $\mathcal{Q}^{\prime}$ be the signless Laplacian tensor of $G$ and $G^{\prime}$, respectively. Then,

Furthermore, if $G^{\prime}$ and $G$ are both connected, then $\lambda(\mathcal{Q}^{\prime})=\lambda(\mathcal{Q})$ if and only if $G^{\prime}=G$. Consequently,

and equality holds if and only if $G$ is a $k$-uniform complete hypergraph.

Proof. The first conclusion follows from [21, Theorem 3.19]. The remaining follows from [21, Theorem 3.20], [18, Theorem 4] and [15, Lemma 3.1] (see also [10, Lemmas 2.2 and 2.3]) which imply that there is a unique positive H-eigenvector of $\mathcal{Q}$ and the corresponding H-eigenvalue must be $\lambda(\mathcal{Q})$ whenever $G$ is connected, and the fact that the vector of all ones is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $2{n-1\choose k-1}$ when $G$ is a complete hypergraph (Lemma 4.1). $\Box$

When $k=2$ (i.e., the usual graph), Propositions 4.1 and 4.2 reduce to the classic results in graph theory .

The next theorem gives a tight lower bound for $\lambda(\mathcal{Q})$ and characterizes the extreme hypergraphs.

Let $G=(V,E)$ be a $k$-uniform connected hypergraph with the maximum degree being $d>0$ and $\mathcal{Q}$ be the signless Laplician tensor of $G$. Then

where $\alpha_{*}\in(d-1,d]$ is the largest real root of $\alpha^{k}+(1-d)\alpha^{k-1}-d=0$, with equality holding if and only if $G$ is a hyperstar.

In this situation, the H-eigenvalue is $\lambda=1+\alpha$.

By [17, Theorem 11] and [10, Lemmas 2.2 and 2.3], or by a similar proof of Proposition 3.2, we can show that $\lambda(\mathcal{Q})\geq\lambda(\bar{\mathcal{Q}})$ with equality holding if and only if $G=\bar{G}$. Moreover, let $\alpha_{*}$ be the largest real root of the equation (8), by (8) we have

With a similar proof as Theorem 3.1, we can show that the equation in (8) has a unique real in the interval $(d-1,d]$ which is the maximum. Since $\bar{G}$ is connected, by [10, Lemmas 2.2 and 2.3] and [15, Lemma 3.1], we have that $\lambda(\bar{\mathcal{Q}})=1+\alpha_{*}$. Consequently, the results follow. $\Box$

When $G$ is a 2-uniform hypergraph, we know that $\alpha_{*}=d$, hence Theorem 4.1 reduces to $\lambda(\mathcal{Q})\geq d+1$ .

The Relation between The Largest Laplacian and Signless Laplacian H-Eigenvalues

In this section, we discuss the relationship between the largest Laplacian H-eigenvalue and the largest signless Laplacian H-eigenvalue.

The following theorem characterizes this relationship. This theorem generalizes the classical result in spectral graph theory .

Let $G=(V,E)$ be a $k$-uniform hypergraph. Let $\mathcal{L},\mathcal{Q}$ be the Laplacian and signless Laplacian tensors of $G$ respectively. Then

If furthermore $G$ is connected and $k$ is even, then

Proof. The first conclusion follows from Definition 2.1 and [17, Proposition 14].

Here the second equality follows from the fact that exactly an odd number of vertices in $e$ takes negative values for every $e\in E_{i}$. Similarly, we have for $i\in V_{2}$,

Here the second equality follows from the fact that exactly an even number of vertices in $e\setminus\{i\}$ takes negative values for every $e\in E_{i}$, and the last from the fact that $y_{i}=-x_{i}$. Thus, $\lambda(\mathcal{Q})$ is an H-eigenvalue of $\mathcal{L}$. This, together with the first conclusion, implies that $\lambda(\mathcal{L})=\lambda(\mathcal{Q})$.

Thus, all the inequalities in (9) should be equalities. By [17, Lemma 2.2] and [10, Theorem 2.1(iii)], we have that $\mathbf{y}$ is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $\lambda(\mathcal{Q})$, and it is a positive vector. Let $V_{1}:=\{i\in[n]\;|\;x_{i}>0\}$ and $V_{2}:=\{i\in[n]\;|\;x_{i}<0\}$. Then, $V_{1}\cup V_{2}=[n]$, since $\mathbf{y}$ is positive. Since $G$ is connected and nontrivial, we must have that $V_{2}\neq\emptyset$. Otherwise $\left|\left[(\mathcal{D}-\mathcal{A})\mathbf{x}^{k-1}\right]_{i}\right|<\left[(\mathcal{D}+\mathcal{A})\mathbf{y}^{k-1}\right]_{i}$, since $(\mathcal{A}\mathbf{x}^{k-1})_{i}>0$ in this situation. We also have that $V_{1}\neq\emptyset$, since otherwise $\left|\left[(\mathcal{D}-\mathcal{A})\mathbf{x}^{k-1}\right]_{i}\right|=|-d_{i}y_{i}^{k-1}+(\mathcal{A}\mathbf{y}^{k-1})_{i}|<\left[(\mathcal{D}+\mathcal{A})\mathbf{y}^{k-1}\right]_{i}$.

Moreover, since the first inequality in (9) must be an equality, we must get that for all $i\in V_{1}$,

Hence, for every $e\in E_{i}$ with $i\in V_{1}$, we must have that exactly $|e\cap V_{2}|$ is an odd number. Similarly, we can show that for every $e\in E_{i}$ with $i\in V_{2}$, we must have that exactly $|e\cap V_{1}|$ is an odd number. Consequently, $G$ is odd-bipartite by Definition 2.4. $\Box$

In the following, we give an application of Theorem 5.1.

Let $G=(V,E)$ be a $k$-uniform nontrivial hypergraph. If there is a disjoint partition of the vertex set $V$ as $V=V_{1}\cup\cdots\cup V_{s}$ such that $|V_{1}|=\cdots=|V_{s}|=k$, and

$|V_{1}\cap V_{2}|=\cdots=|V_{s-1}\cap V_{s}|=|V_{s}\cap V_{1}|=1$, and $V_{i}\cap V_{j}=\emptyset$ for the other cases,

the intersections $V_{1}\cap V_{2}$, …, $V_{s}\cap V_{1}$ are mutually different.

then $G$ is called a hypercycle. $s$ is the size of the hypercycle.

It is easy to see that a $k$-uniform hypercycle of size $s>0$ has $n=s(k-1)$ vertices, and is connected. Figure 3 (i) is an example of a $4$-uniform hypercycle of size $3$.

The next lemma says that the largest signless Laplacian H-eigenvalue of a hypercycle is easy to characterize.

Let $G=(V,E)$ be a $k$-uniform hypercycle of size $s>0$ and $\mathcal{Q}$ be its signless Laplacian tensor. Then, $\lambda(\mathcal{Q})=2+2\beta^{k-2}$ with $\beta$ being the unique positive solution of the equation $2\beta^{k}+\beta^{2}-1=0$ which is in the interval $(\frac{1}{2},1)$.

Let $x_{i}=\alpha$ whenever $i$ is an intersection of the edges of $G$ and $x_{i}=\beta$ for the others. Without loss of generality, we assume that $\alpha=1$. Then, for an intersection vertex $i$, we have that $d_{i}=2$ and

and for the other vertices $j$, we have that $d_{j}=1$ and

If there are some $\mu>0$ and $\beta>0$ such that

then $\mu=\lambda(\mathcal{Q})$ by the discussion at the beginning of this proof. We assume that (10) has a required solution pair. Then,

Let $g(\beta):=2\beta^{k}+\beta^{2}-1$. Then $g(1)>0$ and

Thus, (10) does have a solution pair with $\beta\in(\frac{1}{2},1)$ and $\mu=2+2\beta^{k-2}$. Since $\mathcal{Q}$ has a unique positive H-eigenvector ([10, Lemmas 2.2 and 2.3]), the equation $2\beta^{k}+\beta^{2}-1=0$ has a unique positive solution which is in the interval $(\frac{1}{2},1)$. Hence, the result follows. $\Box$

By Theorem 5.1 and Lemma 5.1, we can get the following corollary, which characterizes the largest Laplacian H-eigenvalue of a hypercycle when $k$ is even.

Let $k$ be even and $G=(V,E)$ be a $k$-uniform hypercycle of size $s>0$. Let $\mathcal{L}$ be its Laplacian tensor. Then, $\lambda(\mathcal{L})=2+2\beta^{k-2}$ with $\beta$ being the unique positive solution of the equation $2\beta^{k}+\beta^{2}-1=0$ which is in the interval $(\frac{1}{2},1)$.

Proof. By Theorem 5.1 and Lemma 5.1, it suffices to show that when $k$ is even, a $k$-uniform hypercycle is odd-bipartite.

Let $V=V_{1}\cup\cdots\cup V_{s}$ such that $|V_{1}|=\cdots=|V_{s}|=k$ be the partition of the vertices satisfying the hypotheses in Definition 5.1. Denote $V_{s}\cap V_{1}$ as $i_{1}$, $V_{1}\cap V_{2}$ as $i_{2}$, …, $V_{s-1}\cap V_{s}$ as $i_{s}$. For every $j\in[s]$, choose a vertex $r_{j}\in V_{j}$ such that $r_{j}\notin\{i_{1},\ldots,i_{s}\}$. Let $S_{1}:=\{r_{j}\;|\;j\in[s]\}$ and $S_{2}=V\setminus S_{1}$. Then it is easy to see that $S_{1}\cup S_{2}=V$ is an odd-bipartition of $G$ (Definition 2.4). An illustration of such a partition is shown in Figure 3 (ii).

The next proposition says that when $k$ is odd, the two H-eigenvalues cannot equal for a connected nontrivial hypergraph.

Let $k$ be odd and $G=(V,E)$ be a $k$-uniform connected nontrivial hypergraph. Let $\mathcal{L},\mathcal{Q}$ be the Laplacian and signless Laplacian tensors of $G$ respectively. Then

If $\mbox{sup}(\mathbf{x})\neq[n]$, then $\lambda(\mathcal{L})<\lambda(\mathcal{Q})$ by [10, Lemma 2.2]. Hence, in the following we assume that $\mbox{sup}(\mathbf{x})=[n]$. We prove the conclusion by contradiction. Suppose that $\lambda(\mathcal{L})=\lambda(\mathcal{Q})$. Then all the inequalities in (11) should be equalities. By [17, Theorem 11], $\mathbf{y}:=|\mathbf{x}|$ is an H-eigenvector of $\mathcal{Q}$ corresponding to the H-eigenvalue $\lambda(\mathcal{Q})$, and it is a positive vector. Similar to the proof of Proposition 5.1, we can get a bipartition of $V$ as $V=V_{1}\cup V_{2}$ with $V_{1},V_{2}\neq\emptyset$. Moreover, for all $i\in V$,

Suppose, without loss of generality, that $x_{1}>0$. Then, we have that $|e\cap V_{2}|<k-1$ is an odd number for every $e\in E_{1}$. Since $G$ is connected and nontrivial, we have that $E_{1}\neq\emptyset$. Suppose that $2\in\bar{e}\cap V_{2}$ with $\bar{e}\in E_{1}$. We have $x_{2}<0$ and

Thus, we get a contradiction. Consequently, $\lambda(\mathcal{L})<\lambda(\mathcal{Q})$. $\Box$

Combining Theorem 5.1 and Proposition 5.1, we have the following theorem.

Let $G=(V,E)$ be a $k$-uniform hypergraph. Let $\mathcal{L},\mathcal{Q}$ be the Laplacian and signless Laplacian tensors of $G$ respectively. Then

if and only if $k$ is even and $G$ is odd-bipartite.

Final Remarks

In this paper, the largest Laplacian and signless Laplacian H-eigenvalues of a uniform hypergraph are discussed. The largest signless Laplacian H-eigenvalue is the spectral radius of the signless Laplacian tensor , since the signless Laplacian tensor is a nonnegative tensor. There is sophisticated theory for the spectral radius of a nonnegative tensor. Thus, the corresponding theory for the largest signless Laplacian H-eigenvalue is clear. On the other hand, the largest Laplacian H-eigenvalue is more subtle. It can be seen that there are neat and simple characterizations for the lower bound of the largest Laplacian H-eigenvalue of an even-uniform hypergraph (Theorem 3.4). These are largely due to Lemma 3.4. While, for odd-uniform hypergraphs, the current theory is incomplete. This would be the next topic to investigate.

Acknowledgement. The authors are grateful to Prof. Jia-Yu Shao for his comments, and Prof. Xiaodong Zhang for Reference .

References