# Renewal-scaled solutions of the Kolmogorov forward equation for residual
times

Joe Klobusicky1

###### Abstract

Let $N(\tau)$ be a renewal process for holding times $\\{X_{i}\\}_{k\geq 0}$
,where $\\{X_{k}\\}_{k\geq 1}$ are iid with density $p(x)$. If the associated
residual time $R(\tau)$ has a density $u(x,t)$, its Kolmogorov forward
equation is given by

$\partial_{t}u(x,t)-\partial_{x}u(x,t)=p(x)u(0,t),\quad x,t\in[0,\infty),$

with an initial holding time density $u(x,0)=u_{0}(x)$. We derive a measure-
valued solution formula for the density of residual times after an expected
number of renewals occur. Solutions under this time scale are then shown to
evolve continuously in the space of measures with the weak topology for a wide
variety of holding times.

MSC classification: 60K05

Keywords: Kolmogorov forward equation, residual time, renewal theory

11footnotetext: Department of Mathematical Sciences, Rensselaer Polytechnic
Institute, 110 8th Street, Troy, NY 12180. Email<EMAIL_ADDRESS>
##  1 Introduction

Let $\\{X_{i}\\}_{i\geq 1}$ be a sequence of iid random variables in
$\mathbb{R}_{+}=[0,\infty)$ called holding times, each having a density
$p(x)\in L^{1}(\mathbb{R}_{+})$. Also define a random initial holding time
$X_{0}\in\mathbb{R}_{+}$, independent from $\\{X_{i}\\}_{i\geq 1}$, but
possibly distinct in law. The renewal process $N(\tau)$ associated with
$\\{X_{i}\\}_{i\geq 0}$ counts the number of renewals up to time $\tau$, and
is given by

$N(\tau)=\sup\left\\{i\geq 0:\sum_{j=0}^{i}X_{i}\leq\tau\right\\}.$ (1.1)

Related to the renewal process is the residual time (also known as the forward
recurrence time), defined as

$R(\tau)=\sum_{i=1}^{N(\tau)+1}X_{i}-\tau.$ (1.2)

At time $\tau$, $R(\tau)$ is the time remaining until the next renewal.
Residual times are fundamental in renewal theory and queueing theory (see Ch.
9 of Cox [2] for a detailed introduction), and may be viewed as an extension
of homogeneous Poisson processes, in which holding times, and consequently
residual times, are exponentially distributed [9].

If $R(\tau)$ has a differentiable density in time and space $u(x,\tau)\in
C^{1}(\mathbb{R}^{+}\times\mathbb{R}^{+},\mathbb{R}^{+})$, then the Kolmogorov
forward equation for residual times is given by

$\displaystyle\partial_{\tau}u(x,\tau)-\partial_{x}u(x,\tau)$
$\displaystyle=p(x)u(0,\tau),\quad\tau,x\geq 0,$ (1.3) $\displaystyle u(x,0)$
$\displaystyle=u_{0}(x).$

This equation has the explicit solution (see Pg. 63 of [1]) of

$u(x,\tau)=u_{0}(x+\tau)+\int_{0}^{\tau}p(x+\tau-s)\alpha(s)ds.$ (1.4)

Here, $\alpha(s)$ is the renewal density

$\alpha(\tau)=u_{0}(\tau)*\sum_{i=0}^{\infty}p^{*(i)}(\tau),$ (1.5)

where $p^{*(i)}$ denotes $i$-fold self-convolution (with the convention
$p^{*(0)}=1$ and $p^{*(1)}=p$). An important fact (see Sect. 9.12 in [10]) is
that

$A(\tau):=\mathbb{E}[N(\tau)]=\int_{0}^{\tau}\alpha(s)ds.$ (1.6)

In Section 2.1 we derive (1.3) through asymptotic expansions, and in Section
2.2, we derive (1.4) through Laplace transforms, a method similar to [4].

The main novelty of this paper is a change of variables for (1.3) based on
expected renewals, presented in Section 3. Specifically, we introduce the new
time scale $t(\tau)=A(\tau).$ Using the $t$ time scale is a natural option for
several scenarios in queuing theory. For an example, consider a factory lit by
a large collection of $N$ light bulbs, running simultaneously. When a bulb
breaks, it is immediately replaced by a new light bulb with a random run
length distributed with respect to $p(x)$. If the initial distribution of run
lengths at time zero for the $N$ bulbs is approximately $u_{0}(x)$, then
$u(x,\tau)$ estimates remaining run lengths at time $\tau$. What, then, is the
distribution of remaining run lengths after $Nt$ light bulbs have been
replaced? The answer to this question is provided through the renewal-scaled
solution formula (3.7). Given the expansive history of renewal theory, the
author expected to find (3.7) in the literature, but was unable to do so after
a thorough search.

Both the change of time scale and method for renewal-scaled solutions are
motivated by the work of Menon, Niethammer, and Pego in [8], who investigated
a wide range of clustering events generalizing the 1D Allen-Cahn equation in
mathematical physics. The measure-valued space of clusters was shown to be
continuous in time in the space of probability measures
$\mathcal{P}(\mathbb{R}^{+})$ through using an intrinsic time scale based on
the number of clusters in the system. In our case, we define measure-valued
solutions of (1.3) in the $t$ time scale which evolve continuously in
$\mathcal{P}(\mathbb{R}^{+})$ under a wide range of holding times. We conclude
with an example in Section 3.3, which illustrates with how renewal-scaled
solutions continuously evolve under initial holding times with point masses.

##  2 Strong solutions

###  2.1 Derivation of forward equation

Figure 2.1: A dynamical system representation Left: A particle at time
$\tau=0$ is placed on the positive real line. Middle: The particle moves
toward the origin at unit speed. Right: The particle reaches the origin, where
where it is randomly reassigned to $(0,\infty)$ under a probability density
$p(x)$.

To provide a helpful schematic of residual times, we will use an equivalent
reformulation for $R(\tau)$ from the perspective of a random dynamical system.
This is done by considering a particle at time $\tau=0$ randomly placed on
$\mathbb{R}^{+}$, with its initial position $R(0)$ given by the first holding
time $X_{0}$. The particle drifts toward the origin at unit speed until it
reaches the origin at time $\tau=X_{0}$. At this time, it is immediately
reassigned to $R(X_{0})=X_{1}\in\mathbb{R}^{+}$, distributed with respect to
$p(x)$. The particle proceeds as before, moving toward the origin and being
reassigned upon its arrival, with $R(\sum_{j=1}^{k-1}X_{j})=X_{k},$ and
$\\{X_{i}\\}_{i\geq 1}$ iid (see Figure 2.1). It is clear that the position of
the particle at time $\tau$ corresponds with the residual time $R(\tau)$ under
holding times $\\{X_{k}\\}_{k\geq 1}.$

To derive (1.3), we will compute asymptotics for probabilities that a particle
is in a small interval. Assume for now that $p(x)$ is continuous, and
$u(x,\tau)$ is differentiable in both $x$ and $\tau$. Then an asymptotic
expansion for the probability that a particle is in $[x,x+\Delta x]$ at time
$\tau$ is

$\mathbb{P}(R(\tau)\in[x,x+\Delta x])=u(x,\tau)\Delta
x+\frac{1}{2}\partial_{x}u(x,\tau)(\Delta x)^{2}+o((\Delta x)^{2}).$ (2.1)

Next, we consider the probability that the particle at initial time
$\tau-\Delta x$ is contained in $[x,x+\Delta x]$ at time $\tau$. This can
occur in two ways. The simplest case is when the particle is initially in
$[x+\Delta x,x+2\Delta x]$. Denote this event $A$, whose probability has the
expansion

$\displaystyle\mathbb{P}(A)$ $\displaystyle=\mathbb{P}(R(\tau-{\Delta
x})\in[x+\Delta x,x+2\Delta x])$ (2.2) $\displaystyle=u(x,\tau)\Delta
x-\partial_{\tau}u(x,\tau)(\Delta x)^{2}+\frac{3}{2}\partial_{x}u(x,t)(\Delta
x)^{2}+o((\Delta x)^{2}).$

The second case is when a particle begins in $[0,\Delta x]$, reaches the
origin, and is reassigned before drifting into $[x,x+\Delta x]$ at time
$\tau$. Denote this event $B$. We may partition this event according to the
particle’s initial position $s\in[0,\Delta x]$, and how many times the
particle jumps. Then

$\displaystyle\mathbb{P}(B)$ $\displaystyle=\int_{0}^{\Delta x}u(s,\tau-\Delta
x)[(\mathbb{P}((\hbox{1 jump})\cap B|R(\tau-\Delta x)=s)$ (2.3)
$\displaystyle\hskip 70.0pt+\mathbb{P}((>\hbox{1 jump})\cap B|R(\tau-\Delta
x)=s)]ds$ $\displaystyle=\int_{0}^{\Delta x}u(s,\tau-\Delta
x)\left(\int_{x+\Delta x-s}^{x+2\Delta x-s}p(y)dy\right)ds+o\big{(}(\Delta
x)^{2}\big{)}$ $\displaystyle=u(0,\tau)p(x)(\Delta x)^{2}+o\big{(}(\Delta
x)^{2}\big{)}.$

Since $\mathbb{P}(R(\tau)\in[x,x+\Delta x])=\mathbb{P}(A)+\mathbb{P}(B)$, we
compare $(\Delta x)^{2}$ terms in (2.1), (2.2), and (2.3) to arrive at (1.3).

###  2.2 Classical solutions

In this section, we will derive the solution formula (1.4) for initial
conditions in the space

$\mathcal{C}=\\{u\in C^{1}(\mathbb{R}^{+})\cap
L^{1}(\mathbb{R}^{+}):u>0,\|u\|_{1}=1,u(x)\rightarrow 0\hbox{ as
}x\rightarrow\infty\\}.$ (2.4)

######  Definition 1.

Let $p(x)\in\mathcal{C}$. A function $u(x,\tau)\in
C^{1}(\mathbb{R}^{+}\times\mathbb{R}^{+};\mathbb{R}^{+})$ with
$u(x,0)\in\mathcal{C}$ which solves $(\ref{pde})$ is a strong solution.

Our first step in finding an explicit strong solution formula is integrating
(1.3) along characteristics $x(\tau)=x_{0}-\tau$, which gives us the integral
form of (1.3)

$u(x,\tau)=u_{0}(x+\tau)+\int_{0}^{\tau}p(x+\tau-s)u(0,s)ds.$ (2.5)

By comparing (1.4) and (2.5), we see that finding an explicit solution formula
is equivalent to showing $u(0,\tau)=\alpha(\tau)$. This in fact follows
immediately by simply setting $x=0$ in (2.5), from which we obtain the well-
known renewal equation whose solution is $\alpha(\tau)$. However, we derive
here the explicit formula for $\alpha(\tau)$, as some of the intermediate
formulas produced will be of use in later sections.

Toward this end, we apply the Laplace transform

$\bar{u}(q,\tau):=\int_{\mathbb{R^{+}}}e^{-qx}u(x,\tau)dx,\quad
q\in\mathbb{C}_{+},$ (2.6)

to both sides of (1.3) to yield

$\frac{d}{d\tau}\bar{u}-q\bar{u}=(\bar{p}(q)-1)u(0,s).$ (2.7)

This may easily be solved for $\bar{u}$, with

$\bar{u}(q,\tau)=e^{q\tau}\bar{u}_{0}(q)+(\bar{p}(q)-1)\int_{0}^{\tau}e^{q(\tau-s)}u(0,s)ds.$
(2.8)

This solution is similar to (1.4), but now we can use Laplace inversion to
extract a formula for $u(0,s)$. Since we are taking the Laplace transform of a
probability density, $|\bar{u}(q,\tau)|<1$ for $\tau>0,q\in\mathbb{C}_{+}$.
Thus $\bar{u}(q,\tau)e^{-q\tau}\rightarrow 0$ as $\tau\rightarrow\infty$. We
then can obtain, from the $\tau\rightarrow\infty$ limit of (2.8),

$\frac{1}{1-\bar{p}(q)}\bar{u}_{0}(q)=\int_{\mathbb{R^{+}}}e^{-qs}\alpha(s)ds=[\bar{u}(0,\cdot)](q).$
(2.9)

We now have a formula for $\bar{u}(0,\tau)$ based on the initial data. Notice
that the left hand side is a Laplace transform in the spatial variable,
whereas the right hand side is a Laplace transform of $u(0,\tau)$ in the time
variable.

To perform Laplace inversion on (2.9), observe that $p$ is a probability
density, so that $|\bar{p}(q)|<1$ for $q\in\mathbb{C}_{+}$. Thus, we can
express the left hand side of (2.9) as the geometric series

$[\bar{u}(0,\cdot)](q)=\bar{u}_{0}(q)\sum_{i=0}^{\infty}(\bar{p}(q))^{i}.$
(2.10)

From the convolution formula, our renewal density has an explicit expression

$u(0,\tau)=u_{0}(\tau)*\sum_{i=0}^{\infty}p^{*(i)}(\tau),$ (2.11)

which is equivalent to $\alpha(\tau)$. Since $\alpha(t)$ is locally integrable
(Th. 3.18 of [6]), (1.4) is well-defined, $u(x,\tau)$ is differentiable in
both spatial and time variables, and for fixed $\tau\geq 0$,
$u(x,\tau)\rightarrow 0$ as $x\rightarrow\infty$. Finally, we may show that
$u(\tau,x)$ is a probability density for each $\tau\geq 0$ integrating (1.3)
with respect to the $x$ variable. We summarize our findings in

######  Theorem 2.

Let $p(x)\in C(\mathbb{R}^{+}),$ and $u_{0}(x)\in\mathcal{C}$. Then there
exists a unique strong solution $u(x,\tau)$ of (1.3) with $u(x,0)=u_{0}(x)$
given by (1.4). For each $\tau>0$, $u(\cdot,t)\in\mathcal{C}$.

##  3 Rescaling by expected renewals

We now introduce a new time variable $t$ to denote total expected visits to
the origin, given by

$t=A(\tau).$ (3.1)

In preparation for defining measure-valued solutions in the next section,
we’ll first reformulate (1.3) in terms of probability measures
$\mathcal{P}(\mathbb{R}^{+})$. In one dimension a probability measure
$\mu\in\mathcal{P}$ may may be identified with its cumulative distribution
function $G_{\mu}(x)=\mu([0,x))$. In the future, when no confusion arises, we
will often write $G_{\mu}\in\mathcal{P}(\mathbb{R}^{+}).$ The Lapace transform
of a measure $G$ is then defined as

$\bar{G}(q)=\int_{0}^{\infty}e^{-qx}G(dx),\quad q\in\mathbb{C}^{+}.$ (3.2)

If a measure $G(x)$ admits a density $G(dx)=g(x)dx$, then
$\bar{G}(q)=\bar{g}(q)$.

For $p(x),u_{0}(x)\in\mathcal{C}$, (2.7) may be rewritten in terms of measures
as

$\frac{d}{d\tau}\bar{U}-qU=(1-\bar{P}(q))\alpha(\tau),$ (3.3)

where $dU_{\tau}(x)=u(x,\tau)dx$ and $P(dx)=p(x)dx$. Since $p$ and $u_{0}$ are
strictly positive and continuous, so is $\alpha(\tau)$, and thus $A(\tau)$ is
strictly increasing and differentiable, with $\frac{dt}{d\tau}=\alpha(\tau)$.
We may now transform (3.3) as

$\displaystyle\frac{1}{\alpha(\tau)}\frac{d}{d\tau}(e^{-q\tau}\bar{U}_{\tau})=(1-\bar{P}(q))e^{-q\tau}.$

From the chain rule, we now convert to the $t$ time scale, with

$\frac{d}{dt}(e^{-q\tau(t)}\bar{F}_{t})=(1-\bar{P}(q))e^{-q\tau(t)},$ (3.4)

where we now define $F_{t}(x)=U_{\tau(t)}(x)$. This in turn gives us the
solution formula

$\bar{F}_{t}(q)e^{-q\tau(t)}-\bar{F}_{0}(q)=(1-\bar{P}(q))\int_{0}^{t}e^{-q\tau(s)}ds.$
(3.5)

Since $\tau(t)\rightarrow\infty$ as $t\rightarrow\infty$, the limit of (3.5)
is then

$\bar{F}_{0}(q)=(1-\bar{P}(q))\int_{0}^{\infty}e^{-q\tau(s)}ds,$ (3.6)

and consequently, $\bar{F}_{t}$ takes the simple form

$\boxed{\bar{F}_{t}(q)=(1-\bar{P}(q))\int_{t}^{\infty}e^{q(\tau(t)-\tau(s))}ds.}$
(3.7)

###  3.1 Extension to measure valued solutions

The solution formula (3.7) has only been defined for the strict class of
functions $\mathcal{C}$, but its form suggests that we may directly extend
solutions for measures $F_{0},P\in\mathcal{P}(\mathbb{R}^{+})$. To do so,
however, we require a proper extension for $A(\tau)$, since the trace
$\alpha(\tau)=u(0,\tau)$ assumes solutions have a density. Nonetheless, we can
use formula (2.11) to define

$A=F_{0}*\sum_{i=0}^{\infty}P^{*(i)},$ (3.8)

where convolution of two measures $\mu,\nu$ is defined by

$\mu*\nu(E)=\int_{\mathbb{R}^{+}}\int_{\mathbb{R}^{+}}\mathbf{1}_{E}(x+y)d\mu(x)d\nu(y).$
(3.9)

For a sequence of measures $f_{n}\rightarrow\mu$, and $g_{n}\rightarrow\nu$
converging weakly in $\mathbb{R}^{+}$, then by Prokhorov’s theorem, $f_{n}$
and $g_{n}$ are tight, and $f_{n}*g_{n}\rightarrow\mu*\nu$ weakly. We may use
this to show that $A(\tau)$ is nondecreasing for arbitrary measures
$F_{0},P\in\mathcal{P}(\mathbb{R}^{+})$ by regularization.

Even with a proper notion of $A(\tau)$, still more is required to make (3.7)
well-defined for measures. This is because $A(\tau)$ may be constant on an
interval, or have jumps, both of which prohibit an inverse with a domain
defined on all of $\mathbb{R}^{+}$. To address this, we use a generalized
notion of inverse for nondecreasing functions. For a nondecreasing function
$f:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$, define the generalized inverse
$f^{\dagger}:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$ by

$f^{\dagger}(q)=\inf\\{s\in\mathbb{R}^{+}|f(s)>q\\}.$ (3.10)

When $f$ is strictly increasing and continuous, the usual inverse $f^{-1}$ and
generalized inverse $f^{\dagger}$ coincide. For a generic distribution
$A(\tau)$, we define

$\tau(t)=A^{\dagger}(t).$ (3.11)

######  Definition 3.

Let $P\in\mathcal{P}(\mathbb{R}^{+})$. A map $(F_{0},t)\mapsto
F_{t}\in\mathcal{P}(\mathbb{R}^{+})$ defined through (3.7) is a renewal-scaled
solution to (1.3), where $A(t)$ and $\tau(t)$ are defined by (3.8) and (3.11).

###  3.2 Properties of renewal-scaled solutions

Here we will demonstrate that the extension of the solution for strong
solutions to include measure-valued initial data and holding times is natural,
in that measure-valued renewal-scaled solutions are weak limits of strong
solutions in the $t$ time scale. We also show our rescaling has the effect of
smoothing point masses approaching the origin, as weak solutions evolve
continuously so long as $A^{\dagger}(t)$ is strictly increasing.

######  Theorem 4.

Let $P\in\mathcal{P}(\mathbb{R}^{+})$ be nondefective (meaning $P(0)<1$). The
following hold:

(1) Let $u^{n}(x,\tau)$ be a sequence of strong solutions with initial
conditions $u_{0}^{n}(x)\in\mathcal{C}$ and holding time densities
$p^{n}(x)\in\mathcal{C}$, and let $F^{n}(t)$ be the corresponding renewal-
scaled solutions. Suppose $F_{t}$ is renewal-scaled solution for initial data
$F_{0}\in\mathcal{P}(\mathbb{R}^{+})$ and holding time measure
$P\in\mathcal{P}(\mathbb{R}^{+})$. Then if $u_{0}^{n}\rightarrow F_{0}$ and
$p^{n}\rightarrow P$ weakly, then $F^{n}_{t}\rightarrow F_{t}$ weakly at all
points of continuity of $A^{\dagger}(t)$.

(2) For any $P,F_{0}\in\mathcal{P}(\mathbb{R}^{+})$, $F_{t}$ is a probability
measure for all $t\geq 0$.

(3) If $A^{\dagger}(t)$ is strictly increasing, then for $t>0$, the map
$t\mapsto F_{t}$ is continuous in $\mathcal{P}(\mathbb{R}^{+})$ under the weak
topology.

######  Remark 5.

Since $\mathcal{C}$ is dense in $\mathcal{P}(\mathbb{R}^{+})$, for any
$F_{0},P\in\mathcal{P}(\mathbb{R}^{+})$ we can always find
$u^{n},p^{n}\in\mathcal{C}$ with $u^{n}\rightarrow F_{0}$ and
$p^{n}\rightarrow P$ weakly. Thus, for points of continuity of $A^{\dagger}$,
we can define renewal-scaled solutions through weak limits of strong
solutions.

######  Remark 6.

The possible nonconvergence at jump points of $A^{\dagger}$ is essentially due
to the multiple ways that one can define a generalized inverse for increasing
functions. In our definition, inverses of cadlag functions remain cadlag,
whereas using the traditional definition of a quantile from statistics, for
instance, would instead give caglad functions.

######  Remark 7.

We note that for statement (3), there are a variety of sufficient $P$ and
$F_{0}$ which produce strictly increasing $A^{\dagger}(t)$ for $t>0$. One such
sufficient condition, for instance, is if $P(x)$ is strictly increasing on an
interval about the origin. The point here is that jumps in the solution only
occur when $A(\tau)$ is constant in an interval. As we will see in Section
3.3, point masses arriving at the origin (corresponding to jumps in $A(\tau)$)
are continuously redistributed in the $t$ time scale.

###### Proof.

(1) Renewal-scaled solutions for $(F^{n}_{0},P^{n})$ satisfy

$\bar{F}_{t}^{n}(q)=(1-\bar{p}^{n}(q))\int_{t}^{\infty}e^{q(\tau^{n}(t)-\tau^{n}(s))}ds.$
(3.12)

To show weak convergence, it is enough to show
$\bar{F}_{t}^{n}(q)\rightarrow\bar{F}_{t}(q)$. We first wish to show that
$A^{n}\rightarrow A$ weakly. This follows from the continuity theorem [3,
XIII.1], which states that weak convergence of locally finite measures is
equivalent to pointwise convergence of their Laplace transforms. From (2.9),

$\bar{A}^{n}(q)=\frac{\bar{F}^{n}_{0}(q)}{1-\bar{P}^{n}(q)}\rightarrow\frac{\bar{F}_{0}(q)}{1-\bar{P}(q)}=\bar{A}(q).$
(3.13)

Weak equivalence of measures implies that cumulative functions $A^{n}(t)$
converge to $A(t)$ at all continuity points of $A(t)$. Now, for all points of
continuity of $\tau(t)=A^{\dagger}(t)$,
$\lim_{n\rightarrow\infty}(A^{n})^{\dagger}(t)=A^{\dagger}(t)$ [8, Lemma 3.1].
As the generalized inverse is a nondecreasing function, its discontinuity set
is countable, and thus $\tau^{n}(t)\rightarrow\tau(t)$ almost everywhere.

What remains is to show convergence of the integrals

$\int_{t}^{\infty}e^{-q\tau^{n}(s)}ds\rightarrow\int_{t}^{\infty}e^{-q\tau(s)}ds.$
(3.14)

Here, we will use the dominated convergence theorem. This requires bounding
the integrand $e^{-q\tau^{n}(s)}$, which we obtain from several steps:

(i) Observe that there exist $M>0$ and a positive integer $N$ such that $M$ is
a point of continuity for $P$, and $P^{n}(M)>\frac{1}{2}$ for $n>N$. Define
truncated holding times which are restricted to $[0,M]$, with cumulative
functions

$\tilde{P}^{n}(x)=P^{n}(x)/P^{n}(M),\quad\tilde{P}(x)=P(x)/P(M),\quad
x\in[0,M].$ (3.15)

Denote $\tilde{\mathbf{P}}^{n}$ and $\tilde{\mathbf{P}}$ as random variables
distributed with respect to $\tilde{P}^{n}$ and $\tilde{P}(x)$, respectively.
Then clearly $\tilde{\mathbf{P}}^{n}\rightarrow\tilde{\mathbf{P}}$ weakly, and
since $P^{n}(x)\leq\tilde{P}^{n}(x)$, it follows that
$A^{n}(t)\leq\tilde{A}^{n}(t).$

(ii) Since $\tilde{P}^{n}$ is supported on a finite interval, it has a finite
first and second moment. Thus allows us to apply Lorden’s estimate [7] to
obtain

$\tilde{A}^{n}(\tau)\leq\frac{\tau}{\mathbb{E}\left[\tilde{\mathbf{P}}^{n}\right]}+\frac{\mathbb{E}\left[(\tilde{\mathbf{P}}^{n})^{2}\right]}{\mathbb{E}\left[\tilde{\mathbf{P}}^{n}\right]^{2}}+1.$
(3.16)

Note that we have added 1 to Lorden’s original estimate to account for a
possibly distinct initial holding time.

(iii) Since $\tilde{\mathbf{P}}^{n}$ are all supported in $[0,M]$, it follows
that weak convergence to $\tilde{\mathbf{P}}$ implies the convergence of
moments. From this and (3.16) it is straightforward to show that there exist
$a,b>0$ such that for all positive $n$,

$A^{n}(\tau)\leq\tilde{A}^{n}(\tau)\leq a\tau+b$ (3.17)
$\Rightarrow\tau^{n}(t)\geq\frac{t-b}{a}.$ (3.18)

Thus, integrands in the left hand side of (3.14) are dominated by an
exponentially decaying function, which proves (3.14) and thus part (1).

Part (2) follows immediately from the weak convergence shown in part (1),
since $F^{n}$ are all probability measures.

For part (3), note that if $A(\tau)$ is strictly increasing, then $\tau(t)$ is
continuous. From (3.7), it is clear that $\bar{F}_{t}(q)$ is continuous in
$t$, which in turn implies that $F_{t}$ evolves continuously under the weak
topology in the space of measures.

∎

###  3.3 An example of renewal-scaled solutions with point mass initial
conditions

To illustrate how renewal-scaled solutions behave under jumps in initial data,
we conclude with an example with monodisperse initial conditions.
Specifically, let the initial measure data satisfy
$F_{0}=\mathbf{1}_{[1,\infty)}(x)$ and $p(x)=e^{-x}$. Then
$\mathcal{L}(p(x))=\frac{1}{q+1},\bar{F}_{0}(q)=e^{-q}$, and using (2.9),

$\bar{A}(q)=\frac{q+1}{q}e^{-q}=e^{-q}+\frac{e^{-q}}{q}.$ (3.19)

For $t>0$, Laplace inversion then gives

$A(\tau)=\begin{cases}0&\tau\in[0,1)\\\ \tau&\tau\geq 1\\\ \end{cases},$
(3.20)

which has a generalized inverse of

$\tau(t)=A^{\dagger}(t)=\begin{cases}1&t\in(0,1)\\\ t&t>1.\\\ \end{cases}$
(3.21)

Substitution of these variables into (3.7), for $t\in(0,1]$, yields

$\displaystyle\bar{F}_{t}(q)=$ $\displaystyle
e^{q}\left(\frac{q}{q+1}\int_{t}^{\infty}e^{-q\tau(s)}ds\right)$ (3.22)
$\displaystyle=$ $\displaystyle
e^{q}\left(\frac{q}{q+1}\right)\left((1-t)e^{-q}+\int_{1}^{\infty}e^{-qs}ds\right)$
$\displaystyle=$ $\displaystyle\frac{t}{q+1}+(1-t).$

Taking inverse Laplace transforms then gives us the solution
$F_{t}(dx)=(1-t)\delta_{0}(dx)+te^{-x}dx$ for $t\in(0,1]$. By a similar
calculation, we can show that $F_{t}(dx)=e^{-x}dx$ for $t>1$.

In the $t$ time scale, initial conditions with a support not containing the
origin will immediately jump through translation. For our example, the point
mass jumps to the origin, and is then continuously reassigned to $[0,\infty)$
according to $p(x)$ at a constant rate of one. After the reassignment of the
entire point mass, the solution, now a density, is stationary, since
$u(x,\tau)=e^{-x}$ is a solution to (1.3) with $p(x)=u_{0}(x)=e^{-x}$ (one can
see, in fact, that this is a manifestation of the memoryless property of
exponential distributions).

##  4 Acknowledgements

The author is indebted to Robert Pego and Govind Menon for multiple
conversions regarding the preparation of his thesis [5], a chapter of which is
the basis of this paper.

##  5 Conflicts of Interest

The author declares no conflict of interest.

## References

  * [1] D. R. Cox, Renewal theory, vol. 1, Methuen London, 1967.
  * [2] , The theory of stochastic processes, Routledge, 2017.
  * [3] W. Feller, An introduction to probability theory and its applications, vol. 2, John Wiley & Sons, 2008.
  * [4] J. W. Kim and G. C. Shim, A Markovian approach to the forward recurrence time in the renewal process, JKSS (Journal of the Korean Statistical Society), 33 (2004), pp. 299–302.
  * [5] J. Klobusicky, Kinetic limits of piecewise deterministic Markov processes and grain boundary coarsening, PhD thesis, Brown University, Providence, RI, 2014.
  * [6] M. Liao, Applied stochastic processes, CRC Press, 2013.
  * [7] G. Lorden, On excess over the boundary, The Annals of Mathematical Statistics, (1970), pp. 520–527.
  * [8] G. Menon, B. Niethammer, and R. Pego, Dynamics and self-similarity in min-driven clustering, Transactions of the American Mathematical Society, 362 (2010), pp. 6591–6618.
  * [9] S. I. Resnick, Adventures in stochastic processes, Springer Science & Business Media, 2013.
  * [10] W. J. Stewart, Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling, Princeton University Press, 2009\.


# The multiplicity of the zero Laplacian eigenvalue of uniform hypertrees

Ge Lin<EMAIL_ADDRESS>Changjiang Bu<EMAIL_ADDRESS>College of
Mathematical Sciences, Harbin Engineering University, Harbin, PR China

###### Abstract

In this paper, the Laplacian characteristic polynomial of uniform hypergraphs
with cut vertices or pendant edges and the Laplacian matching polynomial of
uniform hypergraphs are characterized. The multiplicity of the zero Laplacian
eigenvalue of uniform hypertrees is given, which proves the conjecture in [18]
(The zero eigenvalue of the Laplacian tensor of a uniform hypergraph, Linear
and Multilinear Algebra, (2023) Doi:10.1080/03081087.2023.2172541).

###### keywords:

hypertree, Laplacian tensor, multiplicity, characteristic polynomial, matching
polynomial
_AMS classification(2020):_ 05C65, 05C50.

##  1 Introduction

A hypergraph is called $k$-uniform if its each edge contains exactly $k$
vertices. For a $k$-uniform hypergraph $H=(V(H),E(H))$, its adjacency tensor
$\mathcal{A}_{H}=(a_{i_{1}i_{2}\cdots i_{k}})$ is a $k$-order
$|V(H)|$-dimensional tensor [5], where

$a_{i_{1}i_{2}\cdots i_{k}}=\begin{cases}\frac{1}{(k-1)!}&\text{if
$\\{i_{1},i_{2},\ldots,i_{k}\\}\in E(H)$},\\\ 0&\text{otherwise}.\end{cases}$

The Laplacian tensor of $H$ is
$\mathcal{L}_{H}=\mathcal{D}_{H}-\mathcal{A}_{H}$ [13], where
$\mathcal{D}_{H}$ is the diagonal tensor of vertex degrees of $H$. The
eigenvalues of $\mathcal{A}_{H}$ and $\mathcal{L}_{H}$ are called the
eigenvalues and Laplacian eigenvalues of $H$, respectively. The characteristic
polynomial of $\mathcal{A}_{H}$ and $\mathcal{L}_{H}$ are called the
characteristic polynomial and the Laplacian characteristic polynomial of $H$,
respectively.

The characteristic polynomials of uniform hypergraphs are a research area that
has attached much attention in spectral hypergraph theory. In 2012, Cooper and
Dutle [5] characterized some properties on the characteristic polynomials of
uniform hypergraphs and gave the characteristic polynomial of the one-edge
hypergraph. In 2015, Cooper and Dutle [6] gave the characteristic polynomial
of the $3$-uniform hyperstar. In 2020, Bao et al. [1] provided a combinatorial
method for computing the characteristic polynomial of uniform hypergraphs with
cut vertices, and gave the characteristic polynomial of the $k$-uniform
hyperstar. In 2021, Chen and Bu [3] gave a reduction formula for the
characteristic polynomial of uniform hypergraphs with pendant edges. Besides,
they used the reduction formula to derive the characteristic polynomial of the
uniform hyperpath.

However, there are few results on the Laplacian characteristic polynomials of
uniform hypergraphs. In 2023, Zheng [18] gave the Laplacian characteristic
polynomial of uniform hyperstar, and obtained the multiplicity of the zero
Laplacian eigenvalue of uniform hyperstar and hyperpath. Moreover, the
following conjecture was proposed in [18].

######  Conjecture 1.1.

[18] Let $T=(V(T),E(T))$ be a $k$-uniform hypertree for $k\geq 3$. Then the
multiplicity of the zero Laplacian eigenvalue of $T$ is $k^{|E(T)|(k-2)}$.

The eigenvalues of uniform hypertrees can be studied by the matching
polynomial. In 2017, Zhang et al. [17] showed that the roots of the matching
polynomial of a uniform hypertree are its eigenvalues. For a $k$-uniform
hypertree $T$ with $k\geq 3$, Clark and Cooper [4] determined all eigenvalues
of $T$ by roots of the matching polynomials of all sub-hypertrees of $T$. In
2022, Wan et al. [15] defined the Laplacian matching polynomial of uniform
hypergraphs, and used the roots of the Laplacian matching polynomials of all
sub-hypertrees of $T$ to obtain all Laplacian eigenvalues of $T$ (without
multiplicity).

In this paper, we give a expression for the Laplacian characteristic
polynomial of uniform hypergraphs with cut vertices or pendant edges (Section
2). And we characterize some properties on the Laplacian matching polynomial
of uniform hypergraphs (Section 3). Further, we use these results to give the
multiplicity of the zero Laplacian eigenvalue of uniform hypertrees, which
shows that Conjecture 1.1 is true (Section 4).

##  2 The Laplacian characteristic polynomial of uniform hypergraphs

###  2.1 Preliminaries

In this subsection, we present some notation and lemmas about the eigenvalue
of tensors and the formula of resultants.

A $k$-order $n$-dimensional tensor $\mathcal{A}=(a_{i_{1}i_{2}\cdots i_{k}})$
refers to a multi-dimensional array with entries $a_{i_{1}i_{2}\cdots i_{k}}$
for all $i_{j}\in[n]:=\\{1,\ldots,n\\}$ and $j\in[k]$. If there exists
$\lambda\in\mathbb{C}$ and a non-zero vector
$\mathbf{x}=(x_{1},\ldots,x_{n})^{\mathrm{T}}\in\mathbb{C}^{n}$ such that

$\displaystyle\mathcal{A}\mathbf{x}^{k-1}=\lambda\mathbf{x}^{[k-1]},$

where $\mathcal{A}\mathbf{x}^{k-1}$ is an $n$-dimensional vector with
$\sum_{i_{2},\ldots,i_{k}=1}^{n}a_{ii_{2}\ldots i_{k}}x_{i_{2}}\cdots
x_{i_{k}}$ as its $i$-th component and
$\mathbf{x}^{[k-1]}=(x_{1}^{k-1},\ldots,x_{n}^{k-1})^{\mathrm{T}}$, then
$\lambda$ is called an eigenvalue of $\mathcal{A}$ and $\mathbf{x}$ is an
eigenvector of $\mathcal{A}$ corresponding to $\lambda$ (see [10, 12]). The
resultant of the polynomials system
$(\lambda\mathbf{x}^{[k-1]}-\mathcal{A}\mathbf{x}^{k-1})$ is called the
characteristic polynomial of $\mathcal{A}$, denoted by $\phi(\mathcal{A})$.

In the following, we introduce some formulas of resultants required for proofs
in this section.

######  Lemma 2.2.

[7, Poisson Formula for resultants] Let
$F_{1},F_{2},\ldots,F_{n}\in\mathbb{C}[x_{1},\ldots,x_{n}]$ be homogeneous
polynomials of respective degrees $d_{1},d_{2},\ldots,d_{n}$. For each
$i\in[n]$, let $\overline{F}_{i}=F_{i}|_{x_{1}=0}$ and
$f_{i}=F_{i}|_{x_{1}=1}$. Let $\mathcal{V}$ be the affine variety defined by
the polynomials $f_{2},\ldots,f_{n}$. If
$\mathrm{Res}(\overline{F}_{2},\ldots,\overline{F}_{n})\neq 0$, then

$\displaystyle\mathrm{Res}(F_{1},F_{2},\ldots,F_{n})=\mathrm{Res}(\overline{F}_{2},\ldots,\overline{F}_{n})^{d_{1}}\prod_{\mathbf{p}\in\mathcal{V}}f_{1}(\mathbf{p})^{m(\mathbf{p})},$

where $m(\mathbf{p})$ is the multiplicity of a point $\mathbf{p}$ in
$\mathcal{V}$.

######  Lemma 2.3.

[5, lemma 3.2] Let $F_{1},\ldots,F_{n}\in\mathbb{C}[x_{1},\ldots,x_{n}]$ be
homogeneous polynomials of respective degrees $d_{1},\ldots,d_{n}$, and let
$G_{1},\ldots,G_{m}\in\mathbb{C}[y_{1},\ldots,y_{m}]$ be homogeneous
polynomials of respective degrees $\delta_{1},\ldots,\delta_{m}$. Then

$\displaystyle\mathrm{Res}(F_{1},\ldots,F_{n},G_{1},\ldots,G_{m})=\mathrm{Res}(F_{1},\ldots,F_{n})^{\prod_{j=1}^{m}\delta_{j}}\mathrm{Res}(G_{1},\ldots,G_{m})^{\prod_{i=1}^{n}d_{i}}.$

Let $H=(V(H),E(H))$ be a $k$-uniform hypergraph with $V(H)=[n]$. For a vertex
$v\in V(H)$, let $E_{H}(v)$ denote the set of edges of $H$ containing $v$ and
$d_{H}(v)$ denote the degree of $v$ in $H$. Given an edge $e\in E(H)$ and a
vector $\mathbf{x}=(x_{1},\ldots,x_{n})^{\mathrm{T}}\in\mathbb{C}^{n}$, let
$\mathbf{x}_{e}=\prod_{v\in e}x_{v}$. Then the eigenvalue equation
$\mathcal{L}_{H}\mathbf{x}^{k-1}=\lambda\mathbf{x}^{[k-1]}$ corresponding to
the Laplacian tensor of $H$ can be written as

$\displaystyle d_{H}(v)x_{v}^{k-1}-\sum_{e\in
E_{H}(v)}\mathbf{x}_{e\setminus\\{v\\}}=\lambda x_{v}^{k-1},v=1,\ldots,n.$

For each $v\in V(H)$, define

$\displaystyle F_{v}=(\lambda-d_{H}(v))x_{v}^{k-1}+\sum_{e\in
E_{H}(v)}\mathbf{x}_{e\setminus\\{v\\}}.$

For a fixed vertex $w\in V(H)$, let

$\displaystyle\overline{F}_{v}=F_{v}|_{x_{w}=0},f_{v}=F_{v}|_{x_{w}=1}.$

Let $\mathcal{V}^{H}$ be the affine variety defined by the polynomials $f_{v}$
for all $v\in V(H)\setminus\\{w\\}$. We use
$\mathcal{L}_{H}(w)=(l_{i_{1}\cdots i_{k}})$ to denote a $k$-order
$n-1$-dimensional principal sub-tensor of $\mathcal{L}_{H}$, where
$i_{1},\ldots,i_{k}\in V(H)\setminus\\{w\\}$. By the Poisson Formula for
resultants, we obtain the following lemma about the Laplacian characteristic
polynomial of $H$.

######  Lemma 2.4.

Let $H$ be a $k$-uniform hypergraph and $w$ be a vertex on $H$. Then the
Laplacian characteristic polynomial

$\displaystyle\phi(\mathcal{L}_{H})=\phi(\mathcal{L}_{H}(w))^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{H}}(\lambda-
d_{H}(w)+\sum_{e\in E_{H}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})},$
(2.1)

where $m(\mathbf{p})$ is the multiplicity of $\mathbf{p}$ in
$\mathcal{V}^{H}$.

###### Proof.

By the definition of the Laplacian characteristic polynomial, we know that
$\phi(\mathcal{L}_{H})=\mathrm{Res}(F_{v}:v\in V(H))$, where $F_{v}=(\lambda-
d_{H}(v))x_{v}^{k-1}+\sum_{e\in E_{H}(v)}\mathbf{x}_{e\setminus\\{v\\}}$. For
the vertex $w\in V(H)$, by Lemma 2.2, we have

$\displaystyle\phi(\mathcal{L}_{H})=\mathrm{Res}(\overline{F}_{v}:v\in
V(H)\setminus\\{w\\})^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{H}}f_{w}(\mathbf{p})^{m(\mathbf{p})}.$

For all $v\in V(H)\setminus\\{w\\}$,
$\overline{F}_{v}=F_{v}|_{x_{w}=0}=(\lambda-d_{H}(v))x_{v}^{k-1}+\sum_{e\in
E_{H-w}(v)}\mathbf{x}_{e\setminus\\{v\\}}=0$ are the eigenvalue equations of
$\mathcal{L}_{H}(w)$, where $H-w$ denote the hypergraph obtained from $H$ by
removing the vertex $w$ and all edges incident to it, so we have

$\displaystyle\mathrm{Res}(\overline{F}_{v}:v\in
V(H)\setminus\\{w\\})=\phi(\mathcal{L}_{H}(w)).$ (2.2)

Note that $f_{w}=F_{w}|_{x_{w}=1}=\lambda-d_{H}(w)+\sum_{e\in
E_{H}(w)}\mathbf{x}_{e\setminus\\{w\\}}$. Then we obtain

$\displaystyle\phi(\mathcal{L}_{H})=\phi(\mathcal{L}_{H}(w))^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{H}}(\lambda-
d_{H}(w)+\sum_{e\in E_{H}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})}.$

∎

When $H$ is a uniform hypergraph with cut vertices, we can give a description
of the affine variety $\mathcal{V}^{H}$ for this case and obtain a more
explicit expression for the Laplacian characteristic polynomial of $H$ than
(2.1).

###  2.2 Main results

Let $H=(V(H),E(H))$ be a $k$-uniform connected hypergraph and $w\in V(H)$.
Denote $\widehat{E}_{H}(w)=\\{e\setminus\\{w\\}:e\in E_{H}(w)\\}$. Deleting
the vertex $w$, it can get a non-uniform hypergraph $\widehat{H}$ with vertex
set $V(\widehat{H})=V(H)\setminus\\{w\\}$ and edge set
$E(\widehat{H})=(E(H)\setminus E_{H}(w))\cup\widehat{E}_{H}(w)$. The vertex
$w$ is called a cut vertex if $\widehat{H}$ is not connected [1]. Suppose that
$w$ is a cut vertex on $H$ and $\widehat{H}_{1},\ldots,\widehat{H}_{s}$ are
connected components of $\widehat{H}$. For each $i\in[s]$, denote the induced
sub-hypergraph of $H$ on $V(\widehat{H}_{i})\cup\\{w\\}$ by
$\widetilde{H}_{i}$, and we call $\widetilde{H}_{i}$ a branch of $H$
associated with $w$. Clearly, $H$ can be obtained by coalescing the branches
$\widetilde{H}_{1},\ldots,\widetilde{H}_{s}$ to the vertex $w$. Recall that
the affine variety $\mathcal{V}^{H}$ is defined by the polynomials
$f_{v}=(\lambda-d_{H}(v))x_{v}^{k-1}+\sum_{e\in
E_{H}(v)}\mathbf{x}_{e\setminus\\{v\\}}|_{x_{w}=1}$ for all $v\in
V(H)\setminus\\{w\\}$. Then, for each $v_{i}\in
V(\widetilde{H}_{i})\setminus\\{w\\}$ and $i\in[s]$, we have

$\displaystyle f_{v_{i}}$ $\displaystyle=(\lambda-
d_{H}(v_{i}))x_{v_{i}}^{k-1}+\sum_{e\in
E_{H}(v_{i})}\mathbf{x}_{e\setminus\\{v_{i},w\\}}$ $\displaystyle=(\lambda-
d_{\widetilde{H}_{i}}(v_{i}))x_{v_{i}}^{k-1}+\sum_{e\in
E_{\widetilde{H}_{i}}(v_{i})}\mathbf{x}_{e\setminus\\{v_{i},w\\}}.$

It is known that $\mathcal{V}^{\widetilde{H}_{i}}$ is the affine variety
defined by the polynomials $f_{v_{i}}$ for all $v_{i}\in
V(\widetilde{H}_{i})\setminus\\{w\\}$ and each $i\in[s]$. So

$\displaystyle\mathcal{V}^{H}=\mathcal{V}^{\widetilde{H}_{1}}\times\cdots\times\mathcal{V}^{\widetilde{H}_{s}}.$
(2.3)

Combining Lemma 2.2 with (2.3), an expression for the Laplacian characteristic
polynomial of uniform hypergraphs with cut vertices is derived as follows.

######  Theorem 2.5.

Let $H$ be a $k$-uniform hypergraph and $w$ be a cut vertex on $H$. Let
$\widetilde{H}_{1},\ldots,\widetilde{H}_{s}$ are the branches of $H$
associated with $w$. Denote
$\mathcal{V}^{(i)}=\mathcal{V}^{\widetilde{H}_{i}}$ and
$E_{i}(w)=E_{\widetilde{H}_{i}}(w)$. Then

$\displaystyle\phi(\mathcal{L}_{H})=\prod_{i=1}^{s}\phi\left(\mathcal{L}_{\widetilde{H}_{i}}(w)\right)^{(k-1)^{2-s+\sum_{j\neq
i}|V(\widetilde{H}_{j})|}}\prod_{\begin{subarray}{c}\mathbf{p}^{(i)}\in\mathcal{V}^{(i)}\\\
i\in[s]\end{subarray}}(\lambda-\sum_{i=1}^{s}d_{\widetilde{H}_{i}}(w)+\sum_{\begin{subarray}{c}e\in
E_{i}(w)\\\
i\in[s]\end{subarray}}\mathbf{p}^{(i)}_{e\setminus\\{w\\}})^{\prod_{i=1}^{s}m(\mathbf{p}^{(i)})},$

where $m(\mathbf{p}^{(i)})$ is the multiplicity of $\mathbf{p}^{(i)}$ in
$\mathcal{V}^{(i)}$ for each $i\in[s]$.

###### Proof.

By Lemma 2.4, the Laplacian characteristic polynomial

$\displaystyle\phi(\mathcal{L}_{H})=\phi(\mathcal{L}_{H}(w))^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{H}}(\lambda-
d_{H}(w)+\sum_{e\in E_{H}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})}.$
(2.4)

From (2.2), we know that
$\phi(\mathcal{L}_{H}(w))=\mathrm{Res}(\overline{F}_{v}:v\in
V(H)\setminus\\{w\\})$. Recall that $\overline{F}_{v}=(\lambda-
d_{H}(v))x_{v}^{k-1}+\sum_{e\in
E_{H}(v)}\mathbf{x}_{e\setminus\\{v\\}}|_{x_{w}=0}$ for each $v\in
V(H)\setminus\\{w\\}$, and note that $H$ can be obtained by coalescing the
branches $\widetilde{H}_{1},\ldots,\widetilde{H}_{s}$ to the vertex $w$. For
all $v_{i}\in V(\widetilde{H}_{i})\setminus\\{w\\}$ and each $i\in[s]$, we
have

$\displaystyle\overline{F}_{v_{i}}$ $\displaystyle=(\lambda-
d_{H}(v_{i}))x_{v_{i}}^{k-1}+\sum_{e\in
E_{H}(v_{i})}\mathbf{x}_{e\setminus\\{v_{i}\\}}|_{x_{w}=0}$
$\displaystyle=(\lambda-
d_{\widetilde{H}_{i}}(v_{i}))x_{v_{i}}^{k-1}+\sum_{e\in
E_{\widetilde{H}_{i}}(v_{i})}\mathbf{x}_{e\setminus\\{v_{i}\\}}|_{x_{w}=0}$
$\displaystyle=(\lambda-
d_{\widetilde{H}_{i}}(v_{i}))x_{v_{i}}^{k-1}+\sum_{e\in
E_{\widetilde{H}_{i}-w}(v_{i})}\mathbf{x}_{e\setminus\\{v_{i}\\}},$

where $\widetilde{H}_{i}-w$ denote the hypergraph obtained from
$\widetilde{H}_{i}$ by removing the vertex $w$ and all edges incident to it.
So $\phi(\mathcal{L}_{H}(w))=\mathrm{Res}(\overline{F}_{v}:v\in
V(H)\setminus\\{w\\})=\mathrm{Res}(\overline{F}_{v_{i}}:v_{i}\in
V(\widetilde{H}_{i})\setminus\\{w\\},i\in[s])$. By Lemma 2.3, we get

$\displaystyle\phi(\mathcal{L}_{H}(w))=\prod_{i=1}^{s}\mathrm{Res}(\overline{F}_{v_{i}}:v_{i}\in
V(\widetilde{H}_{i})\setminus\\{w\\})^{(k-1)^{1-s+\sum_{j\neq
i}|V(\widetilde{H}_{j})|}}.$

For all $v_{i}\in V(\widetilde{H}_{i})\setminus\\{w\\}$ and each $i\in[s]$,
$\overline{F}_{v_{i}}=0$ are the eigenvalue equations of
$\mathcal{L}_{\widetilde{H}_{i}}(w)$. Then we have
$\mathrm{Res}(\overline{F}_{v_{i}}:v_{i}\in
V(\widetilde{H}_{i})\setminus\\{w\\})=\phi(\mathcal{L}_{\widetilde{H}_{i}}(w))$,
which implies that

$\displaystyle\phi(\mathcal{L}_{H}(w))=\prod_{i=1}^{s}\phi(\mathcal{L}_{\widetilde{H}_{i}}(w))^{(k-1)^{1-s+\sum_{j\neq
i}|V(\widetilde{H}_{j})|}}.$ (2.5)

For any $\mathbf{p}\in\mathcal{V}^{H}$, by (2.3), we have
$\mathbf{p}=\left(\begin{matrix}\mathbf{p}^{(1)}\\\ \vdots\\\
\mathbf{p}^{(s)}\end{matrix}\right)$, where
$\mathbf{p}^{(i)}\in\mathcal{V}^{(i)}$ for all $i\in[s]$. Then we obtain

$\displaystyle\prod_{\mathbf{p}\in\mathcal{V}^{H}}(\lambda-d_{H}(w)+\sum_{e\in
E_{H}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})}$
$\displaystyle=\prod_{\mathbf{p}\in\mathcal{V}^{H}}(\lambda-
d_{H}(w)+\sum_{\begin{subarray}{c}e\in E_{i}(w)\\\
i\in[s]\end{subarray}}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})}$
$\displaystyle=\prod_{\begin{subarray}{c}\mathbf{p}^{(i)}\in\mathcal{V}^{(i)}\\\
i\in[s]\end{subarray}}(\lambda-\sum_{i=1}^{s}d_{\widetilde{H}_{i}}(w)+\sum_{\begin{subarray}{c}e\in
E_{i}(w)\\\
i\in[s]\end{subarray}}\mathbf{p}^{(i)}_{e\setminus\\{w\\}})^{\prod_{i=1}^{s}m(\mathbf{p}^{(i)})}.$
(2.6)

Substituting (2.5) and (2.2) into (2.4), the proof is completed.

∎

An edge on $k$-uniform hypergraph is called a pendant edge if it contains
exactly $k-1$ vertices with degree one. When $k$-uniform hypergraph $H$ has a
pendant edge incident to $w$, it implies that $w$ is a cut vertex on $H$ and
one of the branches is the one-edge hypergraph. We use Theorem 2.5 to give a
more explicit expression for the Laplacian characteristic polynomial of
uniform hypergraphs with pendant edges.

######  Corollary 2.6.

Let $H$ be a $k$-uniform hypergraph with a pendant edge incident to the non-
pendent vertex $w$, and we define $\widetilde{H}$ as the $k$-uniform
hypergraph obtained by removing the pendant edge and pendent vertices on it
from $H$. Then

$\displaystyle\phi(\mathcal{L}_{H})=$
$\displaystyle(\lambda-1)^{(k-1)^{|V(\widetilde{H})|+k-1}}\phi(\mathcal{L}_{\widetilde{H}}(w))^{(k-1)^{k}}\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{H}}}(\lambda-
d_{\widetilde{H}}(w)-1+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})K_{1}}$
$\displaystyle\times\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{H}}}(\lambda-
d_{\widetilde{H}}(w)-1+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})K_{2}},$

where $K_{1}=(k-1)^{k-1}-k^{k-2}$ and $K_{2}=k^{k-2}$.

###### Proof.

Clearly, $w$ is a cut vertex on $H$. Suppose that the branches of $H$
associated with $w$ are $\widetilde{H}$ and the one-edge hypergraph with $k$
vertices, denoted by $H^{\prime}$. By Theorem 2.5, we have

$\displaystyle\phi(\mathcal{L}_{H})=$
$\displaystyle\phi\left(\mathcal{L}_{\widetilde{H}}(w)\right)^{(k-1)^{k}}\phi\left(\mathcal{L}_{H^{\prime}}(w)\right)^{(k-1)^{|V(\widetilde{H})|}}$
$\displaystyle\times\prod_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{H}}\\\
\mathbf{q}\in\mathcal{V}^{H^{\prime}}\end{subarray}}(\lambda-
d_{\widetilde{H}}(w)-1+\mathbf{q}_{e^{\prime}\setminus\\{w\\}}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})m(\mathbf{q})},$
(2.7)

where $e^{\prime}$ is the edge of $H^{\prime}$.

Since $\mathcal{L}_{H^{\prime}}(w)$ is a $k$-order $k-1$-dimensional identity
tensor for the one-edge hypergraph $H^{\prime}$, we get

$\displaystyle\phi(\mathcal{L}_{H^{\prime}}(w))=(\lambda-1)^{(k-1)^{k-1}}.$
(2.8)

It is shown that the Laplacian characteristic polynomial of $H^{\prime}$ is
$\phi(\mathcal{L}_{H^{\prime}})=(\lambda-1)^{k(k-1)^{k-1}-k^{k-1}}((\lambda-1)^{k}+(-1)^{k-1})^{k^{k-2}}$
in the [18, Theorem 4.2]. It follows from (2.1) that

$\displaystyle\prod_{\mathbf{q}\in\mathcal{V}^{H^{\prime}}}(\lambda-1+\mathbf{q}_{e^{\prime}\setminus\\{w\\}})^{m(\mathbf{q})}$
$\displaystyle=\frac{\phi(\mathcal{L}_{H^{\prime}})}{\phi\left(\mathcal{L}_{H^{\prime}}(w)\right)^{k-1}}$
$\displaystyle=(\lambda-1)^{(k-1)^{k-1}-k^{k-2}}(\lambda-1+(\frac{-1}{\lambda-1})^{k-1})^{k^{k-2}}.$

Then we have

$\displaystyle\mathbf{q}_{e^{\prime}\setminus\\{w\\}}=\begin{cases}0,&\text{if
$\mathbf{q}=\mathbf{0}$,}\\\ (\frac{-1}{\lambda-1})^{k-1},&\text{if
$\mathbf{q}\neq\mathbf{0}$,}\end{cases}$ (2.9)

for $\mathbf{q}\in\mathcal{V}^{H^{\prime}}$, and we have
$m(\mathbf{0})=(k-1)^{k-1}-k^{k-2}$,
$\sum_{\mathbf{0}\neq\mathbf{q}\in\mathcal{V}^{H^{\prime}}}m(\mathbf{q})=k^{k-2}$
for $\mathbf{0}\in\mathcal{V}^{H^{\prime}}$. By (2.9), the equation in (2.2)
is derived as follows:

$\displaystyle\prod_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{H}}\\\
\mathbf{q}\in\mathcal{V}^{H^{\prime}}\end{subarray}}(\lambda-
d_{\widetilde{H}}(w)-1+\mathbf{q}_{e^{\prime}\setminus\\{w\\}}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})m(\mathbf{q})}$
$\displaystyle=$
$\displaystyle\prod_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{H}}\\\
\mathbf{0}=\mathbf{q}\in\mathcal{V}^{H^{\prime}}\end{subarray}}(\lambda-
d_{\widetilde{H}}(w)-1+\mathbf{q}_{e^{\prime}\setminus\\{w\\}}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})m(\mathbf{q})}$
$\displaystyle\times\prod_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{H}}\\\
\mathbf{0}\neq\mathbf{q}\in\mathcal{V}^{H^{\prime}}\end{subarray}}(\lambda-
d_{\widetilde{H}}(w)-1+\mathbf{q}_{e^{\prime}\setminus\\{w\\}}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})m(\mathbf{q})}$
$\displaystyle=$
$\displaystyle\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{H}}}(\lambda-
d_{\widetilde{H}}(w)-1+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})((k-1)^{k-1}-k^{k-2})}$
$\displaystyle\times\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{H}}}(\lambda-
d_{\widetilde{H}}(w)-1+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{H}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})k^{k-2}}.$
(2.10)

Substituting (2.8) and (2.2) into (2.2), the proof is completed.

∎

##  3 The Laplacian matching polynomial of uniform hypergraphs

Let $H=(V(H),E(H))$ be a $k$-uniform hypergraph. Let $M$ be a sub-set of
$E(H)$. Denote by $V(M)$ the set of vertices of $H$ each of which is an
endpoint of one of the edges in $M$. If no two distinct edges in $M$ share a
common vertex, then $M$ is called a matching of $H$. The set of matchings
(including the empty set) of $H$ is denoted by $\mathcal{M}(H)$. Let
$\mathbf{w}:V(H)\cup E(H)\rightarrow\mathbb{C}$ be a weighting function on
$H$. In 2022, Wan et al. [15] defined the weighted matching polynomial of $H$
as

$\displaystyle\sum_{M\in\mathcal{M}(H)}(-1)^{|M|}\prod_{e\in
M}\mathbf{w}(e)^{k}\prod_{v\in V(H)\setminus V(M)}(\lambda-\mathbf{w}(v)).$

For any sub-hypergraph $\widetilde{H}$ of $H$, if we choose the weighting
function on $\widetilde{H}$ such that $\mathbf{w}(v)=d_{H}(v)$ for all $v\in
V(\widetilde{H})$ and $\mathbf{w}(e)=-1$ for all $e\in E(\widetilde{H})$, then
the weighted matching polynomial of $\widetilde{H}$ can be derived as

$\displaystyle\sum_{M\in\mathcal{M}(\widetilde{H})}(-1)^{(k-1)|M|}\prod_{v\in
V(\widetilde{H})\setminus V(M)}(\lambda-
d_{H}(v))=:\varphi_{H}(\widetilde{H}).$ (3.1)

In [15], the polynomial (3.1) is called the Laplacian matching polynomial of
$\widetilde{H}$ with respect to $H$.

The goal of this section is to characterize some properties on the Laplacian
matching polynomial of uniform hypergraphs, which will be used to prove the
main results in Section 4.

Firstly, we introduce some related notation. For a sub-set $S\subseteq V(H)$,
we use $H-S$ to denote the hypergraph obtained from $H$ by deleting the
vertices in $S$ and the edges incident to them. For a sub-set $I\subseteq
E(H)$, let $H\setminus I$ denote the hypergraph obtained from $H$ by deleting
the edges in $I$ (no deletion of resultant isolated vertices). When
$S=\\{v\\}$ and $I=\\{e\\}$, $H-S$ and $H\setminus I$ are simply written as
$H-v$ and $H\setminus e$, respectively.

######  Theorem 3.7.

Let $H$ be a $k$-uniform hypergraph, and $\widetilde{H}$ be a sub-hypergraph
of $H$. Then the following statements hold.
(1) If $\widetilde{H}$ is not connected and its connected components is
$\widetilde{H}_{1}$ and $\widetilde{H}_{2}$, then
$\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}_{1})\varphi_{H}(\widetilde{H}_{2})$;
(2) For $e\in E(\widetilde{H})$, we have
$\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}\setminus
e)+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e))$;
(3) For $v\in V(\widetilde{H})$ and $I\subseteq E_{\widetilde{H}}(v)$, we have

$\displaystyle\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}\setminus
I)+(-1)^{k-1}\sum_{e\in I}\varphi_{H}(\widetilde{H}-V(e)),$

and

$\displaystyle\varphi_{H}(\widetilde{H})=(\lambda-
d_{H}(v))\varphi_{H}(\widetilde{H}-v)+(-1)^{k-1}\sum_{e\in
E_{\widetilde{H}}(v)}\varphi_{H}(\widetilde{H}-V(e));$

(4) $\frac{\mathrm{d}}{\mathrm{d}\lambda}\varphi_{H}(\widetilde{H})=\sum_{v\in
V(\widetilde{H})}\varphi_{H}(\widetilde{H}-v)$.

###### Proof.

(1) For any $M\in\mathcal{M}(\widetilde{H})$, there exists
$M_{1}\in\mathcal{M}(\widetilde{H}_{1})$ and
$M_{2}\in\mathcal{M}(\widetilde{H}_{2})$ such that $M=M_{1}\cup M_{2}$. It is
easy to check that
$\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}_{1})\varphi_{H}(\widetilde{H}_{2})$.

(2) For any $M\in\mathcal{M}(\widetilde{H})$, if $M$ does not contain edge
$e$, then $M$ is a matching of $\widetilde{H}\setminus e$; if $M$ contain edge
$e$, then $M\setminus\\{e\\}$ is a matching of $\widetilde{H}-V(e)$. Thus, we
have

$\displaystyle\varphi_{H}(\widetilde{H})=$ $\displaystyle\sum_{e\notin
M\in\mathcal{M}(\widetilde{H})}(-1)^{(k-1)|M|}\prod_{v\in
V(\widetilde{H})\setminus V(M)}(\lambda-d_{H}(v))$ $\displaystyle+\sum_{e\in
M\in\mathcal{M}(\widetilde{H})}(-1)^{(k-1)|M|}\prod_{v\in
V(\widetilde{H})\setminus V(M)}(\lambda-d_{H}(v))$ $\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}(\widetilde{H}\setminus
e)}(-1)^{(k-1)|M|}\prod_{v\in V(\widetilde{H}\setminus e)\setminus
V(M)}(\lambda-d_{H}(v))$
$\displaystyle+\sum_{M\setminus\\{e\\}\in\mathcal{M}(\widetilde{H}-V(e))}(-1)^{(k-1)(|M\setminus\\{e\\}|+1)}\prod_{v\in
V(\widetilde{H}-V(e))\setminus V\left(M\setminus\\{e\\}\right)}(\lambda-
d_{H}(v))$ $\displaystyle=$ $\displaystyle\varphi_{H}(\widetilde{H}\setminus
e)+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e)).$

(3) Suppose that $I=\\{e_{1},\ldots,e_{s}\\}$. It follows from Theorem 3.7 (2)
that

$\displaystyle\varphi_{H}(\widetilde{H})$
$\displaystyle=\varphi_{H}(\widetilde{H}\setminus
e_{1})+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e_{1}))$
$\displaystyle=\varphi_{H}(\widetilde{H}\setminus\\{e_{1},e_{2}\\})+(-1)^{k-1}\varphi_{H}(\widetilde{H}\setminus
e_{1}-V(e_{2}))+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e_{1})).$

Since $\widetilde{H}\setminus e_{1}-V(e_{2})=\widetilde{H}-V(e_{2})$, we have

$\displaystyle\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}\setminus\\{e_{1},e_{2}\\})+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e_{2}))+(-1)^{k-1}\varphi_{H}(\widetilde{H}-V(e_{1})).$

Repeatedly using Theorem 3.7 (2), we get

$\displaystyle\varphi_{H}(\widetilde{H})=\varphi_{H}(\widetilde{H}\setminus
I)+(-1)^{k-1}\sum_{e\in I}\varphi_{H}(\widetilde{H}-V(e)).$ (3.2)

When $I=E_{\widetilde{H}}(v)$, the vertex $v$ is an isolated vertex on
$H\setminus I$. By (3.2) and Theorem 3.7 (1), we thus have that

$\displaystyle\varphi_{H}(\widetilde{H})=(\lambda-
d_{H}(v))\varphi_{H}(\widetilde{H}-v)+(-1)^{k-1}\sum_{e\in
E_{\widetilde{H}}(v)}\varphi_{H}(\widetilde{H}-V(e)).$

(4) By (3.1), we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\lambda}\varphi_{H}(\widetilde{H})$
$\displaystyle=\sum_{M\in\mathcal{M(\widetilde{H})}}\sum_{v\in
V(\widetilde{H})\setminus V(M)}(-1)^{(k-1)|M|}\prod_{v\neq u\in
V(\widetilde{H})\setminus V(M)}(\lambda-d_{H}(u))$
$\displaystyle=\sum_{M\in\mathcal{M(\widetilde{H})}}\sum_{v\in
V(\widetilde{H})\setminus V(M)}(-1)^{(k-1)|M|}\prod_{u\in
V(\widetilde{H}-v)\setminus V(M)}(\lambda-d_{H}(u)).$ (3.3)

For any $v\in V(\widetilde{H})$, a matching of $\widetilde{H}$ without $v$ is
a matching of $\widetilde{H}-v$. So $\mathcal{M}(\widetilde{H}-v)$ can be seen
as the set of all matchings without $v$ in $\widetilde{H}$. From (3), we
obtain

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\lambda}\varphi_{H}(\widetilde{H})$
$\displaystyle=\sum_{v\in
V(\widetilde{H})}\sum_{M\in\mathcal{M}(\widetilde{H}-v)}(-1)^{(k-1)|M|}\prod_{u\in
V(\widetilde{H}-v)\setminus V(M)}(\lambda-d_{H}(u))$ $\displaystyle=\sum_{v\in
V(\widetilde{H})}\varphi_{H}(\widetilde{H}-v).$

∎

Next, we will give a result about the zero roots of the Laplacian matching
polynomial of uniform hypertrees. For this we need a result about the
eigenvalues of principal sub-tensor of Laplacian tensor and the relationship
between the eigenvalue of weighted adjacency tensor and the weighted matching
polynomial.

For a non-empty $S\subseteq V(H)$, let $\mathcal{L}_{H}[S]=(l_{i_{1}\cdots
i_{k}})$ denote the $k$-order $|S|$-dimensional principal sub-tensor of
$\mathcal{L}_{H}$, where $i_{1},\ldots,i_{k}\in S$. When
$S=V(H)\setminus\\{v\\}$, $\mathcal{L}_{H}[S]$ is simply written as
$\mathcal{L}_{H}(v)$. A tensor is called a $\mathcal{Z}$-tensor if all of its
off-diagonal entries are non-positive. Clearly, $\mathcal{L}_{H}[S]$ is a
$\mathcal{Z}$-tensor for any non-empty $S\subseteq V(H)$. Applying some
properties of $\mathcal{Z}$-tensor, we obtain the following result.

######  Lemma 3.8.

Let $H$ be a uniform connected hypergraph. For any non-empty proper sub-set
$S\subset V(H)$, the real eigenvalues of $\mathcal{L}_{H}[S]$ are all greater
than zero.

###### Proof.

For any non-empty proper sub-set $S\subset V(H)$, let
$\tau(\mathcal{L}_{H}[S])$ denote the minimum real part of all eigenvalues of
$\mathcal{L}_{H}[S]$. For a non-empty proper sub-set $U\subset V(H)$
satisfying $U\supseteq S$, it is known that
$\tau(\mathcal{L}_{H}[U])\leq\tau(\mathcal{L}_{H}[S])$ [14, Theorem 3.1].
Thus, we have

$\displaystyle\min_{v\in
V(H)}\tau(\mathcal{L}_{H}(v))\leq\tau(\mathcal{L}_{H}[S]).$

By [8, Proposition 2.4], $\tau(\mathcal{L}_{H}(v))$ is the minimum
$\mathrm{H}$-eigenvalue of $\mathcal{L}_{H}(v)$ for any $v\in V(H)$. It is
shown that the minimum $\mathrm{H}$-eigenvalue of $\mathcal{L}_{H}(v)$ is
greater than zero for uniform connected hypergraph $H$ in [2, Lemma 2.1 and
Theorem 3.1]. Then we have $\tau(\mathcal{L}_{H}(v))>0$. Thus $0<\min_{v\in
V(H)}\tau(\mathcal{L}_{H}(v))\leq\tau(\mathcal{L}_{H}[S])$, which implies that
the real eigenvalues of $\mathcal{L}_{H}[S]$ are all greater than zero.

∎

For a $k$-uniform hypergraph $H$ and the weighting function
$\mathbf{w}:V(H)\cup E(H)\rightarrow\mathbb{C}$, Wan et al. [15] defined the
weighted adjacency tensor $\mathcal{A}_{H,\mathbf{w}}=(a_{i_{1}\ldots
i_{k}})$, where

$a_{i_{1}\cdots i_{k}}=\begin{cases}\mathbf{w}(v)&\text{if
$i_{1}=\cdots=i_{k}=v\in V(H)$},\\\ \frac{\mathbf{w}(e)}{(k-1)!}&\text{if
$\\{i_{1},\ldots,i_{k}\\}=e\in E(H)$},\\\ 0&\text{otherwise}.\end{cases}$

They determined all eigenvalues of the weighted adjacency tensor of uniform
hypertrees by means of the weighted matching polynomial.

######  Lemma 3.9.

[15, Theorem2] Let $T=(V(T),E(T))$ be a $k$-uniform hypertree for $k\geq 3$.
Let $\mathbf{w}:V(T)\cup E(T)\rightarrow\mathbb{C}$ be a weighting function on
$T$. Then $\lambda$ is an eigenvalue of $\mathcal{A}_{T,\mathbf{w}}$ if and
only if there exists a sub-hypertree $\widetilde{T}$ of $T$ (including
isolated vertices) such that $\lambda$ is a root of the weighted matching
polynomial

$\displaystyle\sum_{M\in\mathcal{M}(\widetilde{T})}(-1)^{|M|}\prod_{e\in
M}\mathbf{w}(e)^{k}\prod_{v\in V(\widetilde{T})\setminus
V(M)}(\lambda-\mathbf{w}(v)).$

We are now ready to derive the result as follows.

######  Theorem 3.10.

Let $T$ be a $k$-uniform hypertree. Then zero is a simple root of the
polynomial $\varphi_{T}(T)$. Moreover, zero is not a root of the polynomial
$\varphi_{T}(\widetilde{T})$ for any non-trivial sub-hypertree $\widetilde{T}$
of $T$.

###### Proof.

When $k=2$, $\varphi_{T}(T)$ is the Laplacian matching polynomial of tree $T$.
It is shown that $\varphi_{T}(T)$ is equal to the Laplacian characteristic
polynomial of $T$ in the [11, Theorem3.3]. Since zero is a simple root of the
Laplacian characteristic polynomial of $T$, zero is a simple root of
$\varphi_{T}(T)$. By [16, Theorem 2.7], for any non-trivial sub-tree
$\widetilde{T}$ of $T$, it is easy to check that $\varphi_{T}(\widetilde{T})$
is equal to the characteristic polynomial of the Laplacian principal sub-
matrix $L_{T}(w)$ of $T$. Since zero is not a root of the characteristic
polynomial of $L_{T}(w)$, zero is not a root of $\varphi_{T}(\widetilde{T})$.
In the following, we consider the case $k\geq 3$.

Clearly, for any sub-hypertree $\widetilde{T}$ of $T$, if we choose the
weighting function $\mathbf{w}$ on $\widetilde{T}$ such that
$\mathbf{w}(v)=d_{T}(v)$ for all $v\in V(\widetilde{T})$ and
$\mathbf{w}(e)=-1$ for all $e\in E(\widetilde{T})$, then
$\mathcal{A}_{\widetilde{T},\mathbf{w}}$ is exactly the principal sub-tensor
$\mathcal{L}_{T}[V(\widetilde{T})]$ of $\mathcal{L}_{T}$, and the weighted
matching polynomial of $\widetilde{T}$ is exactly
$\varphi_{T}(\widetilde{T})$. It follows from Lemma 3.9 that the roots of
$\varphi_{T}(\widetilde{T})$ is the eigenvalues of
$\mathcal{L}_{T}[V(\widetilde{T})]$. When $\widetilde{T}$ is a non-trivial
sub-hypertree of $T$, by Lemma 3.8, we know that zero is not the eigenvalue of
$\mathcal{L}_{T}[V(\widetilde{T})]$, which implies that zero is not a root of
the polynomial $\varphi_{T}(\widetilde{T})$. Since zero is a Laplacian
eigenvalue of $T$, by [15, Corollary4], there exists a sub-hypertree of $T$
such that zero is the root of the Laplacian matching polynomial of it with
respect to $T$. It is known that zero is not a root of
$\varphi_{T}(\widetilde{T})$ for any non-trivial sub-hypertree $\widetilde{T}$
of $T$, which implies that zero is a root of $\varphi_{T}(T)$. Next, we prove
that zero is a simple root of $\varphi_{T}(T)$.

By Theorem 3.7 (4), we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\lambda}\varphi_{T}(T)=\sum_{v\in
V(T)}\varphi_{T}(T-v).$ (3.4)

Given a vertex $v\in V(T)$, we know that $T-v$ is not connected and each
connected component is sub-hypertree of $T$. By Theorem 3.7 (1), the roots of
$\varphi_{T}(T-v)$ are the eigenvalues of $\mathcal{L}_{T}[V(T-v)]$. By Lemma
3.8, the real eigenvalues of $\mathcal{L}_{T}[V(T-v)]$ are all greater than
zero, which implies that all real roots of $\varphi_{T}(T-v)$ are greater than
zero. Note that $\varphi_{T}(T-v)$ is a real coefficient polynomial, whose all
of imaginary part non-zero complex roots occur in pairs. So the product of all
roots of $\varphi_{T}(T-v)$ is greater than zero. Let
$\lambda_{1}^{(v)},\ldots,\lambda_{|V(T)|-1}^{(v)}$ denote the roots of
$\varphi_{T}(T-v)$ for each $v\in V(T)$ and we have
$\lambda_{1}^{(v)}\cdots\lambda_{|V(T)|-1}^{(v)}>0$. Then the constant term of
the polynomial $\sum_{v\in V(T)}\varphi_{T}(T-v)$ is
$(-1)^{|V(T)|-1}\sum_{v\in
V(T)}\lambda_{1}^{(v)}\cdots\lambda_{|V(T)|-1}^{(v)}\neq 0$, which implies
that zero is not a root of $\sum_{v\in V(T)}\varphi_{T}(T-v)$. By (3.4), zero
is not a root of $\frac{\mathrm{d}}{\mathrm{d}\lambda}\varphi_{T}(T)$. Thus,
zero is a simple root of $\varphi_{T}(T)$.

∎

##  4 The multiplicity of the zero Laplacian eigenvalue of uniform hypertrees

In this section, we apply the Laplacian characteristic polynomial and the
Laplacian matching polynomial to give the multiplicity of the zero Laplacian
eigenvalue of uniform hypertrees, which shows that Conjecture 1.1 is true.

For a $k$-uniform hypertree $T=(V(T),E(T))$ and a vertex $w\in V(T)$, recall
that $F_{v}=F_{v}(x_{i}:i\in V(T))=(\lambda-d_{T}(v))x_{v}^{k-1}+\sum_{e\in
E_{T}(v)}\mathbf{x}_{e\setminus\\{v\\}}$ and $f_{v}=F_{v}|_{x_{w}=1}$ for all
$v\in V(T)$. Let $\mathcal{V}^{T}$ be the affine variety defined by the
polynomials $f_{v}$ for all $v\in V(T)\setminus\\{w\\}$. By Lemma 2.2, the
Laplacian characteristic polynomial of $T$ is

$\displaystyle\phi(\mathcal{L}_{T})$
$\displaystyle=\phi(\mathcal{L}_{T}(w))^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{T}}(\lambda-
d_{T}(w)+\sum_{e\in E_{T}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})}$
$\displaystyle=\phi(\mathcal{L}_{T}(w))^{k-1}\prod_{\mathbf{p}\in\mathcal{V}^{T}}f_{w}(\mathbf{p})^{m(\mathbf{p})}.$
(4.1)

From Lemma 3.8, we know that zero is not the eigenvalue of
$\mathcal{L}_{T}(w)$. Hence, in order to determine the multiplicity of the
zero Laplacian eigenvalue of $T$, we only need to consider
$\prod_{\mathbf{p}\in\mathcal{V}^{T}}f_{w}(\mathbf{p})^{m(\mathbf{p})}$ in
(4).

Let $\mathbf{p}=(p_{i})$ be a point in affine variety $\mathcal{V}^{T}$, and
let $\mathbf{q}=(q_{i})$ be a $|V(T)|$-dimensional vector with components
$q_{w}=1$ and $q_{i}=p_{i}$ for all $i\in V(T)\setminus\\{w\\}$. Then we have

$\displaystyle f_{w}(\mathbf{p})=F_{w}(q_{i}:i\in V(T))=F_{w}(\mathbf{q}),$

and $f_{v}(\mathbf{p})=F_{v}(q_{i}:i\in V(T))=F_{v}(\mathbf{q})=0$ for all
$v\in V(T)\setminus\\{w\\}$. When $\lambda=0$. If $F_{w}(\mathbf{q})=0$, then
$\mathbf{q}$ is an eigenvector corresponding to the zero Laplacian eigenvalue
of $T$. It is shown that all components of the eigenvector corresponding to
the zero Laplacian eigenvalue of a connected uniform hypergraph are non-zero
in the [9, Theorem 4.1 (i)]. Therefore, the all components of
$\mathbf{p}\in\mathcal{V}^{T}$ satisfying $f_{w}(\mathbf{p})=0$ are non-zero
when $\lambda=0$. It implies that the multiplicity of the zero Laplacian
eigenvalue of $T$ is only related to the points having all components non-zero
in $\mathcal{V}^{T}$.

######  Lemma 4.11.

Let $T$ be a $k$-uniform hypertree and $w$ be a vertex on $T$. If
$\mathbf{p}\in\mathcal{V}^{T}$ have all components non-zero, then

$\displaystyle\mathbf{p}_{e\setminus\\{w\\}}=\frac{(-1)^{k-1}\varphi_{T}(T-V(e))}{\varphi_{T}(T-w)}$

for each $e\in E_{T}(w)$.

###### Proof.

We prove the result by the induction on the number of edges of $T$.

When $|E(T)|=1$, we have $\varphi_{T}(T-w)=(\lambda-1)^{k-1}$ and
$\varphi_{T}(T-V(e))=1$ for the edge $e\in E_{T}(w)$. From (2.9), we know that
$\mathbf{p}_{e\setminus\\{w\\}}=(\frac{-1}{\lambda-1})^{k-1}$, which implies
that

$\displaystyle\mathbf{p}_{e\setminus\\{w\\}}=\frac{(-1)^{k-1}\varphi_{T}(T-V(e))}{\varphi_{T}(T-w)}.$

So the assertion holds.

Assuming that the result holds for any $|E(T)|\leq r$, we consider the case
$|E(T)|=r+1$.

When $w$ is a cut vertex of $T$, $T$ has $d_{T}(w)$$(>1)$ branches associated
with $w$ and each $e\in E_{T}(w)$ belongs to a distinct branch. Let
$\widetilde{T}_{i}$ be the branch of $T$ with edge $e_{i}\in E_{T}(w)$ for
each $i\in[d_{T}(w)]$ and we know that $|E(\widetilde{T}_{i})|\leq r$. By the
induction hypothesis, for $\mathbf{p}^{(i)}\in\mathcal{V}^{\widetilde{T}_{i}}$
having all components non-zero, we have

$\displaystyle\mathbf{p}^{(i)}_{e_{i}\setminus\\{w\\}}=\frac{(-1)^{k-1}\varphi_{\widetilde{T}_{i}}(\widetilde{T}_{i}-V(e_{i}))}{\varphi_{\widetilde{T}_{i}}(\widetilde{T}_{i}-w)}.$

By the definition of the Laplacian matching polynomial, we have
$\varphi_{\widetilde{T}_{i}}(\widetilde{T}_{i}-V(e_{i}))=\varphi_{T}(\widetilde{T}_{i}-V(e_{i}))$
and
$\varphi_{\widetilde{T}_{i}}(\widetilde{T}_{i}-w)=\varphi_{T}(\widetilde{T}_{i}-w)$.
Then

$\displaystyle\mathbf{p}^{(i)}_{e_{i}\setminus\\{w\\}}$
$\displaystyle=\frac{(-1)^{k-1}\varphi_{T}(\widetilde{T}_{i}-V(e_{i}))}{\varphi_{T}(\widetilde{T}_{i}-w)}$
$\displaystyle=\frac{(-1)^{k-1}\varphi_{T}(\widetilde{T}_{i}-V(e_{i}))\prod_{\begin{subarray}{c}j\in[d_{T}(w)]\\\
j\neq
i\end{subarray}}\varphi_{T}(\widetilde{T}_{j}-w)}{\prod_{j\in[d_{T}(w)]}\varphi_{T}(\widetilde{T}_{j}-w)}.$
(4.2)

Note that $T-w$ is the disjoint union of $\widetilde{T}_{i}-w$ for all
$i\in[d_{T}(w)]$, and $T-V(e_{j})$ is the disjoint union of
$\widetilde{T}_{j}-V(e_{j})$ and $\widetilde{T}_{i}-w$ for all $i\neq
j\in[d_{T}(w)]$. It follows from Theorem 3.7 (1) that

$\displaystyle\prod_{j\in[d_{T}(w)]}\varphi_{T}(\widetilde{T}_{j}-w)=\varphi_{T}(T-w),$

and

$\displaystyle\varphi_{T}(\widetilde{T}_{i}-V(e_{i}))\prod_{\begin{subarray}{c}j\in[d_{T}(w)]\\\
j\neq
i\end{subarray}}\varphi_{T}(\widetilde{T}_{j}-w)=\varphi_{T}(T-V(e_{i})).$

By Theorem 2.5 and (4), for $\mathbf{p}\in\mathcal{V}^{T}$ having all
components non-zero, we get

$\displaystyle\mathbf{p}_{e_{i}\setminus\\{w\\}}=\mathbf{p}^{(i)}_{e_{i}\setminus\\{w\\}}=\frac{(-1)^{k-1}\varphi_{T}(T-V(e_{i}))}{\varphi_{T}(T-w)}.$

When $w$ is not a cut vertex of $T$, the degree of $w$ is clearly one. Let the
edge $\widehat{e}=\\{v_{1},\ldots,v_{k-1},w\\}$. Then $T\setminus\widehat{e}$
has $k$ connected components and we use $\widehat{T}_{t}$ to denote the
connected component containing $v_{t}$ for each $t\in[k]$.

For all $v\in V(T)$, recall that $F_{v}=F_{v}(x_{i}:i\in V(T))=(\lambda-
d_{T}(v))x_{v}^{k-1}+\sum_{e\in E_{T}(v)}\mathbf{x}_{e\setminus\\{v\\}}$ and
$f_{v}=F_{v}|_{x_{w}=1}$. For all $t\in[k-1]$ and any $v\in
V(\widehat{T}_{t})\setminus\\{v_{t}\\}$, note that $f_{v}=f_{v}(x_{i}:i\in
V(\widehat{T}_{t}))$ is a homogeneous polynomial. Since
$\mathbf{p}=(p_{i})\in\mathcal{V}^{T}$ have all components non-zero, we get

$\displaystyle f_{v}(\mathbf{p})=f_{v}(p_{i}:i\in
V(\widehat{T}_{t}))=f_{v}\left(\frac{p_{i}}{p_{v_{t}}}:i\in
V(\widehat{T}_{t})\right)=0.$ (4.3)

Fix $t\in[k-1]$, we consider the sub-hypertree $\widehat{T}_{t}$. For all
$v\in V(\widehat{T}_{t})\setminus\\{v_{t}\\}$, let
$\widehat{F}_{v}=\widehat{F}_{v}(x_{i}:i\in V(\widehat{T}_{t}))=(\lambda-
d_{\widehat{T}_{t}}(v))x_{v}^{k-1}+\sum_{e\in
E_{\widehat{T}_{t}}(v)}\mathbf{x}_{e\setminus\\{v\\}}$ and
$\widehat{f}_{v}=\widehat{F}_{v}|_{x_{v_{t}}=1}$. It is easy to check that
$\widehat{F}_{v}=f_{v}$. Let $q_{i}=\frac{p_{i}}{p_{v_{t}}}$ for all $i\in
V(\widehat{T}_{t})$ and note that $q_{v_{t}}=1$. By (4.3), we have

$\displaystyle\widehat{f}_{v}(q_{i}:i\in
V(\widehat{T}_{t})\setminus\\{v_{t}\\})=\widehat{F}_{v}(q_{i}:i\in
V(\widehat{T}_{t}))=f_{v}(q_{i}:i\in V(\widehat{T}_{t}))=0$ (4.4)

for all $v\in V(\widehat{T}_{t})\setminus\\{v_{t}\\}$. Let the vector
$\mathbf{q}=(q_{i})$ for $i\in V(\widehat{T}_{t})\setminus\\{v_{t}\\}$. Then
$\mathbf{q}$ is a point in the affine variety $\mathcal{V}^{\widehat{T}_{t}}$
defined by the polynomials $\widehat{f}_{v}$ for all $v\in
V(\widehat{T}_{t})\setminus\\{v_{t}\\}$, and the all components of
$\mathbf{q}$ are non-zero. By the induction hypothesis, for each $e\in
E_{\widehat{T}_{t}}(v_{t})$, we have

$\displaystyle\mathbf{q}_{e\setminus\\{v_{t}\\}}=\frac{(-1)^{k-1}\varphi_{\widehat{T}_{t}}(\widehat{T}_{t}-V(e))}{\varphi_{\widehat{T}_{t}}(\widehat{T}_{t}-v_{t})}.$

By the definition of the Laplacian matching polynomial, we have
$\varphi_{\widehat{T}_{t}}(\widehat{T}_{t}-V(e))=\varphi_{T}(\widehat{T}_{t}-V(e))$
and
$\varphi_{\widehat{T}_{t}}(\widehat{T}_{t}-v_{t})=\varphi_{T}(\widehat{T}_{t}-v_{t})$.
Then

$\displaystyle\mathbf{q}_{e\setminus\\{v_{t}\\}}=\frac{(-1)^{k-1}\varphi_{T}(\widehat{T}_{t}-V(e))}{\varphi_{T}(\widehat{T}_{t}-v_{t})}=\frac{\mathbf{p}_{e\setminus\\{v_{t}\\}}}{p_{v_{t}}^{k-1}}.$

Thus, for $\mathbf{p}\in\mathcal{V}^{T}$ having all components non-zero and
each $e\in E_{\widehat{T}_{t}}(v_{t})$, we get

$\displaystyle\mathbf{p}_{e\setminus\\{v_{t}\\}}=\frac{(-1)^{k-1}\varphi_{T}(\widehat{T}_{t}-V(e))}{\varphi_{T}(\widehat{T}_{t}-v_{t})}p_{v_{t}}^{k-1}.$
(4.5)

For each $t\in[k-1]$, recall that

$\displaystyle f_{v_{t}}(\mathbf{p})=(\lambda-
d_{T}(v_{t}))p_{v_{t}}^{k-1}+\mathbf{p}_{\widehat{e}\setminus\\{v_{t},w\\}}+\sum_{e\in
E_{\widehat{T}_{t}}(v_{t})}\mathbf{p}_{e\setminus\\{v_{t}\\}}=0.$

By (4.5) and Theorem 3.7 (3), we have

$\displaystyle\mathbf{p}_{\widehat{e}\setminus\\{v_{t},w\\}}$
$\displaystyle=-\left(\lambda-d_{T}(v_{t})+\sum_{e\in
E_{\widehat{T}_{t}}(v_{t})}\frac{(-1)^{k-1}\varphi_{T}(\widehat{T}_{t}-V(e))}{\varphi_{T}(\widehat{T}_{t}-v_{t})}\right)p_{v_{t}}^{k-1}$
$\displaystyle=-\frac{\varphi_{T}(\widehat{T}_{t})}{\varphi_{T}(\widehat{T}_{t}-v_{t})}p_{v_{t}}^{k-1}.$

Combining these equations for all $t\in[k-1]$, we get

$\displaystyle\prod_{t=1}^{k-1}\mathbf{p}_{\widehat{e}\setminus\\{v_{t},w\\}}$
$\displaystyle=(-1)^{k-1}\prod_{t=1}^{k-1}\frac{\varphi_{T}(\widehat{T}_{t})}{\varphi_{T}(\widehat{T}_{t}-v_{t})}p_{v_{t}}^{k-1}.$

Since
$\prod_{t=1}^{k-1}\mathbf{p}_{\widehat{e}\setminus\\{v_{t},w\\}}=\prod_{t=1}^{k-1}p_{v_{t}}^{k-2}$,
we have

$\displaystyle\mathbf{p}_{\widehat{e}\setminus\\{w\\}}=\frac{\prod_{t=1}^{k-1}p_{v_{t}}^{k-1}}{\prod_{t=1}^{k-1}\mathbf{p}_{\widehat{e}\setminus\\{v_{t},w\\}}}=(-1)^{k-1}\prod_{t=1}^{k-1}\frac{\varphi_{T}(\widehat{T}_{t}-v_{t})}{\varphi_{T}(\widehat{T}_{t})}.$

Note that for all $t\in[k-1]$, the disjoint union of $\widehat{T}_{t}-v_{t}$
is $T-V(\widehat{e})$ and the disjoint union of $\widehat{T}_{t}$ is $T-w$. It
follows from Theorem 3.7 (1) that

$\displaystyle\mathbf{p}_{\widehat{e}\setminus\\{w\\}}=\frac{(-1)^{k-1}\varphi_{T}(T-V(\widehat{e}))}{\varphi_{T}(T-w)}.$

∎

For the point $\mathbf{p}\in\mathcal{V}^{T}$, we have
$f_{w}(\mathbf{p})=\lambda-d_{T}(w)+\sum_{e\in
E_{T}(w)}\mathbf{p}_{e\setminus\\{w\\}}$. If $\mathbf{p}$ have all components
non-zero, by Lemma 4.11 and Theorem 3.7 (3), we get

$\displaystyle f_{w}(\mathbf{p})$ $\displaystyle=\lambda-d_{T}(w)+\sum_{e\in
E_{T}(w)}\frac{(-1)^{k-1}\varphi_{T}(T-V(e))}{\varphi_{T}(T-w)}$
$\displaystyle=\frac{\varphi_{T}(T)}{\varphi_{T}(T-w)}.$ (4.6)

Note that $T-w$ is not connected and each connected component is a non-trivial
sub-hypertree of $T$. From Theorem 3.7 (1) and Theorem 3.10, we know that zero
is not the root of $\varphi_{T}(T-w)$ and is a simple root of
$\varphi_{T}(T)$. Let $n_{0}(T)$ denote the multiplicity of the zero Laplacian
eigenvalue of $T$. Since $n_{0}(T)$ is only related to $\mathbf{p}$ having all
components non-zero in $\mathcal{V}^{T}$, combining (4) with (4), we have

$\displaystyle
n_{0}(T)=\sum_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{T}\\\ \forall
p_{i}\neq 0\end{subarray}}m(\mathbf{p}),$ (4.7)

where $m(\mathbf{p})$ is the multiplicity of $\mathbf{p}=(p_{i})$ in
$\mathcal{V}^{T}$.

We are now ready to determine the multiplicity of the zero Laplacian
eigenvalue of $T$.

######  Theorem 4.12.

Let $T=(V(T),E(T))$ be a $k$-uniform hypertree. Then the multiplicity of the
zero Laplacian eigenvalue of $T$ is $k^{|E(T)|(k-2)}$.

###### Proof.

We prove the result by the induction on the number of edges of $T$.

When $|E(T)|=1$. It is shown that the multiplicity of the zero Laplacian
eigenvalue of $T$ is $k^{k-2}$ in the [18, Theorem 4.9]. So the assertion
holds.

Assuming that the result holds when $|E(T)|=r$, we consider the case
$|E(T)|=r+1$.

Let $w$ be a non-pendent vertex on a pendant edge of $T$, and $\widetilde{T}$
denote the $k$-uniform hypertree obtained by removing this pendant edge and
pendent vertices on it from $T$. By Corollary 2.6, the Laplacian
characteristic polynomial of $T$ is

$\displaystyle\phi(\mathcal{L}_{T})=$
$\displaystyle(\lambda-1)^{(k-1)^{(r+1)(k-1)+1}}\phi(\mathcal{L}_{\widetilde{T}}(w))^{(k-1)^{k}}\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{T}}}(\lambda-
d_{T}(w)+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})K_{1}}$
$\displaystyle\times\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{T}}}(\lambda-
d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})K_{2}},$
(4.8)

where $K_{1}=(k-1)^{k-1}-k^{k-2}$ and $K_{2}=k^{k-2}$.

Clearly, $w$ is a cut vertex on $T$. Suppose that the branches of $T$
associated with $w$ are $\widetilde{T}$ and a one-edge hypergraph, denoted by
$T^{\prime}$. By (2.3), we know that
$\mathcal{V}^{T}=\mathcal{V}^{\widetilde{T}}\times\mathcal{V}^{T^{\prime}}$.
Then we have $\mathbf{r}=\left(\begin{matrix}\mathbf{p}\\\
\mathbf{q}\end{matrix}\right)$ for any $\mathbf{r}\in\mathcal{V}^{T}$, where
$\mathbf{p}\in\mathcal{V}^{\widetilde{T}}$,
$\mathbf{q}\in\mathcal{V}^{T^{\prime}}$. It is known from (4.7) that the
multiplicity of the zero Laplacian eigenvalue of $T$ is only related to
$\mathbf{r}\in\mathcal{V}^{T}$ having all components non-zero. By (2.2), it
implies that we only need to consider

$\displaystyle\prod_{\mathbf{p}\in\mathcal{V}^{\widetilde{T}}}(\lambda-
d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}})^{m(\mathbf{p})K_{2}}$
(4.9)

in (4) and $\mathbf{p}$ have all components non-zero in
$\mathcal{V}^{\widetilde{T}}$.

By Lemma 4.11, for $\mathbf{p}\in\mathcal{V}^{\widetilde{T}}$ having all
components non-zero, we have

$\displaystyle\lambda-d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}}$ $\displaystyle=$
$\displaystyle\lambda-d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\frac{(-1)^{k-1}\varphi_{\widetilde{T}}(\widetilde{T}-V(e))}{\varphi_{\widetilde{T}}(\widetilde{T}-w)}.$

By the definition of the Laplacian matching polynomial, we know
that$\varphi_{\widetilde{T}}(\widetilde{T}-w)=\varphi_{T}(\widetilde{T}-w)$
and
$\varphi_{\widetilde{T}}(\widetilde{T}-V(e))=\varphi_{T}(\widetilde{T}-V(e))$
for each $e\in E_{\widetilde{T}}(w)$. It follows from Theorem 3.7 (3) that

$\displaystyle\lambda-d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}}$ $\displaystyle=$
$\displaystyle\frac{(\lambda-1)^{k-1}\varphi_{T}(\widetilde{T})+(-1)^{k-1}\varphi_{T}(\widetilde{T}-w)}{(\lambda-1)^{k-1}\varphi_{T}(\widetilde{T}-w)}.$
(4.10)

Let pendant edge $\widetilde{e}=\\{v_{1},\ldots,v_{k-1},w\\}$, where
$v_{1},\ldots,v_{k-1}$ are the pendent vertices. Note that the Laplacian
matching polynomial of $v_{i}$ with respect to $T$ is $\lambda-1$ for each
$i\in[k-1]$. Since the disjoint union of $\widetilde{T}-w$ and $v_{i}$ for all
$i\in[k-1]$ is $T-w$, by Theorem 3.7 (1), we have

$\displaystyle(\lambda-1)^{k-1}\varphi_{T}(\widetilde{T}-w)=\varphi_{T}(T-w).$

Since
$(\lambda-1)^{k-1}\varphi_{T}(\widetilde{T})+(-1)^{k-1}\varphi_{T}(\widetilde{T}-w)=(\lambda-
d_{T}(v_{i}))\varphi_{T}(T-v_{i})+(-1)^{k-1}\varphi_{T}(T-V(\widetilde{e}))$
for any $i\in[k-1]$, by Theorem 3.7 (3), we have

$\displaystyle(\lambda-1)^{k-1}\varphi_{T}(\widetilde{T})+(-1)^{k-1}\varphi_{T}(\widetilde{T}-w)=\varphi_{T}(T).$

From (4), for $\mathbf{p}\in\mathcal{V}^{\widetilde{T}}$ having all components
non-zero, we obtain

$\displaystyle\lambda-d_{T}(w)+(\frac{-1}{\lambda-1})^{k-1}+\sum_{e\in
E_{\widetilde{T}}(w)}\mathbf{p}_{e\setminus\\{w\\}}$
$\displaystyle=\frac{\varphi_{T}(T)}{\varphi_{T}(T-w)}.$

Note that $T-w$ is not connected and each connected component is a non-trivial
sub-hypertree of $T$. It is known from Theorem 3.7 (1) and Theorem 3.10 that
zero is not the root of $\varphi_{T}(T-w)$ and is a simple root of
$\varphi_{T}(T)$. By (4.9), we get

$\displaystyle
n_{0}(T)=k^{k-2}\sum_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{T}}\\\
\forall p_{i}\neq 0\end{subarray}}m(\mathbf{p}).$

It follows from (4.7) that
$\sum_{\begin{subarray}{c}\mathbf{p}\in\mathcal{V}^{\widetilde{T}}\\\ \forall
p_{i}\neq 0\end{subarray}}m(\mathbf{p})=n_{0}(\widetilde{T})$. By the
induction hypothesis, we have $n_{0}(\widetilde{T})=k^{r(k-2)}$. Thus,
$n_{0}(T)=k^{k-2}n_{0}(\widetilde{T})=k^{(r+1)(k-2)}$.

∎

## References

## References

  * [1] Y. Bao, Y. Fan, Y. Wang, and M. Zhu.  A combinatorial method for computing characteristic polynomials of starlike hypergraphs.  Journal of Algebraic Combinatorics, 51(4):589–616, 2020.
  * [2] C. Bu, H. Li, and J. Zhou.  Inverse Perron values and connectivity of a uniform hypergraph.  The Electronic Journal of Combinatorics, 25(4), 2018.  Article ID # P4.28.
  * [3] L. Chen and C. Bu.  A reduction formula for the characteristic polynomial of hypergraph with pendant edges.  Linear Algebra and its Applications, 611:171–186, 2021.
  * [4] G. Clark and J. Cooper.  On the adjacency spectra of hypertrees.  The Electronic Journal of Combinatorics, 25(2), 2018.  Article ID #P2.48.
  * [5] J. Cooper and A. Dutle.  Spectra of uniform hypergraphs.  Linear Algebra and its Applications, 436(9):3268–3292, 2012.
  * [6] J. Cooper and A. Dutle.  Computing hypermatrix spectra with the Poisson product formula.  Linear and Multilinear Algebra, 63(5):956–970, 2015.
  * [7] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky.  Discriminants, Resultants and Multidimensional Determinants.  Birkhäuser, Boston, 1994.
  * [8] M.S. Gowda, Z. Luo, L. Qi, and N. Xiu.  Z-tensors and complementarity problems.  arXiv:1510.07933v2, 2015.
  * [9] S. Hu and L. Qi.  The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph.  Discrete Applied Mathematics, 169:140–151, 2014.
  * [10] L. Lim.  Singular values and eigenvalues of tensors: a variational approach.  In 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, pages 129–132. IEEE, 2005.
  * [11] A. Mohammadian.  Laplacian matching polynomial of graphs.  Journal of Algebraic Combinatorics, 52(1):33–39, 2020.
  * [12] L. Qi.  Eigenvalues of a real supersymmetric tensor.  Journal of Symbolic Computation, 40(6):1302–1324, 2005.
  * [13] L. Qi.  $H^{+}$-eigenvalues of Laplacian and signless Laplacian tensors.  Communications In Mathematical Sciences, 12(6):1045–1064, 2014\.
  * [14] J. Shen, Y. Wang, and C. Bu.  Some inequalities on the minimum H-eigenvalue of the Fan product of Z-tensors.  Linear Algebra and its Applications, 579:55–71, 2019.
  * [15] J. Wan, Y. Wang, and F. Hu.  Spectra of weighted uniform hypertrees.  The Electronic Journal of Combinatorics, 29(2), 2022.  Article ID # P2.40.
  * [16] J. Wan, Y. Wang, and A. Mohammadian.  On the location of zeros of the Laplacian matching polynomials of graphs.  Journal of Algebraic Combinatorics, 56(3):755–771, 2022.
  * [17] W. Zhang, L. Kang, E. Shan, and Y. Bai.  The spectra of uniform hypertrees.  Linear Algebra and its Applications, 533:84–94, 2017.
  * [18] Y. Zheng.  The zero eigenvalue of the Laplacian tensor of a uniform hypergraph.  Linear and Multilinear Algebra, 2023.  Doi:10.1080/03081087.2023.2172541.


# A Note on Unconditional Subexponential-Time Pseudo-deterministic Algorithms
for BPP Search Problems

Dhiraj Holden

###### Abstract

We show the first unconditional pseudo-determinism result for all of search-
BPP. Specifically, we show that every BPP search problem can be computed
pseudo-deterministically on average for infinitely many input lengths. In
other words, for infinitely many input lengths and for any polynomial-time
samplable distribution our algorithm succeeds in producing a unique answer (if
one exists) with high probability over the distribution and the coins tossed.

##  1 Introduction

Gat and Goldwasser [1] introduced the notion of pseudo-deterministic
algorithms for search problems; a pseudo-deterministic algorithm $A(x,r)$ has
the property that $\Pr_{r_{1},r_{2}}[A(x,r_{1})=A(x,r_{2})]\geq 1-1/poly(n)$,
which means that the algorithm finds the same output with high probability
over the randomness. The concept of pseudo-deterministic algorithms has been
well-studied, giving pseudo-deterministic algorithms that improve on
deterministic algorithms for a wide variety of problems such as finding non-
zero evaluations of multi-variate polynomials, finding primitive roots of
primes, and finding bipartite matchings in parallel [5, 2, 3, 1, 4].

Recently, Oliveira and Santhanam [9] show that for the general question “given
length $n$, find a string of length $n$ with a pre-specified dense property”,
pseudo-deterministic algorithms exist which for infinitely many lengths $n$
yield a unique string with said property of length $n$ with high probability.
An example of such a dense property is the set of prime numbers.

The major open question is this: does every BPP search problem have a
polynomial-time pseudodeterministic algorithm? In this work we will show that
every BPP search problem has an algorithm for infinitely many input lengths
running in subexponential time that for every polynomial-time samplable
distribution produces a unique answer with high probability on inputs drawn
from the distribution and over the random coins.

This work expands on the work of Oliveira and Santhanam. [9] give a pseudo-
deterministic algorithm for estimating the acceptance probability of a
circuit; we extend their work to general search-BPP problems, where the input
is a string over some alphabet and our algorithm outputs a string that
satisfies a relation with the input. We combine this with the algorithm to
generate canonical samples from a polynomial-time samplable distribution given
in [9] to achieve an average-case pseudo-deterministic algorithm for every
problem in search-BPP.

###  1.1 Outline of the proof

The proof of our main theorem uses techniques from [9] and extends them to the
case of general search-BPP problems, in particular the results of [6, 10] on
pseudorandomness assuming uniform assumptions. There are two cases to the
proof; either PSPACE is contained in subexponential-time BPP, or it is not. In
the first case we can use this to get subexponential-size circuit lower bounds
for BPE, which extending an argument of [9] implies a subexponential-time
pseudo-deterministic algorithm for every search-BPP problem on infinitely many
input lengths. If PSPACE is not contained in subexponential-time BPP, [10]
gives a construction of a pseudorandom generator which is not distinguishable
uniformly for infinitely many input lengths. This implies that in particular,
the search-BPP algorithm cannot distinguish the output of the PRG from uniform
when fed inputs from any polynomial-time samplable distribution, which we use
to construct an algorithm running in subexponential time that for infinitely
many input lengths outputs a unique answer with high probability over the
input distribution and the randomness of the algorithm when the input is drawn
from any polynomial-time samplable distribution.

##  2 Preliminaries

In this section we will define the notions used in this paper. We will define
pseudo-determinism for BPP search problems and the notion of average-case
complexity we will use. First, we will define a search problem.

######  Definition 2.1 (Search Problem).

A search problem is a relation $R$ consisting of pairs $(x,y)$. We say that an
algorithm $A$ solves a search problem $R$ if $(x,A(x))\in R$ for all $x$.

With this definition, we can now given the definition of search-BPP.

######  Definition 2.2 (Search-BPP).

A binary relation $R$ is in search-BPP if there exists an algorithm $A$
running in probabilistic polynomial time that for every $x$ outputs a $y$ such
that $(x,y)\in R$ with probability at least 2/3, and there exists a BPP
machine $B$ such that if it accepts on input $(x,y)$, then $(x,y)\in R$ and
also $B$ accepts $(x,A(x,r))$ with probability at least 1/2.

A pseudo-deterministic search-BPP problem is a search-BPP problem with a
pseudo-deterministic algorithm, or an algorithm which outputs the same $y$
with high probability.

######  Definition 2.3 (Pseudo-deterministic search-BPP).

A search-BPP relation $R$ is in
pseudo-deterministic search-BPP if there exists an algorithm $A$ such that for
every $x$ there exists a $y$ such that $(x,y)\in R$ and $\Pr[A(x,r)=y]\geq
1/2$.

To obtain the best running time for our pseudo-deterministic algorithm, we
will need the iterated exponential functions first used in complexity theory
by [8]. We will be considering functions with half-exponential growth, i.e.
functions $f$ such that $f(f(n))\in O(2^{n^{k}})$ for some $k$.

######  Definition 2.4 (Fractional exponentials [8]).

The fractional exponential function $e_{\alpha}(x)$ will be defined as
$A^{-1}(A(x)+\alpha)$, where $A$ is the solution to the functional equation
$A(e^{x}-1)=A(x)+1$. In addition, we can construct such functions so that
$e_{\alpha}(e_{\beta}(x))=e_{\alpha+\beta}(x)$. It is clear from this
definition that $e_{1}(n)=O(2^{n})$ as desired.

In addition, we also need to talk about average-case complexity for search
problems. Average-case complexity is defined over a given distribution, though
our results will extend to every polynomial-time samplable distribution.

######  Definition 2.5 (Average-case search-BPP).

We say that a search problem given by a relation $R$ is in
HeurBPTIME($t(n)$,$\delta(n)$) for a given distribution $\mathcal{D}$ if there
is some algorithm $A$ running in time $t(n)$ such that $\Pr_{x\leftarrow
D_{|x|},r}[(x,A(x,r))\in R]\geq 1-\delta(n)$, and there exists a BPP machine
$B$ such that if it accepts on input $(x,y)$, then $(x,y)\in R$ and also $B$
accepts $(x,A(x,r))$ with probability at least 1/2.

We can define average-case pseudo-deterministic search-BPP in a similar
fashion by requiring that $A(x,r)$ be unique with high probability.

######  Definition 2.6 (Average-case pseudo-deterministic search-BPP).

We say that a search problem given by a relation $R$ is in
HeurPsdTIME($t(n)$,$\delta(n)$) for a given distribution $\mathcal{D}$ if
there is some algorithm $A$ running in time $t(n)$ such that for every $x$
there exists a $y(x)$ such that $(x,y)\in R$ and $\Pr_{x\leftarrow
D_{|x|},r}[A(x,r)=y(x)]\geq 1-\delta(n)$.

The final result that we need is a statement of [10] about a pseudorandom
generator based on hardness for PSPACE.

######  Theorem 2.7 (Corollary 4.4 of [10]).

For every function $f\in\mathrm{PSPACE}$, there is a constant $d$ such that if
$f\notin\cup_{c}\mathrm{BPTIME}(t(n^{d})^{c})$, then there is a generator $G$
with stretch $t(\cdot)$ that cannot be $1/t(\cdot)^{c}$-distinguished
uniformly in time $t(\cdot)^{c}$ for any constant $c$.

##  3 Results

In this section we will show that every relation $R$ in search-BPP is
contained in
HeurPsdTIME($e_{1/2+\epsilon}(n)$,$\frac{1}{poly(n)}$) for infinitely many
input lengths for every polynomial-time samplable distribution.

######  Theorem 3.1.

Let $R$ be a relation in search-BPP. Then for every polynomial-time samplable
distribution $\mathcal{D}$, and for every $\epsilon>0$, $R$ is contained in
HeurPsdTIME($e_{1/2+\epsilon}(n)$,$\frac{1}{poly(n)}$) for infinitely many
input lengths.

###### Proof.

There are two cases to the proof. Suppose that
$\mathrm{PSPACE}\subseteq\mathrm{BPTIME}(e_{1/2+\epsilon}(n))$. Then, padding
implies that $\mathrm{SPACE}(e_{1/2-\epsilon}(n))\subseteq\mathrm{BPE}$, which
in turn implies $\mathrm{BPE}$ cannot be approximated by
$e_{1/2-\epsilon}(n)$-size circuits. [9] notes that this fact implies that any
search-BPP relation can be solved pseudo-deterministically in time
$O(e_{1/2+\epsilon}(n))$ for infinitely many input lengths. Now, suppose that
$\mathrm{PSPACE}\nsubseteq\mathrm{BPTIME}(e_{1/2+\epsilon}(n))$. Then, by
Theorem 2.7, this means that there is a generator $G$ with stretch
$e_{1/2+\epsilon}(\cdot)$ that cannot be
$1/e_{1/2+\epsilon}(\cdot)^{c}$-distinguished in time
$e_{1/2+\epsilon}(\cdot)$. Then, we claim that the following algorithm is a
HeurPsdTIME($e_{1/2+\epsilon}(n)$,$\frac{1}{poly(n)}$) algorithm for
infinitely many input lengths. Let us call the search algorithm of $R$ $A$ and
the verification algorithm of $R$ $B$. We will use the version of $B$
amplified to a $1-exp(n)$ success probability. Iterate through the
$e_{1/2-\epsilon}(\cdot)$ outputs of $G$ as the randomness, and output the
first $A(x,r)$ such that $B$ accepts $(x,A(x,r))$. Suppose that this algorithm
is not a HeurPsdTIME($e_{1/2+\epsilon}(n)$,$\frac{1}{poly(n)}$) algorithm for
infinitely many input lengths. Then, this means that this algorithm fails for
large enough input lengths, which means that the output of this algorithm is
not correct or not unique with high probability over the distribution and the
randomness. Since $B$ accepts all $(x,y)\in R$ with high probability, this
means that with high probability the first $A(x,r)$ such that $B$ accepts
$(x,A(x,r))$ is also the first $A(x,r)$ such that $(x,A(x,r))\in R$. Now, it
suffices to show that there exists such an $A(x,r)$. If no such $A(x,r)$
exists, then $\Pr_{r\leftarrow G}[B((x,A(x,r))=1]\leq exp(-n)$, and
$\Pr_{r\leftarrow U}[B(x,A(x,r))=1]\geq c$ for some constant $c$ by the
correctness guarantees of $A$ and $B$. Thus, if no such $A(x,r)$ exists,
$B(x,A(x,r))$ with $x$ drawn from some polynomial-time samplable distribution
is a uniform algorithm which distinguishes between the output of $G$ and the
uniform distribution, contradicting the fact that $G$ is indistinguishable.
Thus the algorithm is a HeurPsdTIME($e_{1/2+\epsilon}(n)$,$\frac{1}{poly(n)}$)
for infinitely many input lengths. ∎

##  4 Open Problems

It is open whether this result can be improved further by showing a faster
algorithm, making the algorithm work more than just infinitely often, or by
giving a worst-case rather than an average-case algorithm. We believe that
this would require new techniques in the theory of pseudorandomness. In
addition, it is open whether pseudo-deterministic simulation of general
search-BPP problems implies circuit lower bounds, or if a theorem similar to
that of [7] showing that derandomization implies either circuit lower bounds
for NEXP or arithmetic circuit lower bounds for computing the permanent can be
proven. If so, this will require substantially different techniques than [7],
as finding a non-zero value of a polynomial is known to be in pseudo-
deterministic polynomial time.

## Acknowledgements

I would like to thank Shafi Goldwasser, Ofer Grossman, and Rahul Santhanam for
valuable comments on this work. This work was supported by NSF MACS -
CNS-1413920 and the SIMONS Investigator award Agreement Dated 6-5-12.

## References

  * [1] Eran Gat and Shafi Goldwasser.  Probabilistic search algorithms with unique answers and their cryptographic applications.  In Electronic Colloquium on Computational Complexity (ECCC), volume 18, page 136, 2011.
  * [2] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  On the possibilities and limitations of pseudodeterministic algorithms.  In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 127–138. ACM, 2013.
  * [3] Shafi Goldwasser and Ofer Grossman.  Perfect bipartite matching in pseudo-deterministic rnc.  In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 208, 2015.
  * [4] Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden.  Pseudo-deterministic proofs.
  * [5] Ofer Grossman.  Finding primitive roots pseudo-deterministically.  In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 207, 2015.
  * [6] Russell Impagliazzo and Avi Wigderson.  Randomness vs. time: De-randomization under a uniform assumption.  In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 734–743. IEEE, 1998.
  * [7] Valentine Kabanets and Russell Impagliazzo.  Derandomizing polynomial identity tests means proving circuit lower bounds.  Computational Complexity, 13(1-2):1–46, 2004.
  * [8] Peter Bro Miltersen, N Variyam Vinodchandran, and Osamu Watanabe.  Super-polynomial versus half-exponential circuit size in the exponential hierarchy.  In International Computing and Combinatorics Conference, pages 210–220. Springer, 1999.
  * [9] Igor C Oliveira and Rahul Santhanam.  Pseudodeterministic constructions in subexponential time.  arXiv preprint arXiv:1612.01817, 2016.
  * [10] Luca Trevisan and Salil Vadhan.  Pseudorandomness and average-case complexity via uniform reductions.  Computational Complexity, 16(4):331–364, 2007.