# Algebraic Connectivity Characterization of Ensemble Random Hypergraphs

Shih Yu Chang Shih Yu Chang is with the Department of Applied Data Science,
San Jose State University, San Jose, CA, U. S. A. (e-mail:
shihyu.chang@sjsu.edu).

###### Abstract

Random hypergraph is a broad concept used to describe probability
distributions over hypergraphs, which are mathematical structures with
applications in various fields, e.g., complex systems in physics, computer
science, social sciences, and network science. Ensemble methods, on the other
hand, are crucial both in physics and machine learning. In physics, ensemble
theory helps bridge the gap between the microscopic and macroscopic worlds,
providing a statistical framework for understanding systems with a vast number
of particles. In machine learning, ensemble methods are valuable because they
improve predictive accuracy, reduce overfitting, lower prediction variance,
mitigate bias, and capture complex relationships in data. However, there is
limited research on applying ensemble methods to a set of random hypergraphs.
This work aims to study the connectivity behavior of an ensemble of random
hypergraphs. Specifically, it focuses on quantifying the random behavior of
the algebraic connectivity of these ensembles through tail bounds. We utilize
Laplacian tensors to represent these ensemble random hypergraphs and establish
mathematical theorems, such as Courant-Fischer and Lieb-Seiringer theorems for
tensors, to derive tail bounds for the algebraic connectivity. We derive three
different tail bounds, i.e., Chernoff, Bennett, and Bernstein bounds, for the
algebraic connectivity of ensemble hypergraphs with respect to different
random hypergraphs assumptions.

Index terms— Random tensors, hypergraphs, tail bound, algebraic connectivity,
ensemble.

##  1 Introduction

Mathematics encompasses graph theory, a field dedicated to the examination of
graphs—mathematical constructs employed for representing pairwise
relationships among elements. In this mathematical context, a graph consists
of vertices (referred to as nodes or points) that are interlinked by edges
(also known as links or lines). To extend beyond conventional graphs, a
natural progression involves permitting edges that can establish connections
among an unrestricted number of nodes. A hypergraph is a type of graph where
hyperedges, or generalized edges, have the capability to connect not just two
vertices or nodes but rather a subset of vertices. In a hypergraph, these
edges, often referred to as hyperedges, are defined as arbitrary nonempty sets
of vertices.The utilization of hypergraphs is widespread in numerous fields in
science and engineering [1, 2].

The study of hypergraph connectivity is essential in various fields, including
mathematics, computer science, and network analysis, due to its wide-ranging
applications and significance [3]. For instance, connectivity problems help
ensure reliable data transmission, fault tolerance, and efficient routing [4].
In graph theory, the connectivity of a connected graph can be assessed through
measures like edge connectivity and vertex connectivity. However, computing
these measures can be notably challenging [5]. Fiedler introduced the concept
of algebraic connectivity, establishing a relationship between algebraic
connectivity and vertex connectivity [6]. This connection allows for the
estimation of vertex connectivity at a relatively lower computational cost.
The notion of algebraic connectivity, as proposed by Fiedler, has also been
extended to encompass directed graphs [7] and is widely deliberated in the
context of hypergraphs [8]. In their work, Hu and Qi [9] introduced a
representation of a $2m$-uniform hypergraph using tensors. They employed
$H$-eigenvalues and $Z$-eigenvalues as tools for defining the algebraic
connectivity [10]. In a related study, Cooper and Dutle delved into the
exploration of spectral hypergraph theory by utilizing adjacency tensors [11].

The term _random hypergraph_ is a broad descriptor used to denote probability
distributions across hypergraphs. Random hypergraphs are a fundamental concept
in graph theory and have applications and significance in various fields,
including physics, computer science, social sciences, and network analysis
[12]. Following examples show how random hypergraphs help us to solve problems
in wide spectrum of areas. In information technology, random hypergraphs are
used to model the internet’s topology and computer networks. Understanding
network properties can lead to better network design, routing algorithms, and
resource allocation [13]. In physics, random hypergraph structures exhibit
phase transitions, where certain properties of the hypergraph change suddenly
as parameters (such as the edge probability) vary. Understanding these phase
transitions provides insights into the emergence of network structures in
condense matters [14]. In computer science random hypergraphs are used in the
design and analysis of randomized algorithms. These algorithms use randomness
to solve problems efficiently or approximate solutions to problems that are
otherwise computationally challenging [15]. In sociology and social science,
random hypergraph models are employed to study social networks, diffusion of
information, and social influence. They help explain patterns of social
connections and behavior [16].

On the other hand, the concept of _ensemble_ is important in physics and
learning theory. In physics, particularly in statistical mechanics, ensemble
theory helps us understand and describe the behavior of large collections of
particles or systems, such as gases, solids, and liquids. It is essential
because it provides a statistical framework for dealing with systems that
involve a vast number of particles, making it infeasible to track the behavior
of each individual particle. The main reason to apply ensemble concepts to
interpret physical phenomena is that ensemble theory helps scientists to
bridge the gap between the microscopic and macroscopic worlds, making it
possible to describe and predict the behavior of large collections of
particles or systems. It is a foundational concept that underpins our
understanding of thermodynamics, statistical mechanics, and many other areas
of physics [17]. In learning theory, ensemble methods are a valuable approach
based on the following benefits. First, ensemble methods often lead to better
predictive performance compared to individual models. By combining multiple
models, they can reduce errors and increase overall accuracy. Second,
ensembles of learning models are less prone to overfitting, which occurs when
a model learns to perform well on the training data but fails to generalize to
new, unseen data. Ensembles can generalize better because they capture diverse
patterns and reduce the risk of modeling noise. Third, ensemble methods can
reduce the variance of predictions. This is particularly beneficial when
dealing with noisy or uncertain data. Fourth, ensembles can mitigate bias
present in individual models. By combining models with different biases,
ensembles can provide a more balanced prediction. Finally, ensembles can
capture complex relationships in the data by combining the outputs of multiple
models with different perspectives or assumptions. This makes an ensemble
approach to expand the space of representable functions for solutions [18].
However, there are not many works about considering ensemble behavior for a
set of random hypergraphs.

The purpose of this work is to study the connectivity behavior for ensembles
of random hypergraphs. Given a set of random $2m$-uniform hypergraphs,
represented by $\\{\mathscr{G}_{i}\\}_{i=1}^{N}$, we wish to quantify the
random behavior of the algebraic connectivity for ensemble of these random
hypergraphs via the tail bound of the algebraic connectivity which can be
expressed by:

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq\theta\right),$
(1)

where $\alpha(\overline{\mathscr{G}})$ is the algebraic connectivity of the
ensemble random hypergraph, represented by $\overline{\mathscr{G}}$ and
$\theta$ is a specified positive number about the degree of connectivity. The
Laplacian tensor of the ensemble random hypergraph $\overline{\mathscr{G}}$,
denoted by $\mathcal{L}_{\overline{\mathscr{G}}}$, is obtained by the
following relation:

$\displaystyle\mathcal{L}_{\overline{\mathscr{G}}}=\sum\limits_{i=1}^{N}\mathcal{L}_{\mathscr{G}_{i}},$
(2)

where $\mathcal{L}_{\mathscr{G}_{i}}$ are Laplacia tensors for uniform random
hypergraphs $\\{\mathscr{G}_{i}\\}$. The detailed notions about $2m$-uniform
hypergraphs, algebraic connectivity, Laplacian tensors are discussed in
Section 3. According to [19], the algebraic connectivity of the ensemble
random hypergraph is the $k$-th largest eigenvalue of the Laplcian tensor
$\mathcal{L}_{\overline{\mathscr{G}}}$, where $k$ is some positive integer
related to hypergraph parameters of $\overline{\mathscr{G}}$. Therefore, in
order to bound the probability provided by Eq. (1), it is equivalent to
determine the tail bound for the $k$-th largest eigenvalue for the summation
of random tensors. We establish Courant-Fischer theorem and Lieb-Seiringer
joint concavity theorem for tensors first, and apply these theorems to obtain
Chernoff, Bennett, and Bernstein tail bounds for the algebraic connectivity
$\overline{\mathscr{G}}$ under different random hypergraphs $\mathscr{G}_{i}$
assumptions.

The rest of this paper is organized as follows. Basic tensor facts and
functions of tensors are introduced in Section 2. In Section 3, we will
discuss the random hypergraph and its algebraic connectivity. In Section 4, we
will prepare the tail bounds for any $k$-th largest eigenvalue arising from
the summation of independent Hermitian random tensors. Finally, in Section 5,
we will consider different tail bounds, i.e., Chernoff, Bennett, and Bernstein
bounds, for the algebraic connectivity of ensemble hypergraphs with respect to
different random hypergraphs assumptions.

nomenclasure

Throughout this work, tensors are represented by calligraphic letters (e.g.,
$\mathcal{D}$, $\mathcal{E}$, $\mathcal{F}$, $\ldots$), respectively. Tensors
are multiarrays of values which are higher-dimensional generalizations from
vectors and matrices. Given a positive integer $N$, let
$[N]\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\\{1,2,\cdots,N\\}$. An
_order- $M$ tensor_ (or _$M$ -th order tensor_) denoted by
$\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i_{1},i_{2},\cdots,i_{M}})$, where $1\leq
i_{j}=1,2,\ldots,I_{j}$ for $j\in[M]$, is a multidimensional array containing
$I_{1}\times I_{2}\times\cdots\times I_{M}$ entries. Let
$\mathbb{C}^{I_{1}\times\cdots\times I_{M}}$ and
$\mathbb{R}^{I_{1}\times\cdots\times I_{M}}$ be the sets of the order-$M$
$I_{1}\times\cdots\times I_{M}$ tensors over the complex field $\mathbb{C}$
and the real field $\mathbb{R}$, respectively. For example,
$\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}}$ is an order-$N$
multiarray, where the first, second, …, and $M$-th dimensions have $I_{1}$,
$I_{2}$, $\ldots$, and $I_{M}$ entries, respectively. Thus, each entry of
$\mathcal{X}$ can be represented by $a_{i_{1},\cdots,i_{M}}$.

##  2 Tensor Review

In this section, we’ll offer a concise overview of tensors and probability,
essential prerequisites for our forthcoming theory elaboration. This section
is based on our previous work in [20].

###  2.1 Fundamental of Tensor

####  2.1.1 Tensor Notations

We can divide the dimensions of a tensor into two distinct sets, denoted as
$M$ and $N$ dimensions, respectively. Thus, for two tensors of order $M+N$:
$\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$ and
$\mathcal{Y}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(b_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$, as described in [20], the
operation of _tensor addition_
$\mathcal{X}+\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
J_{1}\times\cdots\times J_{N}}$ can be defined as follows:

$\displaystyle(\mathcal{X}+\mathcal{Y})_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times
j_{N}}$ $\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle a_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times j_{N}}$ (3)
$\displaystyle+b_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times j_{N}}.$

Conversely, when considering tensors
$\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$ and
$\mathcal{Y}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(b_{j_{1},\cdots,j_{N},k_{1},\cdots,k_{L}})\in\mathbb{C}^{J_{1}\times\cdots\times
J_{N}\times K_{1}\times\cdots\times K_{L}}$, as elucidated in [20], the
operation known as the _Einstein product_ (referred to simply as the _tensor
product_ in this context) denoted as
$\mathcal{X}\star_{N}\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times K_{1}\times\cdots\times K_{L}}$ can be defined as follows:

$\displaystyle(\mathcal{X}\star_{N}\mathcal{Y})_{i_{1},\cdots,i_{M},k_{1}\times\cdots\times
k_{L}}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$ (4)
$\displaystyle\sum\limits_{j_{1},\cdots,j_{N}}a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}b_{j_{1},\cdots,j_{N},k_{1},\cdots,k_{L}}.$

Please note that we will frequently condense the tensor product
$\mathcal{X}\star_{N}\mathcal{Y}$ to ”$\mathcal{X}\hskip
1.42271pt\mathcal{Y}$” for the sake of brevity in the remainder of this
document. This tensor product simplifies to standard matrix multiplication
when $L=M=N=1$. Other simplified scenarios include the tensor-vector product
($M>1$, $N=1$, and $L=0$) and the tensor-matrix product ($M>1$ and $N=L=1$).
Similar to matrix analysis, we introduce fundamental tensors and elementary
tensor operations as follows.

###### Definition 1

A tensor whose entries are all zero is called a _zero tensor_ , denoted by
$\mathcal{O}$.

###### Definition 2

An _identity tensor_ $\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{N}\times J_{1}\times\cdots\times J_{N}}$ is defined by

$\displaystyle(\mathcal{I})_{i_{1}\times\cdots\times i_{N}\times
j_{1}\times\cdots\times j_{N}}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\prod_{k=1}^{N}\delta_{i_{k},j_{k}},$ (5)

where $\delta_{i_{k},j_{k}}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}1$ if
$i_{k}=j_{k}$; otherwise
$\delta_{i_{k},j_{k}}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}0$.

To establish the concept of a _Hermitian_ tensor, we outline the operation
known as the _conjugate transpose_ (or _Hermitian adjoint_) of a tensor in the
following manner.

###### Definition 3

Given a tensor $\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$, its conjugate transpose, denoted
by $\mathcal{X}^{H}$, is defined by

$\displaystyle(\mathcal{X}^{H})_{j_{1},\cdots,j_{N},i_{1},\cdots,i_{M}}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\overline{a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}},$ (6)

where the overline notion indicates the complex conjugate of the complex
number $a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}$. If a tensor $\mathcal{X}$
satisfies $\mathcal{X}^{H}=\mathcal{X}$, then $\mathcal{X}$ is a _Hermitian
tensor_.

###### Definition 4

Given a tensor $\mathcal{U}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(u_{i_{1},\cdots,i_{M},i_{1},\cdots,i_{M}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, if

$\displaystyle\mathcal{U}^{H}\star_{M}\mathcal{U}=\mathcal{U}\star_{M}\mathcal{U}^{H}=\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}},$ (7)

then $\mathcal{U}$ is a _unitary tensor_.

In this work, the symbol $\mathcal{U}$ is resrved for a unitary tensor.

###### Definition 5

Given a _square tensor_ $\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{M}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, if there exists
$\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ such that

$\displaystyle\mathcal{X}\star_{M}\mathcal{X}=\mathcal{X}\star_{M}\mathcal{X}=\mathcal{I},$
(8)

then $\mathcal{X}$ is the _inverse_ of $\mathcal{X}$. We usually write
$\mathcal{X}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\mathcal{X}^{-1}$
thereby.

We also list other crucial tensor operations here. The _trace_ of a square
tensor is equivalent to the summation of all diagonal entries such that

$\displaystyle\mathrm{Tr}(\mathcal{X})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\sum\limits_{1\leq i_{j}\leq I_{j},\hskip
1.42271ptj\in[M]}\mathcal{X}_{i_{1},\cdots,i_{M},i_{1},\cdots,i_{M}}.$ (9)

The _inner product_ of two tensors $\mathcal{X}$,
$\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
J_{1}\times\cdots\times J_{N}}$ is given by

$\displaystyle\langle\mathcal{X},\mathcal{Y}\rangle\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\mathrm{Tr}\left(\mathcal{X}^{H}\star_{M}\mathcal{Y}\right).$ (10)

According to Eq. (10), the _Frobenius norm_ of a tensor $\mathcal{X}$ is
defined by

$\displaystyle\left\|\mathcal{X}\right\|\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\sqrt{\langle\mathcal{X},\mathcal{X}\rangle}.$ (11)

We use $\lambda_{\min}$ and $\lambda_{\max}$ to repsent the minimum and the
maximum eigenvales of a Hermitain tensor. The notation $\succeq$ is used to
indicate the semidefinite ordering of tensors. If we have
$\mathcal{X}\succeq\mathcal{Y}$, this means that the difference tensor
$\mathcal{X}-\mathcal{Y}$ is a positive semidefinite tensor.

####  2.1.2 Tensor Functions

For a tensor $\mathcal{A}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$, its eigenvalue $\lambda$ and corresponding
eigen-tensor $\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}}$ is
defined as

$\displaystyle\mathcal{A}\star_{M}\mathcal{X}$ $\displaystyle=$
$\displaystyle\lambda\mathcal{X}.$ (12)

Given a function $g:\mathbb{R}\rightarrow\mathbb{R}$, the mapping result of a
diagonal tensor by the function $g$ is to obtain another same size diagonal
tensor with diagonal entry mapped by the function $g$. Then, the function $g$
can be extended to allow a Hermitian tensor
$\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ as an input argument as

$\displaystyle g(\mathcal{X})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\mathcal{U}\star_{M}g(\Lambda)\star_{M}\mathcal{U}^{H},\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{where
$\mathcal{X}=\mathcal{U}\star_{M}\Lambda\star_{M}\mathcal{U}^{H}$.}$ (13)

The $\Lambda$ is the diagonal tensor with entries as eigenvalues.

The _spectral mapping theorem_ posits that every eigenvalue of
$g(\mathcal{X})$ corresponds to $g(\lambda)$ for some eigenvalue $\lambda$ of
$\mathcal{X}$. Additionally, based on the semidefinite ordering of tensors, we
obtain the following relationship:

$\displaystyle f(x)\geq g(x),\leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{for $x\in[a,b]$}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ f(\mathcal{X})\succeq g(\mathcal{X}),\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{for eigenvalues of $\mathcal{X}\in[a,b]$;}$ (14)

where $[a,b]$ is a real interval.

###### Definition 6

Given a square tensor $\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, the _tensor exponential_ of the
tensor $\mathcal{X}$ is defined as

$\displaystyle e^{\mathcal{X}}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\sum\limits_{k=0}^{\infty}\frac{\mathcal{X}^{k}}{k!},$ (15)

where $\mathcal{X}^{0}$ is defined as the identity tensor
$\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ and
$\mathcal{X}^{k}=\underbrace{\mathcal{X}\star_{M}\mathcal{X}\star_{M}\dots\star_{M}\mathcal{X}}_{\mbox{$k$
terms of $\mathcal{X}$}}$.

Given a tensor $\mathcal{Y}$, the tensor $\mathcal{X}$ is said to be a _tensor
logarithm_ of $\mathcal{Y}$ if $e^{\mathcal{X}}=\mathcal{Y}$

Several important properties pertain to the tensor exponential. Firstly, as
per the spectral mapping theorem, the exponential of a Hermitian tensor is
always positive-definite. Secondly, the trace exponential function, denoted as
$\mathcal{X}\rightarrow\mathrm{Tr}\exp(\mathcal{X})$, is convex. Thirdly, the
trace exponential function exhibits a monotonic behavior with respect to the
semidefinite ordering, as

$\displaystyle\mathcal{X}\succeq\mathcal{Y}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\mathrm{Tr}\exp(\mathcal{X})\geq\mathrm{Tr}\exp(\mathcal{Y}).$ (16)

For the tensor logarithm, we have the following monotone relation

$\displaystyle\mathcal{X}\succeq\mathcal{Y}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\log(\mathcal{X})\succeq\log(\mathcal{Y}).$ (17)

Moreover, the tensor logarithm is also concave, i.e., we have

$\displaystyle
t\log(\mathcal{X}_{1})+(1-t)\log(\mathcal{X}_{2})\preceq\log(t\mathcal{X}_{1}+(1-t)\mathcal{X}_{2}),$
(18)

where $\mathcal{X}_{1},\mathcal{X}_{2}$ are positive-definite tensors and
$t\in[0,1]$. The concavity of tesnor logarithm can be dervied from Hansen-
Pedersen Characterizations, see [21]

###  2.2 Tensor Moments and Cumulants

Because the expectation of a random tensor can be treated as convex
combination, expectation will preserve the semidefinite order as

$\displaystyle\mathcal{X}\succ\mathcal{Y}\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ almost surely}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mathbb{E}(\mathcal{X})\succ\mathbb{E}(\mathcal{Y}).$
(19)

From operator Jensen’s inequality [22], we also have

$\displaystyle\mathbb{E}(\mathcal{X}^{2})\succeq\left(\mathbb{E}(\mathcal{X})\right)^{2}.$
(20)

Assume we have a random Hermitian tensor $\mathcal{X}$ with existing tensor
moments of all orders, denoted as $\mathbb{E}(\mathcal{X}^{n})$ for all $n$.
In such a case, we can introduce the tensor moment-generating function,
represented as $\mathbb{M}{\mathcal{X}}(t)$, and the tensor cumulant-
generating function, represented as $\mathbb{K}_{\mathcal{X}}(t)$, for the
tensor $\mathcal{X}$ as follows:

$\displaystyle\mathbb{M}_{\mathcal{X}}(t)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\mathbb{E}e^{t\mathcal{X}},\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
}\mathbb{K}_{\mathcal{X}}(t)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\log\mathbb{E}e^{t\mathcal{X}},$ (21)

where $t\in\mathbb{R}$. Both the tensor moment-generating function and the
tensor cumulant-generating function can be expressedby power series
expansions:

$\displaystyle\mathbb{M}_{\mathcal{X}}(t)=\mathcal{I}+\sum\limits_{n=1}^{\infty}\frac{t^{n}}{n!}\mathbb{E}(\mathcal{X}^{n}),\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
}\mathbb{K}_{\mathcal{X}}(t)=\sum\limits_{n=1}^{\infty}\frac{t^{n}}{n!}\psi_{n},$
(22)

where $\psi_{n}$ is named as _tensor cumulant_. The tensor cumulant $\psi_{n}$
can be expressed as a polyomial in terms of tensor moments up to the order
$n$, for example, the first cumulant is the mean and the second cumulant is
the varaince:

$\displaystyle\psi_{1}=\mathbb{E}(\mathcal{X}),\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
}\psi_{2}=\mathbb{E}(\mathcal{X}^{2})-(\mathbb{E}(\mathcal{X}))^{2}.$ (23)

##  3 Algebraic Connectivity of A Hypergraph

In this section, we first introduce the random hypergraph concept in Section
3.1 and discuss algebraic connectivity of a hypergraph in Section 3.2.

###  3.1 Random Hypergraph

A hypergraph $\mathscr{G}=(\mathscr{V},\mathscr{E})$ is composed by two parts:
the set of vertices represented by
$\mathscr{V}=\\{V_{1},V_{2},\cdots,V_{m}\\}$, and set of hyperedges
represented by $\mathscr{E}=\\{E_{1},E_{2},\cdots,E_{n}\\}$. A hyperedge
$E_{i}$ for $i\in[n]$ is a subset of $\mathscr{V}$. A hypergraph is named as
$M$-uniform hypergraph if all its hyperedges contain the same number of
vertices, i.e., $\left|E_{i}\right|=M$ for $i\in[n]$. A conventional graph
with all edges determined by two vertices can be treated as a $2$-uniform
hypergraph. In this work, we will consider only $2M$-uniform hypergraphs.

According to the order among vertices in each $E_{i}$, we can have two types
of hypergraph: undirected hypergraph and directd hypergraph. For an undirected
hypergraph, there are no order relationships among vertices in each $E_{i}$;
for a directd hypergraph, the vertices in $E_{i}$ are devided into two parts:
the source part, denoted by $S_{i}$, and the destination part, denoted by
$D_{i}$. $E_{i}=S_{i}\bigcup D_{i}$, and $S_{i}\bigcap D_{i}=\emptyset$. We
have a weight function associated to each directed
$\mathscr{G}=(\mathscr{V},\mathscr{E})$ by assigning each $E_{i}$ a real
value, denoted by $W_{i}$. A directed hypergraph
$\mathscr{G}=(\mathscr{V},\mathscr{E})$ with such weights assignments to each
edge $E_{i}$ is named as a weighted hypergraph. For any two edges
$E_{i},E_{j}$ from a weighted $2M$-uniform hypergraph with $E_{i}=E_{j}$,
$S_{i}=D_{j}$ and $D_{i}=S_{j}$, if $w_{i}=w_{j}$, such hypergraph is named as
a _weighted symmetric $2M$-uniform hypergraph_. If all weights $E_{i}$ of a
weighted symmetric $2M$-uniform hypergraph are random variables, this
hypergraph is called by _random weighted symmetric $2M$-uniform hypergraph_.
The proposed random weighted symmetric $2M$-uniform hypergraph is the
extension of even order uniform hypergraphs (deterministic hypergraphs)
discussed in [19]. To the end of this work, we will focus on discussing random
hypergraphs of this type: random weighted symmetric $2M$-uniform hypergraph.

For a random weighted symmetric $2M$-uniform hypergraph
$\mathscr{G}=(\mathscr{V},\mathscr{E})$ with $m$ vertices, we define its
adjacency tensor, represented by
$\mathcal{A}_{\mathscr{G}}=[a_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}]\in\mathbb{R}^{m^{2M}}$,
as follows:

$\displaystyle a_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$ $\displaystyle
w_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}},$ (24)

where $w_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}$ is the weight for edges
between the source part with vertices $\\{i_{1},\cdots,i_{m}\\}$ and the
destination part with vertices $\\{j_{1},\cdots,j_{m}\\}$. The degree tensor,
represented by
$\mathcal{D}_{\mathscr{G}}=[d_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}]\in\mathbb{R}^{m^{2M}}$,
is defined by

$\displaystyle d_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\sum\limits_{j_{1},\cdots,j_{M}}^{m}a_{i_{1},\cdots,i_{m},j_{1},\cdots,j_{m}}.$
(25)

Then, the Laplacian tensor for this graph $\mathscr{G}$, represented by
$\mathcal{L}_{\mathscr{G}}\in\mathbb{R}^{m^{2M}}$, is defined by

$\displaystyle\mathcal{L}_{\mathscr{G}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\mathcal{D}_{\mathscr{G}}-\mathcal{A}_{\mathscr{G}}.$ (26)

###  3.2 Algebraic Connectivity of A Hypergraph

Before defining the algebraic connectivity for a hypergraph, we say that edges
$(E_{1},E_{2},\cdots,E_{n})$ form a $M$-path if we have

$\displaystyle\left|E_{i}\bigcap E_{i+1}\right|=M,$ (27)

where $i\in[n-1]$; and we also have

$\displaystyle E_{i}\bigcap E_{i+1}\bigcap E_{i+2}=\emptyset,$ (28)

where $i\in[n-2]$. We say that a given $\mathscr{G}$ is $M$-connected, i.e.,
for any $\\{i_{1},\cdots,i_{M}\\}\subset\mathscr{V}$, and
$\\{j_{1},\cdots,j_{M}\\}\subset\mathscr{V}$, there exists an $M$-path from
$\\{i_{1},\cdots,i_{M}\\}$ to $\\{j_{1},\cdots,j_{M}\\}$.

From Eq. (2) in [19], the algebraic connectivity for a hypergrah
$\mathscr{G}$, denoted by $\alpha(\mathscr{G})$, is defined as follows:

$\displaystyle\alpha(\mathscr{G})$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\min\limits_{\left\|\mathcal{X}\right\|,\mathcal{X}\perp\mathcal{E}}\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{L}_{\mathscr{G}}\star_{M}\mathcal{X},$
(29)

where $\mathcal{E}$ is the subspace of $\mathbb{R}^{m^{M}}$ spanned by eigen-
tensors corresponding to the following two cases of zero eigenvalues:

  1. 1.

All-one tensor with dimension $m^{M}\times 1$.

  2. 2.

Within the adjacency tensor, duplicate indices result in a zero-filled section
in the tensor $\mathcal{A}_{\mathscr{G}}$.

According to Theorem 3.2 in [19] and the assumption that $m>M$, if a
hypergraph $\mathscr{G}$ is a $M$-connected hypergraph, then we have

$\displaystyle\alpha(\mathscr{G})\geq 0.$ (30)

Moreover, the algebraic connectivity $\alpha(\mathscr{G})$ is the
$\left(\frac{m!}{(m-M)!}-1\right)$-th largest eigenvalue of
$\mathcal{L}_{\mathscr{G}}$ from Lemma 3.1 in [19].

##  4 Tail Bounds for $k$-th Largest Eigenvalue

In this section, we establish a universal upper limit for the tail
probabilities of any $k$-th largest eigenvalue arising from the summation of
independent Hermitian random tensors. We begin with the Courant-Fischer
theorem for tensors. For notational simplicity, we define
$\mathbb{I}_{M}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\prod\limits_{i=1}^{M}I_{i}$.

######  Theorem 1 (Courant-Fischer Theorem for Tensors)

Let $\mathcal{A}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$ be a Hermitian tensor with eigenvalues
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{\mbox{\tiny$\mathbb{I}_{M}$}}$
and corresponding orthnormal eigen-tensors
$\mathcal{U}_{1},\mathcal{U}_{2},\cdots,\mathcal{U}_{\mbox{\tiny$\mathbb{I}_{M}$}}$.
Spaces $S_{k}$ and $T_{k}$ are obtained by spanning via eigen-tensors
$\mathcal{U}_{j}$ for $j\in\left[\mathbb{I}_{M}\right]$ with dimensions $k$
and $\left(\mathbb{I}_{M}-k+1\right)$, respectively. Then, we have

$\displaystyle\lambda_{k}$ $\displaystyle=_{1}$
$\displaystyle\max\limits_{\begin{subarray}{c}S_{k}\subseteq\mathbb{C}^{I_{1}\times\cdots
I_{M}}\\\ \dim(S_{k})=k\end{subarray}}\min\limits_{\mathcal{X}\in
S_{k}}\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}$
(31) $\displaystyle=_{2}$
$\displaystyle\min\limits_{\begin{subarray}{c}T_{k}\subseteq\mathbb{C}^{I_{1}\times\cdots
I_{M}}\\\
\dim(T_{k})=\left(\left(\mathbb{I}_{M}\right)-k+1\right)\end{subarray}}\max\limits_{\mathbf{X}\in
T_{k}}\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}.$

Proof: We will just prove the identity $=_{1}$ in Eq. (31). The other identity
$=_{2}$ in Eq. (31) can be proved similarly.

We first show that $\lambda_{k}$ is achievable. As $S_{k}$ is the space
spanned by eigen-tensors
$\mathcal{U}_{1},\mathcal{U}_{2},\cdots,\mathcal{U}_{k}$. For every
$\mathbf{X}\in S_{k}$, we can express $\mathcal{X}$ as

$\displaystyle\mathbf{X}$ $\displaystyle=$
$\displaystyle\sum\limits_{j=1}^{k}c_{j}\mathcal{U}_{j}.$ (32)

Then, we have

$\displaystyle\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}$
$\displaystyle=$
$\displaystyle\frac{\sum\limits_{j=1}^{k}\lambda_{j}c_{j}^{2}}{c_{j}^{2}}$
(33) $\displaystyle\geq$
$\displaystyle\frac{\sum\limits_{j=1}^{k}\lambda_{k}c_{j}^{2}}{c_{j}^{2}}=\lambda_{k}.$

To verify that this is the maximum eigenvalue, as $T_{k}$ is the space spanned
by
$\mathcal{U}_{k},\mathcal{U}_{k+1},\cdots,\mathcal{U}_{\mbox{\tiny$\mathbb{I}_{M}$}}$,
for any $S_{k}$ with dimension $k$ the intersection of $S_{k}$ with $T_{k}$ is
non-empty. Then, we also have

$\displaystyle\min\limits_{\mathcal{X}\in
S_{k}}\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}$
$\displaystyle\leq$ $\displaystyle\min\limits_{\mathcal{X}\in S_{k}\bigcap
T_{k}}\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}.$
(34)

Any such $\mathcal{X}$ can be expressed as

$\displaystyle\mathcal{X}$ $\displaystyle=$
$\displaystyle\sum\limits_{j=k}^{\mathbb{I}_{M}}c_{j}\mathcal{U}_{j},$ (35)

then, we have

$\displaystyle\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}$
$\displaystyle=$
$\displaystyle\frac{\sum\limits_{j=k}^{\mathbb{I}_{M}}\lambda_{j}c_{j}^{2}}{c_{j}^{2}}$
(36) $\displaystyle\leq$
$\displaystyle\frac{\sum\limits_{j=k}^{\mathbb{I}_{M}}\lambda_{k}c_{j}^{2}}{c_{j}^{2}}=\lambda_{k}.$

Therefore, all subspace of $S_{k}$ with dimension $k$, we have

$\displaystyle\min\limits_{\mathcal{X}\in
S_{k}}\frac{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{A}\star_{M}\mathcal{X}}{\mathcal{X}^{\mathrm{T}}\star_{M}\mathcal{X}}$
$\displaystyle\leq$ $\displaystyle\lambda_{k}.$ (37)

This theorem is proved since $\lambda_{k}$ is achievable and is the maximum
eigenvalue. $\hfill\Box$

We use $\mathcal{U}_{(k)}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times
I_{1}\times\cdots I_{M}}$ to represent a projection tensor to the space with
dimension $k$, i.e., $\mathcal{U}_{(k)}\star_{M}\mathcal{X}$ will be a tensor
spanned by $k$ eigen-tensors of $\mathcal{X}$ and
$\mathcal{U}_{(k)}^{H}\star_{M}\mathcal{U}_{(k)}\preceq\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots
I_{M}\times I_{1}\times\cdots I_{M}}$.

According to Theorem 1, we can have the following lemma about the $k$-th
largest eigenvalue of a random Hermitian tensor.

###### Lemma 1

Let $\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$ be a random Hermitian tensor, and $k\in[\mathbb{I}_{M}]$. For any
$\theta\in\mathbb{R}$, we have

$\displaystyle\mathrm{Pr}\left(\lambda_{k}\left(\mathcal{X}\right)\geq\theta\right)$
$\displaystyle\leq$
$\displaystyle\inf\limits_{t>0}\min\limits_{\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}}\left[e^{-t\theta}\mathbb{E}\mathrm{Tr}\exp\left(t\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}^{H}\star_{M}\mathcal{X}\star_{M}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}\right)\right].$
(38)

Proof: Because we have

$\displaystyle\mathrm{Pr}\left(\lambda_{k}\left(\mathcal{X}\right)\geq\theta\right)$
$\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(e^{\lambda_{k}\left(t\mathcal{X}\right)}\geq
e^{t\theta}\right)$ (39) $\displaystyle\leq_{2}$ $\displaystyle
e^{-t\theta}\mathbb{E}e^{\lambda_{k}\left(t\mathcal{X}\right)}$
$\displaystyle=_{3}$ $\displaystyle
e^{-t\theta}\mathbb{E}\exp\left(\min\limits_{\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}}\lambda_{\max}\left(t\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}^{H}\star_{M}\mathcal{X}\star_{M}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}\right)\right)$
$\displaystyle\leq_{4}$
$\displaystyle\min\limits_{\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}}\mathbb{E}\lambda_{\max}\left(\exp\left(t\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}^{H}\star_{M}\mathcal{X}\star_{M}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}\right)\right)$
$\displaystyle\leq_{5}$
$\displaystyle\min\limits_{\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}}\mathbb{E}\mathrm{Tr}\left(\exp\left(t\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}^{H}\star_{M}\mathcal{X}\star_{M}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}\right)\right),$

where $=_{1}$ comes from monotonicity of the exponential function with respect
to a real variable; $\leq_{2}$ comes from Markov inequality; $=_{3}$ comes
from Theorem 1; $\leq_{4}$ comes from Jensen’s inequality, and $\leq_{5}$
comes from that the largest eigenvalue is smaller than its trace due to that
the exponential of a Hemitian tensor is positive definite. This lemma is
proved. $\hfill\Box$

Below, we will present Lieb-Seiringer concavity theorem for tensors, which
will be used to extend the subadditivity lemma of tensor cumulant-generating
functions for the random tensor operated by projection tensors, see Lemma 4 in
[20].

######  Theorem 2 (Lieb-Seiringer Joint Concavity for Tensors)

Let $\mathcal{H}$ be a Hermitian tensor operating on a finite dimensional
Hilbert space $\mathfrak{H}$, and $\mathcal{A}_{n}$ be positive-definite
tensors, where $1\leq n\leq N$. If we have

$\displaystyle\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{U}_{i}\preceq\mathcal{I}_{\mathcal{H}},$
(40)

where $\mathcal{U}_{i}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$, and $\mathcal{I}_{\mathcal{H}}$ is the
identity tensor assoicated to the Hilbert space $\mathfrak{H}$. The following
mapping

$\displaystyle\left(\mathcal{A}_{1},\cdots,\mathcal{A}_{N}\right)\rightarrow\mathrm{Tr}_{\mathfrak{H}}\exp\left(\mathcal{H}+\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\left(\log\mathcal{A}_{i}\right)\star_{M}\mathcal{U}_{i}\right)$
(41)

is jointly concave.

Proof: We may assume that Eq. (40) is the identity. Since if
$\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{U}_{i}\prec\mathcal{I}_{\mathcal{H}}$,
we can add one more term
$\mathcal{U}_{N+1}=\left(\mathcal{I}_{\mathfrak{H}}-\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{U}_{i}\right)^{1/2}$
with $\mathcal{A}_{N+1}=\mathcal{I}_{\mathcal{H}}$.

We consider the following three transformations with respect to tensors
$\mathcal{H},\mathcal{U}_{i}$ and $\mathcal{A}_{i}$:

$\displaystyle\tilde{\mathcal{H}}_{i,j}$ $\displaystyle=$
$\displaystyle\frac{\delta_{i,j}}{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{H}\star_{M}\mathcal{U}_{i},$
$\displaystyle\tilde{\mathcal{P}}_{i,j}$ $\displaystyle=$
$\displaystyle\mathcal{U}_{i}\star_{M}\mathcal{U}^{H}_{j},$
$\displaystyle\tilde{\mathcal{A}}_{i,j}$ $\displaystyle=$
$\displaystyle\delta_{i,j}\mathcal{A}_{i},$ (42)

where $\delta_{i,j}$ is a Kronecker delta function with respect to indices
$i\in[N]$ and $j\in[N]$. Note that transformed tensors
$\tilde{\mathcal{H}}_{i,j},\tilde{\mathcal{P}}_{i,j}$ and
$\tilde{\mathcal{A}}_{i,j}$ are tensors operated to another Hilbert space
$\mathfrak{H}\otimes\mathbb{C}^{N\times N}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\tilde{\mathfrak{H}}$. Therefore, tensors
$\tilde{\mathcal{H}},\tilde{\mathcal{P}}$ and $\tilde{\mathcal{A}}$ are with
dimensions $\mathbb{C}^{M\times I_{1}\times\cdots\times I_{M}\times M\times
I_{1}\times\cdots\times I_{M}}$. Besides, we also have
$\tilde{\mathcal{P}}_{i,j}=\tilde{\mathcal{P}}^{H}_{i,j}$ and
$\tilde{\mathcal{P}}_{i,j}=\tilde{\mathcal{P}}^{2}_{i,j}$ since
$\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{U}_{i}=\mathcal{I}_{\mathcal{H}}$.

From Theorem 7 in [20] and any $r\in\mathbb{R}$, we have the following jointly
concave map:

$\displaystyle\left(\mathcal{A}_{1},\cdots,\mathcal{A}_{N}\right)\rightarrow\mathrm{Tr}_{\tilde{\mathfrak{H}}}\exp\left(-r\left(\mathcal{I}_{\tilde{\mathfrak{H}}}-\tilde{\mathcal{P}}\right)+\tilde{\mathcal{H}}+\log\tilde{\mathcal{A}}\right),$
(43)

where $\mathcal{I}_{\tilde{\mathfrak{H}}}$ is the identity tensor in the space
$\tilde{\mathfrak{H}}$. By taking $r\rightarrow\infty$, Eq. (43) can be
reduced as

$\displaystyle\left(\mathcal{A}_{1},\cdots,\mathcal{A}_{N}\right)\rightarrow\mathrm{Tr}_{\tilde{\mathcal{P}}\tilde{\mathfrak{H}}}\exp\left(\tilde{\mathcal{P}}\star_{M+1}\left(\tilde{\mathcal{H}}+\log\tilde{\mathcal{A}}\right)\star_{M+1}\tilde{\mathcal{P}}\right).$
(44)

By considering the map
$\mathcal{V}:\mathfrak{H}\rightarrow\tilde{\mathcal{P}}\tilde{\mathfrak{H}}$
defined by

$\displaystyle\left(\mathcal{V}\left(\mathcal{X}\right)\right)_{i}$
$\displaystyle=$ $\displaystyle\mathcal{U}_{i}\star_{M}\mathcal{X},$ (45)

and the relation of
$\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\mathcal{U}_{i}=\mathcal{I}_{\mathcal{H}}$,
we know that the map $\mathcal{V}$ is a unitary map. Then, we have

$\displaystyle\mathcal{V}^{H}\star_{M}\left(\tilde{\mathcal{P}}\star_{M+1}\left(\tilde{\mathcal{H}}+\log\tilde{\mathcal{A}}\right)\star_{M+1}\tilde{\mathcal{P}}\right)\star_{M}\mathcal{V}$
$\displaystyle=$
$\displaystyle\mathcal{H}+\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\left(\log\mathcal{A}_{i}\right)\star_{M}\mathcal{U}_{i}.$
(46)

Therefore, we have

$\displaystyle\mathrm{Tr}_{\tilde{\mathcal{P}}\tilde{\mathcal{H}}}\exp\left(\tilde{\mathcal{P}}\star_{M+1}\left(\tilde{\mathcal{H}}+\log\tilde{\mathcal{A}}\right)\star_{M+1}\tilde{\mathcal{P}}\right)$
$\displaystyle=$
$\displaystyle\mathrm{Tr}_{\mathcal{H}}\exp\left(\mathcal{H}+\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{i}\star_{M}\left(\log\mathcal{A}_{i}\right)\star_{M}\mathcal{U}_{i}\right)$
(47)

This complets the proof from Eq. (44). $\hfill\Box$

Remark: We have to provide the following comments about Theorem 2:

  1. 1.

Our Theorem 2 extends Theorem 3 in [23] to tensors by modifying the transforms
provided by Eq. (4), which works for both invertible and noninvertible tensors
$\mathcal{U}_{n}$. The original transformations used by the proof in Theorem 3
require tesors $\mathcal{U}_{n}$ to be invertible in [23].

  2. 2.

Proposition 3.1 utilizes Theorem 3 [24] directly, however, the dimension of
the matrix $\bm{V}$ used by Proposition 3.1 does not satisfy the requirement
by Theorem 3 in [23] since $\bm{V}^{H}\bm{V}=\bm{I}_{k}$ (identity $k\times k$
matrix), which is not the identity of the original Hilbert space $\bm{I}_{n}$
(The notations used here adopts from Theorem 3 [24]).

  3. 3.

Similar to [24], we also utilize Courant-Fischer theorem and Lieb-Seiringer
joint concavity theorem to establish the tail bounds. However, our work
extends the settings from matrices to tensors.

The following lemma is the subadditivity tensor cumulant-generating functions
for the random tensor operated by projection tensors.

###### Lemma 2

Given $N$ indepedent Hermitian random tensors
$\mathcal{X}_{i}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$, and $N$ deterministic Hermitian random tensors
$\mathcal{A}_{i}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$ that satisfy

$\displaystyle\mathbb{E}\exp(\mathcal{X}_{i})\preceq\exp(\mathcal{A}_{i}).$
(48)

Pick $k\in[\mathbb{I}_{M}]$, and let
$\mathcal{U}_{(k)}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times
I_{1}\times\cdots I_{M}}$ be a projection tensor. Then, we have

$\displaystyle\mathbb{E}\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{X}_{i}\star_{M}\mathcal{U}_{(k)}\right)$
$\displaystyle\leq$
$\displaystyle\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{A}_{i}\star_{M}\mathcal{U}_{(k)}\right).$
(49)

Proof: Let $\mathbb{E}_{k}$ be the expectation on the first $k$ random tensor
from $\mathcal{X}_{1}$ to $\mathcal{X}_{k}$, then we have

$\displaystyle\mathbb{E}\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{X}_{i}\star_{M}\mathcal{U}_{(k)}\right)$
(50) $\displaystyle=$
$\displaystyle\mathbb{E}_{0}\cdots\mathbb{E}_{N-1}\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N-1}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{X}_{i}\star_{M}\mathcal{U}_{(k)}+\mathcal{U}^{H}_{(k)}\star_{M}\log
e^{\mathcal{X}_{N}}\star_{M}\mathcal{U}_{(k)}\right)$ $\displaystyle\leq_{1}$
$\displaystyle\mathbb{E}_{0}\cdots\mathbb{E}_{N-2}\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N-1}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{X}_{i}\star_{M}\mathcal{U}_{(k)}+\mathcal{U}^{H}_{(k)}\star_{M}\log\mathbb{E}e^{\mathcal{X}_{N}}\star_{M}\mathcal{U}_{(k)}\right)$
$\displaystyle\leq_{2}$
$\displaystyle\mathbb{E}_{0}\cdots\mathbb{E}_{N-2}\mathrm{Tr}\exp\left(\sum\limits_{i=1}^{N-1}\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{X}_{i}\star_{M}\mathcal{U}_{(k)}+\mathcal{U}^{H}_{(k)}\star_{M}\mathcal{A}_{N}\star_{M}\mathcal{U}_{(k)}\right),$

where $=_{1}$ comes from Theorem 2 and Jensen’s inequality, and $=_{2}$ comes
from the condition provided by Eq. (48). This lemma is proved by repeating the
inequality relation with respect to the argument $i$ given by Eq. (50).
$\hfill\Box$

We are ready to present the main result of this section.

###### Theorem 3

Given $N$ indepedent Hermitian random tensors
$\mathcal{X}_{i}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$, and $N$ deterministic Hermitian random tensors
$\mathcal{A}_{i}\in\mathbb{C}^{I_{1}\times\cdots I_{M}\times I_{1}\times\cdots
I_{M}}$ that satisfy

$\displaystyle\mathbb{E}\exp(t\mathcal{X}_{i})\preceq\exp(f(t)\mathcal{A}_{i}),$
(51)

where $f:(0,\infty)\rightarrow[0,\infty)$ and $i\in[N]$. Then, for all
$\theta\in\mathbb{R}$, we have

$\displaystyle\mathrm{Pr}\left(\lambda_{k}\left(\sum\limits_{i=1}^{N}\right)\geq\theta\right)$
(52) $\displaystyle\leq$
$\displaystyle\inf\limits_{t>0}\min\limits_{\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}}\left[e^{-t\theta}\mathrm{Tr}\exp\left(f(t)\sum\limits_{i=1}^{N}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}^{H}\star_{M}\mathcal{A}_{i}\star_{M}\mathcal{U}_{\left(\mathbb{I}_{M}-k+1\right)}\right)\right]$

Proof: By combining Lemma 1 and Lemma 2. $\hfill\Box$

##  5 Algebraic Connectivity of Ensemble Random Hypergraphs

According to Eq. (29), the value of the algebraic connectivity for a
hypergraph $\mathscr{G}$ indicates the degree of connectivity within the
entire hypergraph. In this section, we will consider different tail bounds for
the algebraic connectivity of ensemble hypergraphs with respect to different
random hypergraphs assumptions. These tail bounds are Chernoff, Bennett, and
Bernstein bounds, which will be discussed in Sections 5.1, 5.2, and 5.3,
respectively.

###  5.1 Chernoff Bounds for Algebraic Connectivity of Ensemble Hypergraphs

In this section, we will consider the algebraic connectivity for ensembles of
random hypergraphs whose Laplacian tensors are positive semidefinite tensors.

###### Theorem 4

Given $N$ independent random hypergraphs, $\\{\mathscr{G}_{i}\\}$, whose
Laplacian tensors, $\\{\mathcal{L}_{i}\in\mathbb{R}^{m^{2M}}\\}$ for
$i\in[N]$, are positive semidefinite tensors. We define a positive number
$\nu_{\overline{\mathscr{G}}}$ by

$\displaystyle\nu_{\overline{\mathscr{G}}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathbb{E}\mathcal{L}_{i}\right).$
(53)

Then, we have the following bounds for the algebraic connectivity of the
ensemble hypergraph $\overline{\mathscr{G}}$:

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq(1+\theta)\nu_{\overline{\mathscr{G}}}\right)\leq\left(m^{M}-\frac{m!}{(m-M)!}+2\right)\left[\frac{e^{\theta}}{(1+\theta)^{1+\theta}}\right]^{\nu_{\overline{\mathscr{G}}}},$
(54)

where $\theta>1$; and

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\leq(1+\theta)\nu_{\overline{\mathscr{G}}}\right)\leq\left(\frac{m!}{(m-M)!}-1\right)\left[\frac{e^{-\theta}}{(1-\theta)^{1-\theta}}\right]^{\nu_{\overline{\mathscr{G}}}},$
(55)

where $0\leq\theta<1$.

Proof: We define projection tensors $\mathcal{U}_{+}$ and $\mathcal{U}_{-}$ as

$\displaystyle\mathcal{U}_{+}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\mathcal{U}_{\left(m^{M}-\frac{m!}{(m-M)!}+2\right)},$
$\displaystyle\mathcal{U}_{-}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\mathcal{U}_{\left(\frac{m!}{(m-M)!}-1\right)}.$ (56)

Then, we have

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq(1+\theta)\nu_{\overline{\mathscr{G}}}\right)$
$\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)\geq(1+\theta)\nu_{\overline{\mathscr{G}}}\right)$
(57) $\displaystyle\leq_{2}$
$\displaystyle\inf\limits_{t>0}e^{-t(1+\theta)\nu_{\overline{\mathscr{G}}}}\mathrm{Tr}\exp\left((e^{t}-1)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}_{i}\star_{M}\mathcal{U}_{+}\right)$
$\displaystyle\leq_{3}$
$\displaystyle\inf\limits_{t>0}e^{-t(1+\theta)\nu_{\overline{\mathscr{G}}}}\left(m^{M}-\frac{m!}{(m-M)!}+2\right)$
$\displaystyle\cdot\lambda_{\max}\left(\exp\left((e^{t}-1)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}_{i}\star_{M}\mathcal{U}_{+}\right)\right)$
$\displaystyle=_{4}$
$\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)\inf\limits_{t>0}\exp\left[\left(e^{t}-1-t(1+\theta)\right)\nu_{\overline{\mathscr{G}}}\right],$

where $=_{1}$ comes from the fact that the algebraic connectivity
$\alpha(\overline{\mathscr{G}})$ is the $\left(\frac{m!}{(m-M)!}-1\right)$-th
largest eigenvalue of $\sum\limits_{i=1}^{N}\mathcal{L}_{i}$ from Lemma 3.1 in
[19], $\leq_{2}$ comes from Theorem 3 and Lemma 6 in [20], $\leq_{3}$ comes
from the fact that the trace can be bounded by the maximum eigenvalue and the
dimensions size, and $=_{4}$ comes from Theorem 1 and Eq. (53). Eq. (54) is
proved by applying the minimizer $t=\log(1+\theta)$ at the term
$\exp\left[\left(e^{t}-1-t(1+\theta)\right)\nu_{\overline{\mathscr{G}}}\right]$.

Let us prove Eq. (55). We have

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\leq(1-\theta)\nu_{\overline{\mathscr{G}}}\right)$
$\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)\leq(1-\theta)\nu_{\overline{\mathscr{G}}}\right)$
(58) $\displaystyle=_{2}$
$\displaystyle\mathrm{Pr}\left(\lambda_{m^{M}-\frac{m!}{(m-M)!}+2}\left(-\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)\geq-(1-\theta)\nu_{\overline{\mathscr{G}}}\right)$
$\displaystyle\leq_{3}$
$\displaystyle\inf\limits_{t>0}e^{t(1-\theta)\nu_{\overline{\mathscr{G}}}}\mathrm{Tr}\exp\left((1-e^{-t})\sum\limits_{i=1}^{N}\mathcal{U}_{-}^{H}\star_{M}(-\mathbb{E}\mathcal{L}_{i})\star_{M}\mathcal{U}_{-}\right)$
$\displaystyle\leq_{4}$
$\displaystyle\inf\limits_{t>0}e^{t(1-\theta)\nu_{\overline{\mathscr{G}}}}\left(\frac{m!}{(m-M)!}-1\right)$
$\displaystyle\cdot\lambda_{\min}\left(\exp\left((e^{-t}-1)\sum\limits_{i=1}^{N}\mathcal{U}_{-}^{H}\star_{M}\mathbb{E}\mathcal{L}_{i}\star_{M}\mathcal{U}_{-}\right)\right)$
$\displaystyle=_{5}$
$\displaystyle\left(\frac{m!}{(m-M)!}-1\right)\inf\limits_{t>0}\exp\left[\left(t(1-\theta)-1+e^{-t}\right)\nu_{\overline{\mathscr{G}}}\right],$

where $=_{1}$ comes from the fact that the algebraic connectivity
$\alpha(\overline{\mathscr{G}})$ is the $\left(\frac{m!}{(m-M)!}-1\right)$-th
largest eigenvalue of $\sum\limits_{i=1}^{N}\mathcal{L}_{i}$ from Lemma 3.1 in
[19], $=_{2}$ comes from the eigenvalues duality fact that
$\lambda_{\left(\frac{m!}{(m-M)!}-1\right)}\left(-\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)=-\lambda_{\left(m^{M}-\frac{m!}{(m-M)!}+2\right)}\left(\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)$,
$\leq_{3}$ comes from Theorem 3 and Lemma 6 in [20], $\leq_{4}$ comes from the
fact that the trace can be bounded by the maximum eigenvalue and the
dimensions size, and $=_{5}$ comes from Theorem 1 and Eq. (53). Then, Eq. (55)
is proved by applying the minimizer $t=-\log(1-\theta)$ at the term
$\exp\left[\left(t(1-\theta)-1+e^{-t}\right)\nu_{\overline{\mathscr{G}}}\right]$.
$\hfill\Box$

###  5.2 Bennett Bounds for Algebraic Connectivity of Ensemble Hypergraphs

In this section, we will consider the algebraic connectivity for ensemble of
random hypergraphs whose Laplacian tensors are Hermitian.

###### Theorem 5

Given $N$ independent random hypergraphs, $\\{\mathscr{G}_{i}\\}$, whose
Laplacian tensors, $\\{\mathcal{L}_{i}\in\mathbb{R}^{m^{2M}}\\}$ for
$i\in[N]$, are Hermitian tensors with $\mathbb{E}\mathcal{L}_{i}=\mathcal{O}$
and $\lambda_{\max}(\mathcal{L}_{i})\leq 1$ almost surely. We define a
positive number $\sigma^{2}_{\overline{\mathscr{G}}}$ by

$\displaystyle\sigma^{2}_{\overline{\mathscr{G}}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathbb{E}\mathcal{L}^{2}_{i}\right).$
(59)

Then, we have the following bounds for the algebraic connectivity of the
ensemble hypergraph $\overline{\mathscr{G}}$:

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq\theta\right)$
$\displaystyle\leq$
$\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)\exp(\theta)\left(1+\frac{\theta}{\sigma^{2}_{\overline{\mathscr{G}}}}\right)^{-(\theta+\sigma^{2}_{\overline{\mathscr{G}}})}.$
(60)

Proof: We define projection tensors $\mathcal{U}_{+}$as

$\displaystyle\mathcal{U}_{+}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\mathcal{U}_{\left(m^{M}-\frac{m!}{(m-M)!}+2\right)}.$ (61)

Then, we have

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq\theta\right)$
$\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)\geq\theta\right)$
(62) $\displaystyle\leq_{2}$
$\displaystyle\inf\limits_{t>0}e^{-t\theta}\mathrm{Tr}\exp\left(\left(e^{t}-t-1\right)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}^{2}_{i}\star_{M}\mathcal{U}_{+}\right)$
$\displaystyle\leq_{3}$ $\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)$
$\displaystyle\cdot\inf\limits_{t>0}\left[e^{-t\theta}\lambda_{\max}\left(\exp\left((e^{t}-t-1)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}^{2}_{i}\star_{M}\mathcal{U}_{+}\right)\right)\right]$
$\displaystyle=_{4}$
$\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)\inf\limits_{t>0}e^{(e^{t}-t-1)\sigma^{2}_{\overline{\mathscr{G}}}-t\theta}$

where $=_{1}$ comes from the fact that the algebraic connectivity
$\alpha(\overline{\mathscr{G}})$ is the $\left(\frac{m!}{(m-M)!}-1\right)$-th
largest eigenvalue of $\sum\limits_{i=1}^{N}\mathcal{L}_{i}$ from Lemma 3.1 in
[19], $\leq_{2}$ comes from Theorem 3 and Lemma 7 in [20], $\leq_{3}$ comes
from the fact that the trace can be bounded by the maximum eigenvalue and the
dimensions size, and $=_{4}$ comes from Theorem 1 and Eq. (59). Eq. (60) is
proved by applying the minimizer
$t=\log(1+\theta/\sigma^{2}_{\overline{\mathscr{G}}})$ at the term
$(e^{t}-t-1)\sigma^{2}_{\overline{\mathscr{G}}}-t\theta$. $\hfill\Box$

###  5.3 Bernstein Bounds for Algebraic Connectivity of Ensemble Hypergraphs

In this section, we will consider the algebraic connectivity for ensembles of
random hypergraphs whose Laplacian tensors are Hermitian with subexponential
growth rate.

###### Theorem 6

Given $N$ independent random hypergraphs, $\\{\mathscr{G}_{i}\\}$, whose
Laplacian tensors, $\\{\mathcal{L}_{i}\in\mathbb{R}^{m^{2M}}\\}$ for
$i\in[N]$, are Hermitian tensors. We assume that these Laplacian random
tensors satisfy the following subexponential growth rate as:

$\displaystyle\mathbb{E}(\mathcal{L}_{i}^{p})\preceq\frac{p!\mathcal{A}_{i}^{2}}{2},$
(63)

where $p=2,3,4,\cdots,$, $\mathbb{E}(\mathcal{L}_{i})=\mathcal{O}$ and
$\mathcal{A}_{i}$ are positive-definite tensors. We also define
$\sigma^{2}_{\overline{\mathscr{G}}}$ by

$\displaystyle\sigma^{2}_{\overline{\mathscr{G}}}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathbb{E}\mathcal{L}^{2}_{i}\right).$
(64)

Then, we have

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq\theta\right)$
$\displaystyle\leq$
$\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)e^{-\frac{\theta^{2}}{2\left(\theta+\sigma^{2}_{\overline{\mathscr{G}}}\right)}}.$
(65)

Proof: We define projection tensors $\mathcal{U}_{+}$as

$\displaystyle\mathcal{U}_{+}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}$
$\displaystyle\mathcal{U}_{\left(m^{M}-\frac{m!}{(m-M)!}+2\right)}.$ (66)

Then, we have

$\displaystyle\mathrm{Pr}\left(\alpha(\overline{\mathscr{G}})\geq\theta\right)$
$\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(\lambda_{\frac{m!}{(m-M)!}-1}\left(\sum\limits_{i=1}^{N}\mathcal{L}_{i}\right)\geq\theta\right)$
(67) $\displaystyle\leq_{2}$
$\displaystyle\inf\limits_{0<t<1}e^{-t\theta}\mathrm{Tr}\exp\left(\left(\frac{t^{2}}{2(1-t)}\right)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}^{2}_{i}\star_{M}\mathcal{U}_{+}\right)$
$\displaystyle\leq_{3}$ $\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)$
$\displaystyle\cdot\inf\limits_{0<t<1}\left[e^{-t\theta}\lambda_{\max}\left(\exp\left(\left(\frac{t^{2}}{2(1-t)}\right)\sum\limits_{i=1}^{N}\mathcal{U}_{+}^{H}\star_{M}\mathbb{E}\mathcal{L}^{2}_{i}\star_{M}\mathcal{U}_{+}\right)\right)\right]$
$\displaystyle=_{4}$
$\displaystyle\left(m^{M}-\frac{m!}{(m-M)!}+2\right)\inf\limits_{0<t<1}e^{\left(\frac{t^{2}}{2(1-t)}\right)\sigma^{2}_{\overline{\mathscr{G}}}-t\theta},$

where $=_{1}$ comes from the fact that the algebraic connectivity
$\alpha(\overline{\mathscr{G}})$ is the $\left(\frac{m!}{(m-M)!}-1\right)$-th
largest eigenvalue of $\sum\limits_{i=1}^{N}\mathcal{L}_{i}$ from Lemma 3.1 in
[19], $\leq_{2}$ comes from Theorem 3 and Lemma 8 in [20], $\leq_{3}$ comes
from the fact that the trace can be bounded by the maximum eigenvalue and the
dimensions size, and $=_{4}$ comes from Theorem 1 and Eq. (64). Eq. (65) is
proved by applying the minimizer
$t=\frac{\theta}{\theta+\sigma^{2}_{\overline{\mathscr{G}}}}$ at the term
$\left(\frac{t^{2}}{2(1-t)}\right)\sigma^{2}_{\overline{\mathscr{G}}}-t\theta$.
$\hfill\Box$

## References

  * [1] H. Bunke, P. Dickinson, and M. Kraetzl, “Theoretical and algorithmic framework for hypergraph matching,” in _Image Analysis and Processing–ICIAP 2005: 13th International Conference, Cagliari, Italy, September 6-8, 2005. Proceedings 13_. Springer, 2005, pp. 463–470.
  * [2] A. Bretto and A. Bretto, “Applications of hypergraph theory: a brief overview,” _Hypergraph Theory: An Introduction_ , pp. 111–116, 2013.
  * [3] R. B. Bapat, _Graphs and matrices_. Springer, 2010, vol. 27.
  * [4] H. Gao, C. Liu, Y. Li, and X. Yang, “V2VR: reliable hybrid-network-oriented V2V data transmission and routing considering RSUs and connectivity probability,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 6, pp. 3533–3546, 2020.
  * [5] J. Chuzhoy and S. Khanna, “An o (k^3 log n)-approximation algorithm for vertex-connectivity survivable network design,” in _Proceedings of IEEE Symposium on Foundations of Computer Science_. IEEE, 2009, pp. 437–441.
  * [6] M. Fiedler, “Algebraic connectivity of graphs,” _Czechoslovak mathematical journal_ , vol. 23, no. 2, pp. 298–305, 1973.
  * [7] C. W. Wu, “Algebraic connectivity of directed graphs,” _Linear and multilinear algebra_ , vol. 53, no. 3, pp. 203–223, 2005.
  * [8] M. M. Asadi, M. Khosravi, A. G. Aghdam, and S. Blouin, “Generalized algebraic connectivity for asymmetric networks,” in _2016 American Control Conference (ACC)_. IEEE, 2016, pp. 5531–5536.
  * [9] S. Hu and L. Qi, “Algebraic connectivity of an even uniform hypergraph,” _Journal of Combinatorial Optimization_ , vol. 24, no. 4, pp. 564–579, 2012\.
  * [10] G. Li, L. Qi, and G. Yu, “The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory,” _Numerical Linear Algebra with Applications_ , vol. 20, no. 6, pp. 1001–1029, 2013.
  * [11] J. Cooper and A. Dutle, “Spectra of uniform hypergraphs,” _Linear Algebra and its applications_ , vol. 436, no. 9, pp. 3268–3292, 2012.
  * [12] G. Ghoshal, V. Zlatić, G. Caldarelli, and M. E. Newman, “Random hypergraphs and their applications,” _Physical Review E_ , vol. 79, no. 6, p. 066118, 2009.
  * [13] N. Alon, U. Arad, and Y. Azar, “Independent sets in hypergraphs with applications to routing via fixed paths,” in _International Workshop on Randomization and Approximation Techniques in Computer Science_. Springer, 1999, pp. 16–27.
  * [14] G. Ferraz de Arruda, M. Tizzani, and Y. Moreno, “Phase transitions and stability of dynamical processes on hypergraphs,” _Communications Physics_ , vol. 4, no. 1, p. 24, 2021.
  * [15] H. Fohlin, L. Kliemann, and A. Srivastav, _Randomized algorithms for mixed matching and covering in hypergraphs in 3D seed reconstruction in brachytherapy_. Springer, 2008.
  * [16] P. S. Chodrow, “Configuration models of random hypergraphs and their applications,” _arXiv_ , vol. 2019, 2019.
  * [17] C. Van den Broeck and M. Esposito, “Ensemble and trajectory thermodynamics: A brief introduction,” _Physica A: Statistical Mechanics and its Applications_ , vol. 418, pp. 6–16, 2015.
  * [18] T. G. Dietterich, “Ensemble methods in machine learning,” in _International workshop on multiple classifier systems_. Springer, 2000, pp. 1–15.
  * [19] J. Gu and Y. Wei, “Even order uniform hypergraph via the einstein product,” _AKCE International Journal of Graphs and Combinatorics_ , vol. 20, no. 2, pp. 159–167, 2023.
  * [20] S. Y. Chang and W.-W. Lin, “Convenient tail bounds for sums of random tensors,” _Taiwanese Journal of Mathematics_ , vol. 26, no. 3, pp. 571–606, 2022.
  * [21] P. Chansangiam, “A survey on operator monotonicity, operator convexity, and operator means,” _Int. J. Anal._ , pp. Art. ID 649 839, 8, 2015. [Online]. Available: https://doi.org/10.1155/2015/649839
  * [22] F. Hansen and G. K. Pedersen, “Jensen’s inequality for operators and Löwner’s theorem,” _Math. Ann._ , vol. 258, no. 3, pp. 229–241, 1981/82. [Online]. Available: https://doi.org/10.1007/BF01450679
  * [23] E. H. Lieb and R. Seiringer, “Stronger subadditivity of entropy,” _Physical Review A_ , vol. 71, no. 6, p. 062329, 2005.
  * [24] A. Gittens and J. A. Tropp, “Tail bounds for all eigenvalues of a sum of random matrices,” _arXiv preprint arXiv:1104.4513_ , 2011.