$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E\right]\cdot\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nQ)}{\zeta}}\right)+\frac{1}{nQ^{2}}.$

###### Proof.

For any $i\in[n]$, let $Z_{i,1},\dots,Z_{i,T_{\mathcal{A},x_{i}}}$ denote the
observed $T_{\mathcal{A},x_{i}}$ samples on arm $x_{i}$, and define event

$L_{i}=\left\\{\sum_{t=1}^{T_{\mathcal{A},x_{i}}}Z_{i,t}\geq
T_{\mathcal{A},x_{i}}\cdot\phi(x_{i})^{\top}\theta/\kappa+\frac{z}{\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}}\right\\},$

where $z\geq 0$ is a parameter specified later. We also define event
$L=\cap_{i\in[n]}L_{i}$. Then,

$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E\right]\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E,L\right]+\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[\neg
L\right]$

Using the measure change technique, we bound the term
$\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E,L\right]$
as

$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E,L\right]$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(-\frac{1}{2}\sum_{i\in[n]}\sum_{t=1}^{T_{\mathcal{A},x_{i}}}\left((Z_{i,t}-\phi(x_{i})^{\top}\theta/\kappa)^{2}-(Z_{i,t}-\phi(x_{i})^{\top}\theta^{*})^{2}\right)\right)$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(-\frac{1}{2}\sum_{i\in[n]}\sum_{t=1}^{T_{\mathcal{A},x_{i}}}\left((\phi(x_{i})^{\top}\theta/\kappa)^{2}-(\phi(x_{i})^{\top}\theta^{*})^{2}-2Z_{i,t}(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*})\right)\right)$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\Bigg{(}-\frac{1}{2}\sum_{i\in[n]}\Bigg{(}\left((\phi(x_{i})^{\top}\theta/\kappa)^{2}-(\phi(x_{i})^{\top}\theta^{*})^{2}\right)\cdot
T_{\mathcal{A},x_{i}}$
$\displaystyle-2\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)\cdot\sum_{t=1}^{T_{\mathcal{A},x_{i}}}Z_{i,t}\Bigg{)}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\Bigg{(}-\frac{1}{2}\sum_{i\in[n]}\Bigg{(}\left((\phi(x_{i})^{\top}\theta/\kappa)^{2}-(\phi(x_{i})^{\top}\theta^{*})^{2}\right)\cdot
T_{\mathcal{A},x_{i}}$
$\displaystyle-2\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)\cdot\left(T_{\mathcal{A},x_{i}}\cdot\phi(x_{i})^{\top}\theta/\kappa+\frac{z}{\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}}\right)\Bigg{)}\Bigg{)}$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\Bigg{(}-\frac{1}{2}\sum_{i\in[n]}\Bigg{(}\left((\phi(x_{i})^{\top}\theta/\kappa)^{2}-(\phi(x_{i})^{\top}\theta^{*})^{2}\right)\cdot
T_{\mathcal{A},x_{i}}$
$\displaystyle-2\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)\cdot
T_{\mathcal{A},x_{i}}\cdot\phi(x_{i})^{\top}\theta/\kappa-2z\Bigg{)}\Bigg{)}$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\Bigg{(}-\frac{1}{2}\sum_{i\in[n]}\Bigg{(}\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)\Big{(}\phi(x_{i})^{\top}\theta/\kappa\cdot
T_{\mathcal{A},x_{i}}+\phi(x_{i})^{\top}\theta^{*}\cdot T_{\mathcal{A},x_{i}}$
$\displaystyle-2\cdot\phi(x_{i})^{\top}\theta/\kappa\cdot
T_{\mathcal{A},x_{i}}\Big{)}-2z\Bigg{)}\Bigg{)}$ $\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\Bigg{(}-\frac{1}{2}\sum_{i\in[n]}\Bigg{(}-\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)^{2}\cdot
T_{\mathcal{A},x_{i}}-2z\Bigg{)}\Bigg{)}$ $\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(\sum_{i\in[n]}\left(\frac{1}{2}\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)^{2}\cdot
T_{\mathcal{A},x_{i}}+z\right)\right)$ $\displaystyle=$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(\sum_{i\in[n]}\left(\frac{1}{2}(1-\frac{1}{\kappa})^{2}(\phi(x_{i})^{\top}\theta^{*})^{2}\cdot\frac{d(\mathcal{X})}{\Delta^{2}\zeta}\cdot\lambda_{i}+z\right)\right)$
$\displaystyle\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(\frac{(1+c)^{2}}{2}\cdot\frac{d(\mathcal{X})}{\zeta}+nz\right)$

Next, using the Chernoff-Hoeffding inequality, we bound the second term as

$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[\neg
L\right]\leq$
$\displaystyle\sum_{i\in[n]}\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[\neg
L_{i}\right]$ $\displaystyle\leq$
$\displaystyle\sum_{i\in[n]}\exp\left(-2\frac{z^{2}}{(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*})^{2}}\cdot\frac{\zeta}{\lambda_{i}\rho(\mathcal{X},\theta^{*})}\right)$
$\displaystyle=$
$\displaystyle\sum_{i\in[n]}\exp\left(-2\frac{z^{2}}{(1-\frac{1}{\kappa})^{2}(\phi(x_{i})^{\top}\theta^{*})^{2}}\cdot\frac{\Delta^{2}\zeta}{\lambda_{i}d(\mathcal{X})}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[n]}\exp\left(-\frac{2}{(1+c)^{2}}\cdot\frac{z^{2}\zeta}{d(\mathcal{X})}\right)$
$\displaystyle=$ $\displaystyle
n\cdot\exp\left(-\frac{2}{(1+c)^{2}}\cdot\frac{z^{2}\zeta}{d(\mathcal{X})}\right)$

Thus,

$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E\right]\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E,L\right]+\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[\neg
L\right]$ $\displaystyle\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(\frac{(1+c)^{2}}{2}\cdot\frac{d(\mathcal{X})}{\zeta}+nz\right)+n\cdot\exp\left(-\frac{2}{(1+c)^{2}}\cdot\frac{z^{2}\zeta}{d(\mathcal{X})}\right)$

Let $z=\sqrt{\frac{(1+c)^{2}d(\mathcal{X})\log(nQ)}{\zeta}}$. Then, we have

$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)}}\left[E\right]\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E,L\right]\cdot\exp\left(\frac{(1+c)^{2}}{2}\cdot\frac{d(\mathcal{X})}{\zeta}+n\sqrt{\frac{(1+c)^{2}d(\mathcal{X})\log(nQ)}{\zeta}}\right)$
$\displaystyle+n\cdot\exp\left(-2\log(nQ)\right)$ $\displaystyle\leq$
$\displaystyle\Pr_{\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})}}\left[E\right]\cdot\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nQ)}{\zeta}}\right)+\frac{1}{nQ^{2}}$

∎

###### Lemma 0 (Linear Structured Instance Transformation Lemma).

For any integer $\alpha\geq 0$, $q\geq 100$ and $\kappa\geq 1$, we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}+\frac{\rho(\mathcal{X},\theta^{*})}{\beta}\right)\right]\\!\\!\geq$
$\displaystyle\\!\\!\\!\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]-\delta-\sqrt{\frac{(1+c)^{2}}{4}\cdot\frac{d(\mathcal{X})}{q}}$
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$

###### Proof.

Let $\ell=\\{Z_{i,1},\dots,Z_{i,T_{\mathcal{A},x_{i}}}\\}_{i\in[n]}$ denote
the $T_{\mathcal{A}}$ samples of algorithm $\mathcal{A}$ on instance
$\mathcal{I}(\mathcal{X},\theta^{*})$. Let $\mathcal{S}$ denote the set of all
possible $\ell$, conditioned on which
$\mathcal{E}^{+1}(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq})$ holds.
Then, we have

$\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]=\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]$

For any agent $v\in[V]$, let $\mathcal{K}_{v}$ be the event that agent $v$
uses more than $\frac{\rho(\mathcal{X},\theta^{*})}{\beta}$ samples during the
$(\alpha+1)$-st round. Conditioned on $s\in\mathcal{S}$, $\mathcal{K}_{v}$
only depends on the samples of agent $v$ during the $(\alpha+1)$-st round, and
is independent of other agents.

Using the facts that $\mathcal{A}$ is $\delta$-correct and $\beta$-speedup and
all agents have the same performance on fully-collaborative instances, we have

$\displaystyle\delta\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\text{$\mathcal{A}$
uses more than $\frac{\rho(\mathcal{X},\theta^{*})}{\beta}$}\right]$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{1}\vee\dots\vee\mathcal{K}_{V}|\ell=s\right]$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\left(1-\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)\right)$
$\displaystyle=$
$\displaystyle\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)-\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)$

Rearranging the above inequality, we have

(22)
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)\geq$
$\displaystyle\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)-\delta$

Using Lemma 4 with $\zeta=\beta$ and $Q=V$, we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}+\frac{\rho(\mathcal{X},\theta^{*})}{\beta}\right)\right]$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\neg\mathcal{K}_{1}\wedge\dots\wedge\neg\mathcal{K}_{V}|\ell=s\right]$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{K}_{i}|\ell=s\right]\right)$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot$
$\displaystyle\prod_{v\in[V]}\max\left\\{1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\cdot\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-\frac{1}{nV^{2}},0\right\\}$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot$
$\displaystyle\left(\prod_{v\in[V]}\max\left\\{1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\cdot\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right),0\right\\}-\frac{1}{nV}\right)$
$\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot\Bigg{(}\prod_{v\in[V]}\max\Bigg{(}1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]$
$\displaystyle-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\cdot\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right),0\Bigg{)}-\frac{1}{nV}\Bigg{)}$
$\displaystyle\overset{\textup{(e)}}{\geq}$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot$
$\displaystyle\left(\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]\cdot$
$\displaystyle\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)$
$\displaystyle-\sum_{s\in\mathcal{S}}\left|\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\right|-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$

where (e) comes from Lemma 4.

Using the Pinsker’s inequality (Lemma 3), we have

(23)
$\displaystyle\sum_{s\in\mathcal{S}}\left|\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\ell=s\right]-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\right|$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{1}{2}\textup{KL}(\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta/\kappa)},\mathcal{D}_{\mathcal{I}(\mathcal{X},\theta^{*})})}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{1}{4}\sum_{i\in[n]}\left(\phi(x_{i})^{\top}\theta/\kappa-\phi(x_{i})^{\top}\theta^{*}\right)^{2}\cdot\lambda_{i}T_{\mathcal{A}}}$
$\displaystyle=$
$\displaystyle\sqrt{\frac{1}{4}\sum_{i\in[n]}\left((1-\frac{1}{\kappa})^{2}(\phi(x_{i})^{\top}\theta^{*})^{2}\cdot\frac{d(\mathcal{X})}{\Delta^{2}q}\lambda_{i}\right)}$
(24) $\displaystyle\leq$
$\displaystyle\sqrt{\frac{(1+c)^{2}}{4}\cdot\frac{d(\mathcal{X})}{q}}$

Thus, using Eqs. (22),(24), we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}+\frac{\rho(\mathcal{X},\theta^{*})}{\beta}\right)\right]$
$\displaystyle\geq$
$\displaystyle\sum_{s\in\mathcal{S}}\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\ell=s\right]\cdot\prod_{v\in[V]}\left(1-\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{K}_{i}|\ell=s\right]\right)-\sqrt{\frac{(1+c)^{2}}{4}\cdot\frac{d(\mathcal{X})}{q}}$
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$
$\displaystyle\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]-\delta-\sqrt{\frac{(1+c)^{2}}{4}\cdot\frac{d(\mathcal{X})}{q}}$
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$

∎

Now we prove Theorem 4.

###### Proof of Theorem 4.

Combining Lemmas 3,5, we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}+\frac{\rho(\mathcal{X},\theta^{*})}{\beta}\right)\right]$
$\displaystyle\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}^{+1}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]-\delta-\sqrt{\frac{(1+c)^{2}}{4}\cdot\frac{d(\mathcal{X})}{q}}$
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$
$\displaystyle\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]-3\delta-\sqrt{\frac{(1+c)^{2}d(\mathcal{X})}{q}}$
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$

Let $\kappa=\sqrt{1+\frac{Vq}{\beta}}$. Then, we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta/\kappa)}{Vq}\right)\right]$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\kappa^{2}\cdot\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]$
$\displaystyle=$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta/\kappa)}\left[\mathcal{E}\left(\alpha+1,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}+\frac{\rho(\mathcal{X},\theta^{*})}{\beta}\right)\right]$
$\displaystyle\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}\left(\alpha,\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]-3\delta-\sqrt{\frac{(1+c)^{2}d(\mathcal{X})}{q}}$
(25)
$\displaystyle-\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)-\frac{1}{nV}$

Let $\mathcal{I}(\mathcal{X},\theta_{0})$ be the basic instance of induction,
where the reward gap is
$\Delta_{0}=(\phi(x_{*})-\phi(x_{i}))^{\top}\theta_{0}=1$ for any $i\in[n]$.
Let $t_{0}$ be the largest integer such that

$\Delta\cdot\left(1+\frac{Vq}{\beta}\right)^{\frac{t_{0}}{2}}\leq 1,$

where $q=1000t_{0}^{2}$. Then, we have

$t_{0}=\Omega\left(\frac{\log(\frac{1}{\Delta})}{\log(1+\frac{V}{\beta})+\log\log(\frac{1}{\Delta})}\right)$

Starting from $\mathcal{I}(\mathcal{X},\theta_{0})$, we repeatedly apply Eq.
(25) for $t_{0}$ times to switch to $\mathcal{I}(\mathcal{X},\theta^{*})$
where the reward gap is $\Delta$. Since
$\Pr_{\mathcal{I}(\mathcal{X},\theta_{0})}\left[\mathcal{E}\left(0,\frac{\rho(\mathcal{X},\theta_{0})}{Vq}\right)\right]=1$,
by induction, we have

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}\left(t_{0},\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]$
$\displaystyle\geq$ $\displaystyle
1-\left(3\delta+\sqrt{\frac{(1+c)^{2}d(\mathcal{X})}{q}}+\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)+\frac{1}{nV}\right)\cdot
t_{0}$

When $\delta=O(\frac{1}{nV})$ and $q,V,\beta$ are large enough, we can have

$\displaystyle\left(3\delta+\sqrt{\frac{(1+c)^{2}d(\mathcal{X})}{q}}+\left(\exp\left((1+c)^{2}d(\mathcal{X})n\sqrt{\frac{\log(nV)}{\beta}}\right)-1\right)+\frac{1}{nV}\right)\cdot
t_{0}\leq\frac{1}{2}$

and then

$\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}\left(t_{0},\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]\geq\frac{1}{2}.$

Thus,

$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\text{$\mathcal{A}$
uses
$\Omega\left(\frac{\log(\frac{1}{\Delta})}{\log(1+\frac{V}{\beta})+\log\log(\frac{1}{\Delta})}\right)$
communication rounds}\right]$ $\displaystyle\geq$
$\displaystyle\Pr_{\mathcal{I}(\mathcal{X},\theta^{*})}\left[\mathcal{E}\left(t_{0},\frac{\rho(\mathcal{X},\theta^{*})}{Vq}\right)\right]$
$\displaystyle\geq$ $\displaystyle\frac{1}{2},$

which completes the proof of Theorem 4. ∎

##  Appendix B Proofs for the Fixed-Budget Setting

###  B.1. Proof of Theorem 1

###### Proof of Theorem 1.

Our proof of Theorem 1 adapts the error probability analysis in (Katz-Samuels
et al., 2020) to the multi-agent setting.

Since the number of samples used over all agents in each phase is
$N=\left\lfloor TV/R\right\rfloor$, the total number of samples used by
algorithm CoopKernelFB is at most $TV$ and the total number of samples used
per agent is at most $T$.

Now we prove the error probability upper bound.

Recall that for any $\lambda\in\triangle_{\tilde{\mathcal{X}}}$,
$\Phi_{\lambda}=[\sqrt{\lambda_{1}}\phi(x^{*}_{v})^{\top};\dots;\sqrt{\lambda_{nV}}\phi(\tilde{x}_{nV})^{\top}]$
and
$\Phi^{\top}_{\lambda}\Phi_{\lambda}=\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda_{\tilde{x}}\phi(\tilde{x})\phi(\tilde{x})^{\top}$.
Let $\gamma_{*}=\xi_{*}N$.

For any $\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B}_{v}^{(t)},v\in[V],t\in[R]$,
define

$\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}=\inf_{\Delta>0}\left\\{\frac{\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|^{2}_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\Delta^{2}}\leq
2\rho^{*}\right\\}$

and event

$\mathcal{J}_{t,\tilde{x}_{i},\tilde{x}_{j}}=\left\\{\left|\left(\hat{f}_{t}(\tilde{x}_{i})-\hat{f}_{t}(\tilde{x}_{j})\right)-\left(f(\tilde{x}_{i})-f(\tilde{x}_{j})\right)\right|<\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}\right\\}.$

In the following, we prove
$\Pr\left[\neg\mathcal{J}_{t,\tilde{x}_{i},\tilde{x}_{j}}\right]\leq
2\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$.

Similar to the analysis procedure of Lemma 1, we have

$\displaystyle\left(\hat{f}_{t}(\tilde{x}_{i})-\hat{f}_{t}(\tilde{x}_{j})\right)-\left(f(\tilde{x}_{i})-f(\tilde{x}_{j})\right)$
$\displaystyle=$
$\displaystyle\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\Phi_{t}^{\top}\bar{\eta}^{(t)}-\gamma_{*}\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\theta^{*},$

where the mean of the first term is zero and its variance is bounded by

$\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|^{2}_{\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}}\leq\frac{(1+\varepsilon)\cdot\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{N}.$

Using the Hoeffding inequality, we have

$\displaystyle\Pr\left[\left|\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\Phi_{t}^{\top}\eta_{v}^{(t)}\right|\geq\frac{1}{2}\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}\right]$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-2\frac{\frac{1}{4}\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}^{2}}{\frac{(1+\varepsilon)\cdot\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{N}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{1}{2}\frac{N}{\frac{(1+\varepsilon)\cdot\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}^{2}}}\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$

Thus, with probability at least
$1-2\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$, we have

$\left|\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\Phi_{t}^{\top}\eta_{v}^{(t)}\right|<\frac{1}{2}\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}.$

Recall that $\xi_{*}$ satisfies
$(1+\varepsilon)\sqrt{\xi_{*}}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\tilde{\mathcal{X}}_{v},v\in[V]}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\xi_{*}I+\Phi_{\lambda_{u}}^{\top}\Phi_{\lambda_{u}}\right)^{-1}}B\leq\frac{1}{2}\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}$.
Then, we bound the regularization (bias) term.

$\displaystyle\left|\gamma_{*}\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\theta^{*}\right|$
$\displaystyle\leq$
$\displaystyle\gamma_{*}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}}\|\theta^{*}\|_{\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\gamma_{*}}\cdot\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}}\|\theta^{*}\|_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{\xi_{*}N}\cdot\frac{(1+\varepsilon)\cdot\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\sqrt{N}}\cdot\|\theta^{*}\|_{2}$
$\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sqrt{\xi_{*}}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\tilde{\mathcal{B}}^{(t)}_{v},v\in[V]}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\xi_{*}I+\Phi_{\lambda^{*}_{t}}^{\top}\Phi_{\lambda^{*}_{t}}\right)^{-1}}\|\theta^{*}\|_{2}$
$\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sqrt{\xi_{*}}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\tilde{\mathcal{B}}^{(t)}_{v},v\in[V]}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\xi_{*}I+\Phi_{\lambda_{u}}^{\top}\Phi_{\lambda_{u}}\right)^{-1}}\|\theta^{*}\|_{2}$
$\displaystyle\leq$
$\displaystyle(1+\varepsilon)\sqrt{\xi_{*}}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\tilde{\mathcal{X}}_{v},v\in[V]}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\xi_{*}I+\Phi_{\lambda_{u}}^{\top}\Phi_{\lambda_{u}}\right)^{-1}}\cdot
B$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}}$

Thus, with probability at least
$1-2\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$, we have

$\displaystyle\left|\left(\hat{f}_{t}(\tilde{x}_{i})-\hat{f}_{t}(\tilde{x}_{j})\right)-\left(f(\tilde{x}_{i})-f(\tilde{x}_{j})\right)\right|$
$\displaystyle\leq$
$\displaystyle\left|\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\Phi_{t}^{\top}\eta_{v}^{(t)}\right|+\left|\gamma_{*}\left(\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\right)^{\top}\left(\gamma_{*}I+\Phi_{t}^{\top}\Phi_{t}\right)^{-1}\theta^{*}\right|$
$\displaystyle<$ $\displaystyle\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}},$

which completes the proof of
$\Pr\left[\neg\mathcal{J}_{t,\tilde{x}_{i},\tilde{x}_{j}}\right]\leq
2\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$.

Define event

$\mathcal{J}=\left\\{\left|\left(\hat{f}_{t}(\tilde{x}_{i})-\hat{f}_{t}(\tilde{x}_{j})\right)-\left(f(\tilde{x}_{i})-f(\tilde{x}_{j})\right)\right|<\Delta_{t,\tilde{x}_{i},\tilde{x}_{j}},\
\forall\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B}_{v}^{(t)},\forall
v\in[V],\forall t\in[R]\right\\},$

By a union bound over $\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B}_{v}^{(t)}$,
$v\in[V]$ and $t\in[R]$, we have

$\displaystyle\Pr\left[\neg\mathcal{J}\right]\leq$ $\displaystyle
2n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{N}{2(1+\varepsilon)\rho^{*}}\right)$
$\displaystyle=$ $\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV}{\rho^{*}\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$

In order to prove Theorem 1, it suffices to prove that conditioning on
$\mathcal{J}$, algorithm CoopKernelFB returns the correct answers
$\tilde{x}^{*}_{v}$ for all $v\in[V]$.

Suppose that there exist $v\in[V]$ and $t\in[R]$ such that $\tilde{x}^{*}_{v}$
is eliminated in phase $t$. Define

$\mathcal{B^{\prime}}_{v}^{(t)}=\\{\tilde{x}\in\mathcal{B}_{v}^{(t)}:\hat{f}_{t}(\tilde{x})>\hat{f}_{t}(\tilde{x}^{*}_{v})\\},$

which denotes the subset of arms that are ranked before $\tilde{x}^{*}_{v}$ by
the estimated rewards in $\mathcal{B}_{v}^{(t)}$. According to the elimination
rule, we have

(26)
$\displaystyle\omega(\mathcal{B^{\prime}}_{v}^{(t)}\cup\\{\tilde{x}^{*}_{v}\\})>\frac{1}{2}\omega(\mathcal{B}_{v}^{(t)})=\frac{1}{2}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B}_{v}^{(t)}}\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}$

Define
$\tilde{x}_{0}=\operatornamewithlimits{argmax}_{\tilde{x}\in\mathcal{B^{\prime}}_{v}^{(t)}}\Delta_{\tilde{x}}$.
We have

$\displaystyle\frac{1}{2}\frac{\|\phi(\tilde{x}^{*}_{v})-\phi(\tilde{x}_{0})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\Delta_{\tilde{x}_{0}}^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B}_{v}^{(t)}}\frac{\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\Delta_{\tilde{x}_{0}}^{2}}$
$\displaystyle\overset{\textup{(f)}}{<}$
$\displaystyle\frac{\omega(\mathcal{B^{\prime}}_{v}^{(t)}\cup\\{\tilde{x}^{*}_{v}\\})}{\Delta_{\tilde{x}_{0}}^{2}}$
$\displaystyle\overset{\textup{(g)}}{=}$
$\displaystyle\min_{\lambda\in\triangle\mathcal{X}}\max_{\tilde{x}_{i},\tilde{x}_{j}\in\mathcal{B^{\prime}}_{v}^{(t)}\cup\\{\tilde{x}^{*}_{v}\\}}\frac{\|\phi(\tilde{x}_{i})-\phi(\tilde{x}_{j})\|_{\left(\xi_{*}I+\Phi^{\top}_{\lambda}\Phi_{\lambda}\right)^{-1}}}{\Delta_{\tilde{x}_{0}}^{2}}$
$\displaystyle\overset{\textup{(h)}}{\leq}$
$\displaystyle\min_{\lambda\in\triangle\mathcal{X}}\max_{\tilde{x}\in\mathcal{B^{\prime}}_{v}^{(t)}}\frac{\|\phi(\tilde{x}^{*}_{v})-\phi(\tilde{x})\|_{\left(\xi_{*}I+\Phi^{\top}_{\lambda}\Phi_{\lambda}\right)^{-1}}}{\Delta_{\tilde{x}}^{2}}$
$\displaystyle\leq$
$\displaystyle\min_{\lambda\in\triangle\mathcal{X}}\max_{\tilde{x}\in\mathcal{X}_{v}\setminus\\{\tilde{x}^{*}_{v}\\},v\in[V]}\frac{\|\phi(\tilde{x}^{*}_{v})-\phi(\tilde{x})\|_{\left(\xi_{*}I+\Phi^{\top}_{\lambda}\Phi_{\lambda}\right)^{-1}}}{\Delta_{\tilde{x}}^{2}}$
$\displaystyle=$ $\displaystyle\rho^{*},$

where (f) can be obtained by dividing Eq. (26) by
$\Delta_{\tilde{x}_{0}}^{2}$, (g) comes from the definition of
$\omega(\cdot)$, and (h) is due to the definition of $\tilde{x}_{0}$.

According to the definition

$\Delta_{t,\tilde{x}^{*}_{v},\tilde{x}_{0}}=\inf_{\Delta>0}\left\\{\frac{\|\phi(\tilde{x}^{*}_{v})-\phi(\tilde{x}_{0})\|^{2}_{(\xi_{*}I+\Phi^{\top}_{\lambda^{*}_{t}}\Phi_{\lambda^{*}_{t}})^{-1}}}{\Delta^{2}}\leq
2\rho^{*}\right\\},$

we have
$\Delta_{t,\tilde{x}^{*}_{v},\tilde{x}_{0}}\leq\Delta_{\tilde{x}_{0}}$.

Conditioning on $\mathcal{J}$, we have
$\left|\left(\hat{f}_{t}(\tilde{x}^{*}_{v})-\hat{f}_{t}(\tilde{x}_{0})\right)-\left(f(\tilde{x}^{*}_{v})-f(\tilde{x}_{0})\right)\right|<\Delta_{t,\tilde{x}^{*}_{v},\tilde{x}_{0}}\leq\Delta_{\tilde{x}_{0}}$.
Then, we have

$\displaystyle\hat{f}_{t}(\tilde{x}^{*}_{v})-\hat{f}_{t}(\tilde{x}_{0})>\left(f(\tilde{x}^{*}_{v})-f(\tilde{x}_{0})\right)-\Delta_{\tilde{x}_{0}}=0,$

which contradicts the definition of $\tilde{x}_{0}$ that satisfies
$\hat{f}_{t}(\tilde{x}_{0})>\hat{f}_{t}(\tilde{x}^{*}_{v})$. Thus, for any
$v\in[V]$, $\tilde{x}^{*}_{v}$ will never be eliminated.

Since $\omega(\\{\tilde{x}^{*}_{v},\tilde{x}\\})\geq 1$ for any
$\tilde{x}\in\mathcal{X}_{v}\setminus\\{\tilde{x}^{*}_{v}\\},v\in[V]$ and
$R=\left\lceil\log_{2}(\omega(\tilde{\mathcal{X}}))\right\rceil\geq\left\lceil\log_{2}(\omega(\mathcal{X}_{v}))\right\rceil$
for any $v\in[V]$, we have that conditioning on $\mathcal{J}$, algorithm
CoopKernelFB returns the correct answers $\tilde{x}^{*}_{v}$ for all
$v\in[V]$.

For communication rounds, since algorithm CoopKernelFB has at most
$R=\left\lceil\log_{2}(\omega(\tilde{\mathcal{X}}))\right\rceil$ phases, the
number of communication rounds is bounded by
$O(\log(\omega(\tilde{\mathcal{X}})))$. ∎

###  B.2. Proof of Corollary 2

###### Proof of Corollary 2.

Following the analysis procedure of Corollary 2, we have

$\displaystyle\rho^{*}=$
$\displaystyle\min_{\lambda\in\triangle_{\mathcal{X}}}\max_{\tilde{x}\in\tilde{\mathcal{X}}_{v},v\in[V]}\frac{\|\phi(\tilde{x}^{*}_{v})-\phi(\tilde{x})\|^{2}_{\left(\xi_{*}I+\Phi^{\top}_{\lambda}\Phi_{\lambda}\right)^{-1}}}{\left(f(\tilde{x}^{*}_{v})-f(\tilde{x})\right)^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{8}{\Delta^{2}_{\min}}\cdot\log\det\left(I+\xi_{*}^{-1}K_{\lambda^{*}}\right)$

Maximum Information Gain. Recall that the maximum information gain over all
sample allocation $\lambda\in\triangle_{\tilde{\mathcal{X}}}$ is defined as

$\Upsilon=\max_{\lambda\in\triangle_{\tilde{\mathcal{X}}}}\log\det\left(I+{\xi_{*}}^{-1}K_{\lambda}\right).$

Then, the error probability is bounded by

$\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV}{\rho^{*}\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$
$\displaystyle=$ $\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV\Delta^{2}_{\min}}{\Upsilon\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$

Effective Dimension. Recall that $\alpha_{1}\geq\dots\geq\alpha_{nV}$ denote
the eigenvalues of $K_{\lambda^{*}}$ in decreasing order. The effective
dimension of $K_{\lambda^{*}}$ is defined as

$d_{\textup{eff}}=\min\bigg{\\{}j:j\xi_{*}\log(nV)\geq\sum_{i=j+1}^{nV}\alpha_{i}\bigg{\\}},$

and we have

$\displaystyle\log\det\left(I+\xi_{*}^{-1}K_{\lambda^{*}}\right)\leq{d_{\textup{eff}}}\log\left(2nV\cdot\left(1+\frac{\textup{Trace}(K_{\lambda^{*}})}{\xi_{*}d_{\textup{eff}}}\right)\right).$

Then, the error probability is bounded by

$\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV}{\rho^{*}\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$
$\displaystyle=$ $\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV\Delta^{2}_{\min}}{d_{\textup{eff}}\log\left(nV\cdot\left(1+\frac{\textup{Trace}(K_{\lambda^{*}})}{\xi_{*}d_{\textup{eff}}}\right)\right)\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$

Decomposition. Recall that $K=[K(\tilde{x}_{i},\tilde{x}_{j})]_{i,j\in[nV]}$,
$K_{z}=[K_{z}(z_{v},z_{v^{\prime}})]_{v,v^{\prime}\in[V]}$,
$K_{x}=[K_{x}(x_{i},x_{j})]_{i,j\in[nV]}$, and
$\textup{rank}(K_{\lambda^{*}})=\textup{rank}(K)\leq\textup{rank}(K_{z})\cdot\textup{rank}(K_{x})$.
We have

$\displaystyle\log\det\left(I+\xi_{*}^{-1}K_{\lambda^{*}}\right)\leq\textup{rank}(K_{z})\cdot\textup{rank}(K_{x})\log\left(\frac{\textup{Trace}\left(I+\xi_{*}^{-1}K_{\lambda^{*}}\right)}{\textup{rank}(K_{\lambda^{*}})}\right)$

Then, the error probability is bounded by

$\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV}{\rho^{*}\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$
$\displaystyle=$ $\displaystyle
O\left(n^{2}V\log(\omega(\tilde{\mathcal{X}}))\cdot\exp\left(-\frac{TV\Delta^{2}_{\min}}{\textup{rank}(K_{z})\cdot\textup{rank}(K_{x})\log\left(\frac{\textup{Trace}\left(I+\xi_{*}^{-1}K_{\lambda^{*}}\right)}{\textup{rank}(K_{\lambda^{*}})}\right)\log(\omega(\tilde{\mathcal{X}}))}\right)\right)$

Therefore, we complete the proof of Corollary 2. ∎

###  B.3. Proof of Theorem 3

Our proof of Theorem 3 follows the analysis procedure in (Agarwal et al.,
2017).

We first introduce some definitions in information theory. For any random
variable $A$, let $H(A)$ denote the Shannon entropy of $A$. If $A$ is
uniformly distributed on its support, $H(A)=\log|A|$. For any $p\in(0,1)$, let
$H_{2}(p)=-p\log_{2}p-(1-p)\log_{2}(1-p)$ denote the binary entropy, and
$H_{2}(p)=H(A)$ for $A\sim\textup{Bernoulli}(p)$. For any random variables
$A,B$, let $H(A;B)=H(A)-H(A|B)=H(B)-H(B|A)$ denote the mutual information of
$A$ and $B$.

Consider the following fully-collaborative instance
$\mathcal{D}_{d}^{\Delta,p}$: for a uniformly drawn index $i^{*}\in[d]$,
$\theta^{*}_{i^{*}}=p+\Delta$ and $\theta^{*}_{j}=p$ for all $j\neq i^{*}$.
The arm set $\mathcal{X}=\\{x\in\\{0,1\\}^{d}:\sum_{i=1}^{d}x(i)=1\\}$, and
the feature mapping $\phi(x)=Ix$ for all $x\in\mathcal{X}$. Under instance
$\mathcal{D}_{d}^{\Delta,p}$, we have
$\omega(\tilde{\mathcal{X}})=\omega(\mathcal{X})=d$.

Let $\delta_{*}>0$ be a small constant that we specify later. There exists a
single-agent algorithm $\mathcal{A}_{S}$ (e.g., (Katz-Samuels et al., 2020))
that uses at most $T$ samples and guarantees $O(\log
d\cdot\exp(-\frac{\Delta^{2}T}{d\log d}))$ error probability on instance
$\mathcal{D}_{d}^{\Delta,p}$ for any $d>1$. Restricting the error probability
to the constant $\delta_{*}$, we have that for any $d>1$, $\mathcal{A}_{S}$
uses at most $T={O}(\frac{d}{\Delta^{2}}\log d\cdot\log\log d)$ samples to
guarantee $\delta_{*}$ error probability on instance
$\mathcal{D}_{d}^{\Delta,p}$.

Let $\alpha=\frac{V}{\beta}$ and $1\leq\alpha\leq\log d$. According to the
definition of speedup, a $\frac{V}{\alpha}$-speedup distributed algorithm
$\mathcal{A}$ must satisfy that for any $d>1$, $\mathcal{A}$ uses at most
$T=O(\frac{\frac{n}{\Delta^{2}}}{\frac{V}{\alpha}}\cdot V\log d\cdot\log\log
d)=O(\frac{\alpha d}{\Delta^{2}}\log d\cdot\log\log d)$ samples over all
agents and guarantees $\delta_{*}$ error probability on instance
$\mathcal{D}_{d}^{\Delta,p}$.

Main Proof. Now, in order to prove Theorem 3, we first prove the following
Lemma 1, which relaxes the sample budget within logarithmic factors.

###### Lemma 0.

For any $d>1$, any distributed algorithm $\mathcal{A}$ that can use at most
$O(\frac{\alpha d(\log\alpha+\log\log d)^{2}}{\Delta^{2}(\log d)^{2}})$
samples over all agents and guarantee $\delta_{*}$ error probability on
instance $\mathcal{D}_{d}^{\Delta,p}$ needs $\Omega(\frac{\log
d}{\log\alpha+\log\log d})$ communication rounds.

Below we prove Lemma 1 by induction (Lemmas 2,3).

###### Lemma 0 (Basic Step).

For any $d>1$ and $1\leq\alpha\leq\log d$, there is no $1$-round algorithm
$\mathcal{A}_{1}$ that can use $O(\frac{\alpha d}{\Delta^{2}})$ samples and
guarantee $\delta_{1}$ error probability for some constant
$\delta_{1}\in(0,1)$ on instance $\mathcal{D}_{d}^{\Delta,p}$.

###### Proof of Lemma 2.

Let $I$ denote the random variable of index $i^{*}$. Since $I$ is uniformly
distributed on $[d]$, $H(I)=\log d$. Let $S$ denote the sample profile of
$\mathcal{A}_{1}$ on instance $\mathcal{D}_{d}^{\Delta,p}$. According to the
definitions of $\mathcal{X}$ and $\theta^{*}$, for instance
$\mathcal{D}_{d}^{\Delta,p}$, identifying the best arm is equivalent to
identifying $I$. Suppose that $\mathcal{A}_{1}$ returns the best arm with
error probability $\delta_{1}$. Using the Fano’s inequality (Lemma 5), we have

(27) $\displaystyle H(I|S)\leq H_{2}(\delta_{1})+\delta_{1}\log d$

Using Lemma 6, we have

$\displaystyle H(I|S)=$ $\displaystyle H(I)-H(I;S)$ $\displaystyle=$
$\displaystyle\log d-O(\frac{\alpha d}{\Delta^{2}}\cdot\frac{\Delta^{2}}{d})$
$\displaystyle=$ $\displaystyle\log d-O(\alpha)$

Then, for some small enough constant $\delta_{1}\in(0,1)$, Eq. (27) cannot
hold. Thus, for any $d>1$ and $1\leq\alpha\leq\log d$, there is no $1$-round
algorithm $\mathcal{A}_{1}$ that can use $O(\frac{\alpha d}{\Delta^{2}})$
samples and guarantee $\delta_{1}$ error probability on instance
$\mathcal{D}_{d}^{\Delta,p}$. ∎

###### Lemma 0 (Induction Step).

Suppose that $1\leq\alpha\leq\log d$ and $\delta\in(0,1)$. If for any $d>1$,
there is no $(r-1)$-round algorithm $\mathcal{A}_{r-1}$ that can use
$O(\frac{\alpha d}{\Delta^{2}(r-1)^{2}})$ samples and guarantee $\delta$ error
probability on instance $\mathcal{D}_{d}^{\Delta,p}$, then for any $d>1$,
there is no $r$-round algorithm $\mathcal{A}_{r}$ that can use $O(\frac{\alpha
d}{\Delta^{2}r^{2}})$ samples and guarantee $\delta-O(\frac{1}{r^{2}})$ error
probability on instance $\mathcal{D}_{d}^{\Delta,p}$.

###### Proof of Lemma 3.

We prove this lemma by contradiction. Suppose that for some $d>1$, there
exists an $r$-round algorithm $\mathcal{A}_{r}$ that can use $O(\frac{\alpha
d}{\Delta^{2}r^{2}})$ samples and guarantee $\delta$ error probability on
instance $\mathcal{D}_{d}^{\Delta,p}$. In the following, we show how to
construct an $(r-1)$-round algorithm $\mathcal{A}_{r-1}$ that can use
$O(\frac{\alpha d}{\Delta^{2}(r-1)^{2}})$ samples and guarantee at most
$\delta+O(\frac{1}{r^{2}})$ error probability on instance
$\mathcal{D}_{\tilde{d}}^{\Delta,p}$ for some $\tilde{d}$.

Let $S_{1}$ denote the sample profile of $\mathcal{A}_{r}$ in the first round
on instance $\mathcal{D}_{d}^{\Delta,p}$. Since the number of samples of
$\mathcal{A}_{r}$ is bounded by $O(\frac{\alpha d}{\Delta^{2}r^{2}})$, using
Lemma 6, we have

$\displaystyle H(I|S_{1})=$ $\displaystyle H(I)-H(I;S_{1})$ $\displaystyle=$
$\displaystyle\log d-O(\frac{\alpha
d}{\Delta^{2}r^{2}}\cdot\frac{\Delta^{2}}{d})$ $\displaystyle=$
$\displaystyle\log d-O(\frac{\alpha}{r^{2}})$

Let $\mathcal{D}_{d|S_{1}}^{\Delta,p}$ denote the posterior of
$\mathcal{D}_{d}^{\Delta,p}$ after observing the sample profile $S_{1}$.

Using Lemma 7 on random variable $I|S_{1}$ with parameters
$\gamma=O(\frac{\alpha}{r^{2}})$ and $\epsilon=o(\frac{1}{r^{2}})$, we can
write $\mathcal{D}_{d|S_{1}}^{\Delta,p}$ as a convex combination of
distributions $\mathcal{Q}_{0},\mathcal{Q}_{1},\dots,\mathcal{Q}_{\ell}$,
i.e., $\mathcal{D}_{d|S_{1}}^{\Delta,p}=\sum_{j=0}^{\ell}q_{j}\mathcal{Q}_{j}$
such that $q_{0}=o(\frac{1}{r^{2}})$, and for any $j\geq 1$,

$\displaystyle|\textup{supp}(\mathcal{Q}_{j})|\geq$
$\displaystyle\exp\left(\log d-\frac{\gamma}{\epsilon}\right)$
$\displaystyle=$ $\displaystyle\exp\left(\log d-o(\alpha)\right)$
$\displaystyle=$ $\displaystyle\frac{d}{e^{o(\alpha)}},$

and

$\displaystyle\|\mathcal{Q}_{j}-\mathcal{U}_{j}\|_{\textup{TV}}=o(\frac{1}{r^{2}}),$

where $\mathcal{U}_{j}$ is the uniform distribution on
$\textup{supp}(\mathcal{Q}_{j})$.

Since

$\displaystyle\Pr[\mathcal{A}_{r}\textup{ has an
error}|\mathcal{D}_{d|S_{1}}^{\Delta,p}]=\sum_{j=0}^{\ell}q_{j}\Pr[\mathcal{A}_{r}\textup{
has an error}|\mathcal{Q}_{j}]\leq\delta,$

using an average argument, there exists a distribution $\mathcal{Q}_{j}$ for
some $j\geq 1$ such that

$\displaystyle\Pr[\mathcal{A}_{r}\textup{ has an
error}|\mathcal{Q}_{j}]\leq\delta.$

Let $\tilde{d}=|\textup{supp}(\mathcal{Q}_{j})|\geq\frac{d}{e^{o(\alpha)}}$.
Since $\|\mathcal{Q}_{j}-\mathcal{U}_{j}\|_{\textup{TV}}=o(\frac{1}{r^{2}})$
and $\mathcal{U}_{j}$ is equivalent to $\mathcal{D}_{\tilde{d}}^{\Delta,p}$,
we have

$\displaystyle\Pr[\mathcal{A}_{r}\textup{ has an
error}|\mathcal{D}_{\tilde{d}}^{\Delta,p}]\leq\delta+o(\frac{1}{r^{2}}).$

Under instance $\mathcal{D}_{\tilde{d}}^{\Delta,p}$, the sample budget for
$(r-1)$-round algorithms is $O(\frac{\alpha\tilde{d}}{\Delta^{2}(r-1)^{2}})$,
and it holds that

$\displaystyle O(\frac{\alpha\tilde{d}}{\Delta^{2}(r-1)^{2}})\geq
O(\frac{\alpha\frac{d}{e^{o(\alpha)}}}{\Delta^{2}(r-1)^{2}})\geq
O(\frac{\alpha d^{1-o(1)}}{\Delta^{2}(r-1)^{2}})\geq O(\frac{\alpha
d}{\Delta^{2}r^{2}})$

Then, we can construct an $(r-1)$-round algorithm $\mathcal{A}_{r-1}$ using
algorithm $\mathcal{A}_{r}$ from the second round. The constructed
$\mathcal{A}_{r-1}$ uses at most $O(\frac{\alpha d}{\Delta^{2}r^{2}})\leq
O(\frac{\alpha\tilde{d}}{\Delta^{2}(r-1)^{2}})$ samples and guarantees
$\delta+o(\frac{1}{r^{2}})$ error probability.

The specific procedure of $\mathcal{A}_{r-1}$ is as follows: if
$\mathcal{A}_{r}$ samples some dimension $i\in\textup{supp}(\mathcal{Q}_{j})$,
then $\mathcal{A}_{r-1}$ also samples $i$; otherwise, if $\mathcal{A}_{r}$
samples some dimension $i\in[d]\setminus\textup{supp}(\mathcal{Q}_{j})$, then
$\mathcal{A}_{r-1}$ samples $\textup{Bernoulli}(p)$ and feeds the outcome to
$\mathcal{A}_{r}$. Finally, if $\mathcal{A}_{r}$ returns some dimension
$i\in\textup{supp}(\mathcal{Q}_{j})$, then $\mathcal{A}_{r-1}$ also returns
$i$; otherwise, if $\mathcal{A}_{r}$ returns some dimension
$i\in[d]\setminus\textup{supp}(\mathcal{Q}_{j})$, then $\mathcal{A}_{r-1}$
returns an arbitrary dimension in $[d]\setminus\textup{supp}(\mathcal{Q}_{j})$
(the error case). ∎

###### Proof of Lemma 1.

Let $r_{*}=\frac{\log d}{\log\alpha+\log\log d}$. Combining Lemmas 2,3, we
obtain that there is no $r_{*}$-round algorithm $\mathcal{A}$ that can use
$O(\frac{\alpha d}{\Delta^{2}r_{*}^{2}})$ samples and guarantee
$\delta_{1}-\sum_{r=2}^{r_{*}}o(\frac{1}{r^{2}})$ error probability on
instance $\mathcal{D}_{d}^{\Delta,p}$ for any $d>1$.

Let $\delta_{*}<\delta_{1}-\sum_{r=2}^{r_{*}}o(\frac{1}{r^{2}})$. Thus, for
any $d>1$ and $1\leq\alpha\leq\log d$, any distributed algorithm $\mathcal{A}$
that can use $O(\frac{\alpha d}{\Delta^{2}r_{*}^{2}})$ samples and guarantee
$\delta_{*}$ error probability on instance $\mathcal{D}_{d}^{\Delta,p}$ must
cost $r_{*}=\Omega\left(\frac{\log d}{\log(\frac{V}{\beta})+\log\log
d}\right)$ communication rounds. ∎

Therefore, for any $d>1$ and $\frac{V}{\log d}\leq\beta\leq V$, a
$\beta$-speedup distributed algorithm $\mathcal{A}$ needs at least
$\Omega\left(\frac{\log\omega(\tilde{\mathcal{X}})}{\log(\frac{V}{\beta})+\log\log\omega(\tilde{\mathcal{X}})}\right)$
communication rounds under instance $\mathcal{D}_{d}^{\Delta,p}$, which
completes the proof of Theorem 3.

##  Appendix C Technical Tools

###### Lemma 0 (Lemma 15 in (Camilleri et al., 2021)).

For
$\lambda^{*}=\operatornamewithlimits{argmax}_{\lambda\in\triangle_{\tilde{\mathcal{X}}}}\log\det\left(I+{\xi_{*}}^{-1}\sum_{\tilde{x}^{\prime}\in\tilde{\mathcal{X}}}\lambda_{\tilde{x}^{\prime}}\phi(\tilde{x}^{\prime})\phi(\tilde{x}^{\prime})^{\top}\right)$,
we have

$\displaystyle\max_{\tilde{x}\in\tilde{\mathcal{X}}}\|\phi(\tilde{x})\|^{2}_{\left(\xi_{*}I+\sum_{\tilde{x}^{\prime}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}^{\prime}}\phi(\tilde{x}^{\prime})\phi(\tilde{x}^{\prime})^{\top}\right)^{-1}}=\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}}\|\phi(\tilde{x})\|^{2}_{\left(\xi_{*}I+\sum_{\tilde{x}^{\prime}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}^{\prime}}\phi(\tilde{x}^{\prime})\phi(\tilde{x}^{\prime})^{\top}\right)^{-1}}$

###### Lemma 0.

For
$\lambda^{*}=\operatornamewithlimits{argmax}_{\lambda\in\triangle_{\tilde{\mathcal{X}}}}\log\det\left(I+{\xi_{*}}^{-1}\sum_{\tilde{x}^{\prime}\in\tilde{\mathcal{X}}}\lambda_{\tilde{x}^{\prime}}\phi(\tilde{x}^{\prime})\phi(\tilde{x}^{\prime})^{\top}\right)$,
we have

$\displaystyle\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\log\left(1+\lambda^{*}_{\tilde{x}}\|\phi(\tilde{x})\|^{2}_{\left(\xi_{*}I+\sum_{\tilde{x}^{\prime}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}^{\prime}}\phi(\tilde{x}^{\prime})\phi(\tilde{x}^{\prime})^{\top}\right)^{-1}}\right)\leq\log\frac{\det\left(\xi_{*}I+\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}}\phi(\tilde{x})\phi(\tilde{x})^{\top}\right)}{\det\left(\xi_{*}I\right)}$

###### Proof of Lemma 2.

For any $j\in[nV]$, let
$M_{j}=\det\left(\xi_{*}I+\sum_{i\in[j]}\lambda^{*}_{i}\phi(\tilde{x}_{i})\phi(\tilde{x}_{i})^{\top}\right)$.

$\displaystyle\det\left(\xi_{*}I+\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}}\phi(\tilde{x})\phi(\tilde{x})^{\top}\right)$
$\displaystyle=$
$\displaystyle\det\left(\xi_{*}I+\sum_{i\in[nV-1]}\lambda^{*}_{i}\phi(\tilde{x}_{i})\phi(\tilde{x}_{i})^{\top}+\lambda^{*}_{nV}\phi(\tilde{x}_{nV})\phi(\tilde{x}_{nV})^{\top}\right)$
$\displaystyle=$
$\displaystyle\det\left(M_{nV-1}\right)\det\left(I+\lambda^{*}_{nV}\cdot
M^{-\frac{1}{2}}_{nV-1}\phi(\tilde{x}_{nV})\left(M^{-\frac{1}{2}}_{nV-1}\phi(\tilde{x}_{nV})\right)^{\top}\right)$
$\displaystyle=$
$\displaystyle\det\left(M_{nV-1}\right)\det\left(I+\lambda^{*}_{nV}\cdot\phi(\tilde{x}_{nV})^{\top}M^{-1}_{nV-1}\phi(\tilde{x}_{nV})\right)$
$\displaystyle=$
$\displaystyle\det\left(M_{nV-1}\right)\left(1+\lambda^{*}_{nV}\|\phi(\tilde{x}_{nV})\|^{2}_{M^{-1}_{nV-1}}\right)$
$\displaystyle=$
$\displaystyle\det\left(\xi_{*}I\right)\prod_{i=1}^{nV}\left(1+\lambda^{*}_{i}\|\phi(\tilde{x}_{i})\|^{2}_{M^{-1}_{i-1}}\right)$

Thus,

$\displaystyle\frac{\det\left(\xi_{*}I+\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}}\phi(\tilde{x})\phi(\tilde{x})^{\top}\right)}{\det\left(\xi_{*}I\right)}=\prod_{i=1}^{nV}\left(1+\lambda^{*}_{i}\|\phi(\tilde{x}_{i})\|^{2}_{M^{-1}_{i-1}}\right)$

Taking logarithm on both sides, we have

$\displaystyle\log\frac{\det\left(\xi_{*}I+\sum_{\tilde{x}\in\tilde{\mathcal{X}}}\lambda^{*}_{\tilde{x}}\phi(\tilde{x})\phi(\tilde{x})^{\top}\right)}{\det\left(\xi_{*}I\right)}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{nV}\log\left(1+\lambda^{*}_{i}\|\phi(\tilde{x}_{i})\|^{2}_{M^{-1}_{i-1}}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{nV}\log\left(1+\lambda^{*}_{i}\|\phi(\tilde{x}_{i})\|^{2}_{M^{-1}_{nV}}\right),$

which completes the proof of Lemma 2. ∎

###### Lemma 0 (Pinsker’s inequality).

If $P$ and $Q$ are two probability distributions on a measurable space
$(X,\Sigma)$, then for any measurable event $A\in\Sigma$, it holds that

$\displaystyle\left|P(A)-Q(A)\right|\leq\sqrt{\frac{1}{2}\textup{KL}(P\|Q)}.$

###### Lemma 0 (Lemma 29 in (Tao et al., 2019)).

For any $\gamma_{1},\dots,\gamma_{K}\in[0,1]$ and $x\geq 0$, it holds that

$\displaystyle\prod_{i=1}^{K}\max\\{1-\gamma_{i}-\gamma_{i}x,\
0\\}\geq\prod_{i=1}^{K}(1-\gamma_{i})-x$

###### Lemma 0 (Fano’s Inequality).

Let $A,B$ be random variables and $f$ be a function that given $A$ predicts a
value for $B$. If $\Pr(f(A)\neq B)\leq\delta$, then $H(B|A)\leq
H_{2}(\delta)+\delta\cdot\log|B|$.

###### Lemma 0.

For the instance $\mathcal{D}_{d}^{\Delta,p}$ with sample profile
$\mathcal{S}$, we have $H(I;S)=O(|S|\cdot\frac{\Delta^{2}}{d})$.

The proof of Lemma 6 follows the same analysis procedure of Lemma 7 in
(Agarwal et al., 2017).

###### Lemma 0 (Lemma 8 in (Agarwal et al., 2017)).

Let $A\sim\mathcal{D}$ be a random variable on $[d]$ with $H(A)\geq\log
d-\gamma$ for some $\gamma\geq 1$. For any $\varepsilon>\exp(-\gamma)$, there
exists $\ell+1$ distributions $\psi_{0},\psi_{1},...,\psi_{\ell}$ on $[d]$
along with $\ell+1$ probabilities $p_{0},p_{1},\dots,p_{\ell}$
($\sum_{i=0}^{\ell}p_{i}=1$) for some $\ell=O(\gamma/\varepsilon^{3})$ such
that $\mathcal{D}=\sum_{i=1}^{\ell}p_{i}\psi_{i}$, $p_{0}=O(\varepsilon)$, and
for any $i\geq 1$,

  1. 1.

$\log|\textup{supp}(\psi_{i})|\geq\log d-\gamma/\varepsilon.$

  2. 2.

$\|\psi_{i}-\mathcal{U}_{i}\|_{\textup{TV}}=O(\varepsilon)$ where
$\mathcal{U}_{i}$ denotes the uniform distribution on
$\textup{supp}(\psi_{i})$.


# Laplacian Spectra of Semigraphs

Pralhad M. Shinde 111Department of Mathematics, College of Engineering Pune,
Pune - 411005, India,
Email<EMAIL_ADDRESS>
###### Abstract

Consider a semigraph $G=(V,\,E)$; in this paper, we study the eigenvalues of
the Laplacian matrix of $G$. We show that the Laplacian of $G$ is positive
semi-definite, and $G$ is connected if and only if $\lambda_{2}>0.$ Along the
similar lines of graph theory bounds on the largest eigenvalue, we obtain
upper and lower bounds on the largest Laplacian eigenvalue of G and enumerate
the Laplacian eigenvalues of some special semigraphs such as star semigraph,
rooted 3-uniform semigraph tree.

Keywords: Adjacency matrix of semigraph, Laplacian of semigraph, Eigenvalues

2000 Mathematics Subject Classification: 05C15, 05C99

##  1 Introduction

In [3], Sampathkumar generalized the definition of a graph and defined the
notion of a semigraph. A semigraph structure looks similar to a linear
hypergraph structure but has ordered edges; hence, semigraphs are different
from linear hypergraphs. The adjacency matrix of semigraphs is considered in
[5], [3], but the matrix is not symmetric. In an attempt to refine the
definition and make it symmetric so that one can use linear algebra tools, the
adjacency matrix of semigraphs is introduced and studied in [1]. The adjacency
matrix of a semigraph is symmetric, and when a semigraph is a graph it gives
us the adjacency matrix of a graph. In [1], author showed that the spectral
graph theory could be extended to the spectral semigraph theory. This
motivated us to look at the Laplacian matrix of semigraphs. We introduce the
Laplacian matrix of a semigraph and investigate its spectra along similar
lines to the Laplacian spectra of graphs. The generalization is natural
because when a semigraph is a graph, our Laplacian matrix coincides with the
Laplacian matrix of graphs [2]. This paper focuses on studying the spectral
properties of the semigraph Laplacian. In section 2, we give the definitions
of the Laplacian and signless Laplacian matrices of a semigraph and show that
both are positive semi-definite. Further, we show that semigraph is connected
iff the second Laplacian eigenvalue $\lambda_{2}>0$. In section 3, we obtain
upper and lower bounds on the largest Laplacian eigenvalue $\lambda_{n}$ of a
semigraph. In section 4, we enumerate Laplacian spectra of some special types
of semigraphs: star semigraph, rooted 3-uniform semigraph tree.

## Preliminaries

In this section, we recall some definitions, and for all other standard
notations and definitions, we refer to [1], [3].

######  Definition 1.1.

Consider a non-empty set $V$ with $|V|=n\geq 2$, $P_{o}(V)$ denotes the set of
all ordered $k$-tuples of elements of $V,$ $1\leq k\leq n$. A pair G=$(V,E),$
where $V$ is called vertex set and $E\subseteq P_{o}(V)$ is called edge set,
defines a semigraph if it satisfies the following two conditions:

  1. 1.

For all $e_{1},e_{2}\in E$, $|e_{1}\cap e_{2}|\leq 1$.

  2. 2.

Let $e_{1}=(v_{1},v_{2},\cdots,v_{p})$ and $e_{2}=(u_{1},u_{2},\cdots,u_{q})$
be two edges, $e_{1}=e_{2}$ if

    1. i)

p = q and

    2. ii)

either $v_{k}=u_{k}$ for $1\leq k\leq p,$ or $v_{k}=u_{p-k+1}$, for $1\leq
k\leq p.$

Note that the edges $(u_{1},u_{2},\cdots,u_{r})$ and
$(u_{r},u_{r-1},\cdots,u_{1})$ are equal.

Let $V$ and $E$ be vertex and edge sets of a semigraph $G$, the vertices
$v_{i},\;v_{j}\in V$ are said to be adjacent  if $\\{v_{i},\;v_{j}\\}\subseteq
e$ for some edge $e\in E$. If $v_{i},\;v_{j}$ are two vertices which are
consecutive in order such that $\\{v_{i},\;v_{j}\\}\subseteq e$ for some edge
$e\in E$ then we say that they are consecutively adjacent. Let
$e=(v_{1},v_{2},\cdots,v_{p})$ be an edge, the vertices $v_{1}$, $v_{p}$ of an
edge $e$ are end vertices, and $v_{2},v_{3},\cdots,v_{p-1}$ are middle
vertices. Here, for all $1\leq i,j\leq p$, vertices $v_{i},\;v_{j}$ are
adjacent while $v_{i},v_{i+1}$ are consecutively adjacent $\forall\,1\leq
i\leq p-1$. The ordering in the edges gives rise to different types of
vertices and edges, and we define those as follows: If $v_{i}$ is an end
vertex $\forall\,e$ with $v_{i}\in e$, then $v_{i}$ is called a pure end
vertex, and if $v_{i}$ is middle vertex $\forall\,e$ with $v_{i}\in e$ then
$v_{i}$ is called a pure middle vertex. If for $v_{i}$, there exist
$e_{1},e_{2}\in E$ such that $v_{i}$ is a middle vertex of $e_{1}$ and end
vertex of $e_{2}$ then $v_{i}$ is called a middle end vertex. If both $v_{1}$
and $v_{r}$ of an edge $e=(v_{1},v_{2},\cdots,v_{r}),\;r\geq 2$ are pure end
vertices then $e$ is called full edge. If either $v_{1}$ or $v_{r}$ (or both)
of an edge $e=(v_{1},v_{2},\cdots,v_{r}),\;r>2$ are middle end vertices or if
$e=(v_{1},v_{2})$ and exactly one of $v_{1},v_{2}$ is a pure end vertex and
the other is a middle end vertex then $e$ is called an half edge. If both
$v_{1}$ and $v_{2}$ of an edge $e=(v_{1},v_{2})$ are middle end vertices then
we say that $e$ is a quarter edge. Let $e=(v_{1},v_{2},\cdots,v_{r})$ be a
full edge, then $(v_{j},v_{j+1})\;\forall\;1\leq j\leq r-1$ is said to be a
partial edge of $e$, and if $e=(v_{1},v_{2},\cdots,v_{r-1},v_{r})$ is an half
edge then $(v_{1},v_{2})$ is said to be partial half edge if $v_{1}$ is middle
end vertex, $(v_{r-1},v_{r})$ is a partial half edge if $v_{r}$ is middle end
vertex and $(v_{i},v_{i+1})\;\forall\;2\leq i\leq r-2$ are partial edges.

######  Example 1.2.

Consider the vertex set $V=\\{w_{1},w_{2},w_{3},w_{4},w_{5},w_{6},w_{7}\\}$
and an edge set $E=\\{(w_{1},w_{2},w_{3},w_{4}),$ $(w_{2},w_{5},w_{6}),$
$(w_{3},w_{7},w_{6}),$ $(w_{5},w_{7})\\}$, note that $G=(V,E)$ is a semigraph.

$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{6}$$w_{7}$ Figure 1:

In Fig. 1, vertices $w_{1},w_{4}$, and $w_{6}$ are the pure end vertices;
$w_{3}$ is the pure middle vertex; $w_{2}$,$w_{5}$ and $w_{7}$ are the middle
end vertices. Further, $(w_{1},w_{2},w_{3},w_{4})$ is full edge, whereas
$(w_{2},w_{5},w_{6})$ is an half edge with only $(w_{2},w_{6})$ as a partial
half edge. Note that $(w_{5},w_{7})$ is a quarter edge.

######  Definition 1.3.

Let $G$ be a semigraph with vertex set $V$ and edge set $E$. If
$\forall\,u,\,v\in V$ there exist $e_{i_{1}},\cdots,e_{i_{p}}\in E$ such that
$u\in e_{i_{1}},\;v\in e_{i_{p}}$ and $|e_{i_{j}}\cap
e_{i_{j+1}}|=1,\;\forall\;1\leq j\leq p-1$ then $G$ is called connected
semigraph.

In this paper, our semigraph $G=(V,E)$ is connected. Here, $n$ denotes the
number of vertices, $m$ denotes the number of edges such that
$m=m_{1}+m_{2}+m_{3}+m_{4};$ where $m_{1},\;m_{2},\;m_{3},\;m_{4}$ are number
of full edges, quarter edges, half edges with one partial half edge, and half
edges with two partial half edges respectively. If $G$ is a graph then
$m_{2}=m_{3}=m_{4}=0$ and $m=m_{1}$.

###  1.1 Adjacency matrix

Consider a semigraph $G$=$(V,E),$ with $V=\\{v_{1},v_{2},\cdots,v_{n}\\}$ as a
vertex set and $E=\\{e_{1},e_{2},\cdots,e_{m}\\}$ as an edge set. Recall that
the graph skeleton $G^{S}$ [1, definition 1.5] of $G$ is the graph defined on
$V$ such that two vertices are adjacent in $G^{S}$ if and only if they are
consecutively adjacent in $G.$ For any two vertices $u_{i}$ and $u_{j}$ of an
edge $e$, $d_{e}(u_{i},\,u_{j})$ represent the distance between $u_{i}$ and
$u_{j}$ in the graph skeleton of the edge $e$. As each pair of vertices in
semigraph belongs to at most one edge, the distance $d_{e}(u_{i},u_{j})$ is
well-defined.

######  Definition 1.4.

[1] We index the rows and columns of a matrix $A=(a_{ij})_{n\times n}$ by
vertices $v_{1},v_{2},\cdots,v_{n},$ where $a_{ij}$ is given as follows:

$a_{ij}=\begin{cases}d_{e}(v_{i},v_{j}),&\text{if $v_{i},\;v_{j}$ belong to a
full edge or a half edge such that }\\\ &\text{$(v_{i},v_{j})$ is neither a
partial half edge nor a quarter edge}\\\ \;\;\;\frac{1}{2},&\text{if
$(v_{i},\;v_{j})$ is a partial half edge}\\\ \;\;\;\frac{1}{4},&\text{if
$(v_{i},v_{j})$ is a quarter edge}\\\ \;\;\;0,&\text{otherwise}\end{cases}$

The above matrix $A=(a_{ij})_{n\times n}$ is the adjacency matrix of semigraph
$G.$ Let $A_{i}$ be the $i^{th}$ row of the adjacency matrix $A$ associated
with the vertex, say $v_{i}$; the number $d_{i}=A_{i}\mathbf{1}$ is the degree
of $v_{i}$, where $\mathbf{1}$ is the column vector of all entries 1.

##  2 Laplacian of Semigraph

Let $G=(V,E)$ be a semigraph with $|V|=n,\;|E|=m$. The Laplacian of graph is
extensively studied matrix [4]; along similar lines, we define the Laplacian
of semigraph. If $G$ is a graph, then semigraph Laplacian is the same as the
graph Laplacian. This motivated us to study the spectral properties of
Laplacian of semigraphs. Let $D$ is a diagonal degree matrix and $A$ is the
adjacency matrix of semigraph $G$, then we define the Laplacian as

$L=D-A$

######  Example 2.1.

The Laplacian matrix of the semigraph in Fig.1 is

$\begin{pmatrix}6&-1&-2&-3&0&0&0\\\ -1&6.5&-1&-2&-\frac{1}{2}&2&0\\\
-2&-1&7&-1&0&-2&-1\\\ -3&-2&-1&6&0&0&0\\\
0&-\frac{1}{2}&0&0&1.75&-1&-\frac{1}{4}\\\ 0&-2&-2&0&-1&6&-1\\\
0&0&-1&0&-\frac{1}{4}&-1&2.25\end{pmatrix}$

Our goal is to study the eigenvalues of Laplacian matrix. The following result
helps us to deduce that eigenvalues are non-negative.

###  2.1 Positive semi-definite

Here, we show that the Laplacian of semigraph is positive semi-definite. This
makes the study of spectra of semigraphs interesting.
Let $G$ be a semigraph, and let $e=(u,v)$ be an edge having two vertices, then
we have three types of edges based on whether $u,\;v$ are pure end vertices or
middle end vertices. Let $L_{e}$ denote the Laplacian matrix of the semigraph
edge $e$. Our aim is to find a quadratic expression $x^{t}L_{e}x$ for the edge
$e$ of size, say $r$, where $x\in\mathbb{R}^{r}$.

######  Observation 2.2.

Let $e=(u,v)$ be an edge in $G$. For $x=(x_{1},x_{2})^{t}\in\mathbb{R}^{2}$,

$x^{t}L_{e}x=\mu(x_{1}-x_{2})^{2}$

where $\mu=\begin{cases}1,&\text{if both u and v are pure end vertices}\\\
\frac{1}{2},&\text{if one of u and v is a middle end vertex}\\\
\frac{1}{4},&\text{if both u and v are middle end vertices}\end{cases}$

  * Case 1

: Both $u$ and $v$ are pure end vertices. Then $L_{e}=\begin{pmatrix}1&-1\\\
-1&1\end{pmatrix}.$
Thus, for $x=\begin{pmatrix}x_{1}\\\ x_{2}\end{pmatrix}\in\mathbb{R}^{2}$, we
get $x^{t}L_{e}x=(x_{1}-x_{2})^{2}$.

  * Case 2

: Both $u$ and $v$ are middle end vertices. Then
$L_{e}=\begin{pmatrix}\frac{1}{4}&-\frac{1}{4}\\\
-\frac{1}{4}&\frac{1}{4}\end{pmatrix}.$
Thus, for $x=\begin{pmatrix}x_{1}\\\ x_{2}\end{pmatrix}\in\mathbb{R}^{2}$, we
get $x^{t}L_{e}x=\frac{1}{4}(x_{1}-x_{2})^{2}$.

  * Case 3

: One of $u$ and $v$ is middle end vertex. Then
$L_{e}=\begin{pmatrix}\frac{1}{2}&-\frac{1}{2}\\\
-\frac{1}{2}&\frac{1}{2}\end{pmatrix}.$
Thus, for $x=\begin{pmatrix}x_{1}\\\ x_{2}\end{pmatrix}\in\mathbb{R}^{2}$, we
get $x^{t}L_{e}x=\frac{1}{2}(x_{1}-x_{2})^{2}$.

We need the following lemma to get a quadratic expression for laplacian of an
edge $|e|\geq 3$

######  Lemma 2.3.

Let $x\in\mathbb{R}^{l}$, where $x=\begin{pmatrix}x_{1}\\\ \vdots\\\
x_{l}\end{pmatrix}.$ Let $L_{e}$ denote the Laplacian of semigraph edge
$e=(v_{i_{1}},v_{i_{2}},\cdots,v_{i_{l}}),\;l\geq 3$. Then

$\displaystyle
x^{t}L_{e}x=\sum_{j=1}^{l-1}\sum_{i=1}^{l-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

where $\mu_{ji}=i,$ except when $v_{i_{1}}$ is middle end vertex then
$\mu_{11}=\frac{1}{2}$, if $v_{i_{l}}$ is middle end vertex then
$\mu_{(l-1)1}=\frac{1}{2}$.

###### Proof.

For an edge $e$, $L_{e}$ denote the Laplacian of semigraph edge. We prove this
result by induction on $l$.

  * •

Step 1: Let $l=3$, $e=(v_{i_{1}},v_{i_{2}},v_{i_{3}})$. Then

$L_{e}=\begin{pmatrix}\mu_{11}+2&-\mu_{11}&-2\\\
-\mu_{11}&\mu_{11}+\mu_{21}&-\mu_{21}\\\ -2&-\mu_{21}&\mu_{21}+2\end{pmatrix}$

where $\mu_{11}=1$ if $v_{i_{1}}$ is pure end vertex and it is $\frac{1}{2}$
when $v_{i_{1}}$ is middle end vertex and $\mu_{21}=1$ if $v_{i_{3}}$ is pure
end vertex and it is $\frac{1}{2}$ when $v_{i_{3}}$ is middle end vertex.
Thus, for
$x=\begin{pmatrix}x_{1},x_{2},x_{3}\end{pmatrix}^{t}\in\mathbb{R}^{3}$, we
have

$\displaystyle x^{t}L_{e}x=$
$\displaystyle\;(\mu_{11}+2)x^{2}_{1}-\mu_{11}x_{1}x_{2}-2x_{1}x_{3}-\mu_{11}x_{1}x_{2}+(\mu_{11}+\mu_{21})x^{2}_{2}-\mu_{21}x_{2}x_{3}$
$\displaystyle-2x_{1}x_{3}-\mu_{21}x_{2}x_{3}+(\mu_{21}+2)x^{2}_{3}$
$\displaystyle=$
$\displaystyle\;\mu_{11}(x^{2}_{1}-2x_{1}x_{2}+x^{2}_{2})+2(x^{2}_{1}-2x_{1}x_{3}+x^{2}_{3})+\mu_{21}(x^{2}_{2}-2x_{2}x_{3}+x^{2}_{3})$
$\displaystyle=$
$\displaystyle\;\mu_{11}(x_{1}-x_{2})^{2}+2(x_{1}-x_{3})^{2}+\mu_{21}(x_{2}-x_{3})^{2}$
$\displaystyle x^{t}L_{e}x=$
$\displaystyle\;\sum_{j=1}^{3-1}\sum_{i=1}^{3-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

  * •

Step 2: Assume that formula is true for an edge of size $l-1$.
For $x\in\mathbb{R}^{l-1}$, where $x=\begin{pmatrix}x_{1},x_{2},\cdots
x_{l-1}\end{pmatrix}^{t}$, we have

$\displaystyle
x^{t}L_{e}x=\sum_{j=1}^{l-2}\;\sum_{i=1}^{l-1-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

  * •

Step 3: Let $e=(v_{i_{1}},v_{i_{2}},\cdots,v_{i_{l-1}},v_{i_{l}})$. The
Laplacian matrix $L_{e}$ of the edge $e$ is as follows:

$\begin{pmatrix}d_{1}&-\mu_{11}&-2&-3&\cdots&-l+3&-l+2&-l+1\\\
-\mu_{11}&d_{2}&-1&-2&\cdots&-l+4&-l+3&-l+2\\\
-2&-1&d_{3}&-1&\cdots&-l+5&-l+4&-l+3\\\
-3&-2&-1&d_{4}&\cdots&-l+6&-l+5&-l+4\\\ &&&&\ddots&&&\\\
-l+3&-l+4&-l+5&-l+6&\cdots&d_{l-2}&-1&-2\\\
-l+2&-l+3&-l+4&-l+5&\cdots&-1&d_{l-1}&-\mu_{(l-1)1}\\\
-l+1&-l+2&-l+3&-l+4&\cdots&-2&-\mu_{(l-1)1}&d_{l}\end{pmatrix}$

where, $d_{j}$ is the degree of the $i_{j}^{th}$ vertex of $e$.
Here, $d_{j}=(j-1)+\cdots+2+1+1+2+\cdots+(l-j)$ for all $2<j<l-1$.
And

$\displaystyle d_{1}=$ $\displaystyle\;\mu_{11}+2+3+\cdots+(l-1)$
$\displaystyle d_{2}=$ $\displaystyle\;\mu_{11}+1+2+\cdots+(l-2)$
$\displaystyle d_{l-1}=$ $\displaystyle\;(l-2)+(l-3)+\cdots+1+\mu_{(l-1)1}$
$\displaystyle d_{r}=$ $\displaystyle\;(l-1)+(l-2)+\cdots+2+\mu_{(l-1)1}$

We can rewrite $L_{e}$ as

$\begin{pmatrix}d_{1}-(l-1)&-\mu_{11}&-2&\cdots&-l+3&-l+2&0\\\
-\mu_{11}&d_{2}-(l-2)&-1&\cdots&-l+4&-l+3&0\\\
-2&-1&d_{3}-(l-3)&\cdots&-l+5&-l+4&0\\\ &&&\ddots&&&\\\
-l+3&-l+4&-l+5&\cdots&d_{l-2}-2&-1&0\\\
-l+2&-l+3&-l+4&\cdots&-1&d_{l-1}-\mu_{(l-1)1}&0\\\
0&0&0&\cdots&0&0&0\end{pmatrix}$

+

$\begin{pmatrix}l-1&0&0&\cdots&0&0&-(l-1)\\\ 0&l-2&0&\cdots&0&0&-l+2\\\
0&0&l-3&\cdots&0&0&-l+3\\\ &&&\ddots&&&\\\ 0&0&0&\cdots&-2&0&-2\\\
0&0&0&\cdots&0&\mu_{(l-1)1}&-\mu_{(l-1)1}\\\
-l+1&-l+2&-l+3&\cdots&-2&-\mu_{(l-1)1}&d_{l}\end{pmatrix}$

For the first matrix in the summand, say $B$, the last row and column are
zero. Hence, the last column and row of $B$ don’t contribute anything in the
quadratic form expression. Thus, for $x=\begin{pmatrix}x_{1},x_{2},\cdots
x_{l}\end{pmatrix}^{t}\in\mathbb{R}^{l}$ we have
$x^{t}Bx=x^{t}L_{e^{\prime}}x$, where
$e^{\prime}=(v_{i_{1}},v_{i_{2}},\cdots,v_{i_{l-1}})$. Thus, by induction
assumption, for $x\in\mathbb{R}^{l}$, with
$x=\begin{pmatrix}x_{1},x_{2},\cdots x_{l}\end{pmatrix}^{t}$, we have

$\displaystyle
x^{t}L_{e^{\prime}}x=\sum_{j=1}^{l-2}\sum_{i=1}^{l-1-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

where $\mu_{ji}=i$ except when $v_{1}$ is middle end vertex then
$\mu_{11}=\frac{1}{2}$, here without loss of generality we assume that
$v_{i_{l-1}}$ is not a middle end vertex of the edge $e^{\prime}$.
Thus, for $x\in\mathbb{R}^{l}$, where $x=\begin{pmatrix}x_{1},x_{2},\cdots
x_{l}\end{pmatrix}^{t}$, we get

$\displaystyle
x^{t}L_{e}x=x^{t}L_{e^{\prime}}x+x^{t}L_{e-e^{\prime}}x\;\;\;\;\;\;\cdots(1)$

where $L_{e-e^{\prime}}$ is the second matrix in the summand.

Note that the second matrix in the summand gives us

$\displaystyle x^{t}L_{e-e^{\prime}}x=$
$\displaystyle(l-1)x^{2}_{1}-(l-1)x_{1}x_{l}+(l-2)x^{2}_{2}-(l-2)x_{2}x_{l}-\cdots$
$\displaystyle+2x^{2}_{l-2}-2x_{l-2}x_{l}+\mu_{(l-1)1}x^{2}_{l-1}-\mu_{(l-1)1}x_{l-1}x_{r}-(l-1)x_{1}x_{l}$
$\displaystyle-(l-2)x_{2}x_{l}-\cdots-2x_{l-2}x_{l}-\mu_{(l-1)1}x_{l-1}x_{l}+d_{l}x^{2}_{l}$
$\displaystyle=(l-1)(x_{1}-x_{r})^{2}+\cdots+2(x_{l-1}-x_{l})^{2}+\mu_{(l-1)1}(x_{l-1}-x_{l})^{2}$

Thus by (1), we get

$\displaystyle
x^{t}L_{e}x=\sum_{j=1}^{r-1}\sum_{i=1}^{r-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

∎

######  Theorem 2.4.

Let $L$ be the Laplacian matrix of a semigraph $G=(V,E)$, $L$ is positive
semi-definite.

###### Proof.

For an edge $e=(v_{i_{1}},v_{i_{2}},\cdots,v_{i_{l}})$ we re-write $L_{e}$ as

$\begin{pmatrix}\begin{matrix}L_{e}\end{matrix}&\vline&\mbox{\Large
0}_{l\times n-l}\\\ \hline\cr\mbox{\Large 0}_{n-l\times
l}&\vline&\begin{matrix}\mbox{\Large 0}_{n-l\times
n-l}\end{matrix}\end{pmatrix}_{n\times n}$

By additivity, we can write $\displaystyle L=\sum_{e\in E}L_{e}$
Thus,

$\displaystyle x^{t}Lx=x^{t}\left(\sum_{e\in E}L_{e}\right)x=\sum_{e\in
E}x^{t}L_{e}x$

By the Lemma 2.3 and observation 2.2, we get

$\displaystyle x^{t}Lx=\sum_{e\in
E}\sum_{j=1}^{l-1}\sum_{i=1}^{l-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

where $\mu_{ji}$ are defined as earlier, and these are positive numbers. This
implies $L$ is positive semi-definite. ∎

######  Remark 2.5.

We define the signless laplacian $Q$ as $D+A$. Using the similar arguments
above, we get

$\displaystyle x^{t}Qx=\sum_{e\in
E}\sum_{j=1}^{l-1}\sum_{i=1}^{l-j}\mu_{ji}(x_{j}+x_{j+i})^{2}$

Hence, signless laplacian is also positive semi-definite.

###  2.2 Algebraic connectivity of semigraph

We show that the graph theory result about algebraic connectivity holds true
for semigraphs, and the proof goes similar as well. Recall that for any graph
$G$, graph is connected iff second eigenvalue $\lambda_{2}$ of Laplacian is
positive.

######  Theorem 2.6.

Let $G=(V,E)$ be a semigraph, and let
$0=\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}\leq\cdots\leq\lambda_{n}$. Then
$G$ is connected iff $\lambda_{2}>0$.

###### Proof.

Assume that $G$ is disconnected. We show that $\lambda_{2}=0$.
For simplicity, assume that $G_{1}$ and $G_{2}$ are two connected components
of $G$. By reordering the indices, we can re-write the Laplacian matrix as
follows:

$L=\begin{pmatrix}L_{G_{1}}&\mathbf{0}\\\ \mathbf{0}&L_{G_{2}}\end{pmatrix}$

Observe that $\begin{pmatrix}\mathbf{1}\\\
\mathbf{0}\end{pmatrix},\;\begin{pmatrix}\mathbf{0}\\\
\mathbf{1}\end{pmatrix}$ are two orthogonal eigenvectors of the eigenvalue 0.
Thus, the geometric multiplicity of 0 is greater than or equal to 2 and hence
algebraic multiplicity is greater then or equal to 2 implies $\lambda_{2}=0$.
Assume that $G$ is connected; we show that algebraic multiplicity of 0 is 1.
Let $f\in\mathbb{R}^{n}$ be an eigenvector of 0. Thus, $Lf=0$, hence by Lemma
2.3, for each edge we get

$\displaystyle
0=f^{t}Lf=\sum_{j=1}^{r-1}\sum_{i=1}^{r-j}\mu_{ji}(x_{j}-x_{j+i})^{2}$

Therefore, $x_{1}=x_{j}$ for all vertices in an edge $e$. Thus, $f$ is
constant on each edge, and since $G$ is connected $f$ is constant on $V$.
Thus, $f$ is a constant vector; hence geometric multiplicity of 0 is 1. Thus,
algebraic multiplicity is 1. Hence, $\lambda_{2}>0$. ∎

##  3 Bounds on the largest Laplacian eigenvalue

We know that Laplacian is positive semi-definite, suppose
$0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ are the eigenvalues.
Let $\Delta$ be the maximum degree of a vertex, in this section, we prove that
$\lambda_{n}\geq\Delta+1$

######  Theorem 3.1.

Let $G=(V,E)$ be a semigraph with at least one edge. Let
$0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ then
$\lambda_{n}\geq\Delta+1$, where $\Delta$ is the largest degree of vertex in
the semigraph.

###### Proof.

As $L=(l_{ij})$ is positive semi-definite, by Cholsky decomposition
$L=T^{t}T$, where $T=(t_{ij})$ is the lower triangular matrix with non-
negative diagonal entries. WLOG, assume that $d_{1}$, degree of $v_{1}$ is the
largest degree. Thus, by comparison we get $d_{1}=l_{11}=t^{2}_{11}\implies
t_{11}=\sqrt{d_{1}}.$ Comparing the entries of the first columns we get
$l_{i1}=t_{11}t_{i1}\;\forall i=1,2,\cdots,n.$ Hence,

$l_{i1}=\sqrt{d_{1}}\;t_{i1}\;\cdots(1)$

Now, the first diagonal entry of $T^{t}T$ equal is to

$\displaystyle\displaystyle\sum_{i=1}^{n}t^{2}_{i1}=$
$\displaystyle\;\sum_{i=1}^{n}\left(\frac{l_{i1}}{\sqrt{d_{1}}}\right)^{2}$
$\displaystyle=$ $\displaystyle\;\frac{1}{d_{1}}\sum_{i=1}^{n}l^{2}_{i1}$
$\displaystyle\sum_{i=1}^{n}t^{2}_{i1}=$
$\displaystyle\;\frac{1}{d_{1}}\left(d^{2}_{1}+\sum_{i=2}^{n}l^{2}_{i1}\right)$
$\displaystyle=$
$\displaystyle\;d_{1}+\frac{1}{d_{1}}\sum_{i=2}^{n}l^{2}_{i1}$

Note that $\displaystyle\sum_{i=2}^{n}l^{2}_{i1}\geq\sum_{i=2}^{n}|l_{i1}|$
(Here, we get equality when $G$ is a graph).

$\implies\sum_{i=1}^{n}t^{2}_{i1}\geq
d_{1}+\frac{1}{d_{1}}\sum_{i=2}^{n}|l_{i1}|$

Note that $\displaystyle\sum_{i=2}^{n}|l_{i1}|$ is degree $d_{1}$ of the first
vertex $v_{1}$. Thus, we have

$\sum_{i=1}^{n}t^{2}_{i1}\geq d_{1}+1$

The largest eigenvalue of $T^{t}T$ exceeds or equals the largest diagonal
entry of $T^{t}T$; hence it exceeds or equals $d_{1}+1$. As eigenvalues of
$L,\;T^{t}T,\;TT^{t}$ are same implies $\lambda_{n}\geq\Delta+1$, where
$d_{1}=\Delta$. ∎

######  Remark 3.2.

The proof is similar to the proof of [2, Theorem 4.12]. In fact, when $G$ is a
graph, we get the graph theory result as a consequence of the above proof.

If $i^{th}$ and $j^{th}$ vertices make a partial edge, we denote it by
$j\sim_{S}i$, and if they make a partial half edge, then we denote it by
$j\sim_{|-}i$. If $i^{th}$ and $j^{th}$ vertices make a quarter edge then we
denote it by $j\sim_{|-|}i$, and if $d_{e}(i,j)=l$ for some edge then we
denote it by $j\sim_{l}i$. Let $d^{S}_{i}$ is the degree contribution to
degree of $i^{th}$ vertex due to all partial edges incident to it,
$d^{\frac{1}{2}}_{i}$ is the degree contribution to degree of $i^{th}$ vertex
due to all partial half edges incident to it, $d^{\frac{1}{4}}_{i}$ is the
degree contribution to degree of $i^{th}$ vertex due to all quarter edges
incident to it, $d^{l}_{i}$ is the degree contribution to degree of $i^{th}$
vertex due to all adjacent vertices which are $l$ distance apart from it. Note
that $\displaystyle
d_{i}=d^{S}_{i}+d^{\frac{1}{2}}_{i}+d^{\frac{1}{4}}_{i}+\sum_{l=2}^{r-1}d^{l}_{i}$.

Let $C_{S}(i,j)$ be the number of vertices that are consecutively adjacent to
both $i^{th}$ and $j^{th}$ vertices and form partial edges,
$C_{\frac{1}{2}}(i,j)$ is the number of vertices that are consecutively
adjacent to both $i^{th}$ and $j^{th}$ vertices and form partial half edges,
$C_{\frac{1}{4}}(i,j)$ is the number of vertices that are consecutively
adjacent to both $i^{th}$ and $j^{th}$ vertices and form quarter edges,
$C_{l}(i,j)$ is the number of vertices that are adjacent to both $i^{th}$ and
$j^{th}$ vertices and are $l$ distance apart from each of them. Let
$\displaystyle
C(i,j)=C_{S}(i,j)+C_{\frac{1}{2}}(i,j)+C_{\frac{1}{4}}(i,j)+\sum_{l=2}^{r-1}lC_{l}(i,j)$.

######  Theorem 3.3.

Let $G=(V,E)$ be a semigraph with at least one edge. Let
$0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ then

$\lambda_{n}\leq max\\{d_{i}+d_{j}-C(i,j)\\}$

###### Proof.

Let $\lambda_{n}$ be the largest eigenvalue. Let
$x=(x_{1},x_{2},\cdots,x_{n})^{t}\in\mathbb{R}^{n}$ be an eigenvector such
that $Lx=\lambda_{n}x$. We choose $i$ such that $\displaystyle
x_{i}=\underset{\;\;\;k}{m}ax\;x_{k}$. Further, we choose $j$ such that
$\displaystyle x_{j}=\underset{\;\;\;k}{m}in\\{x_{k}:k\sim i\\}.$ Here
adjacency is the semigraph adjacency. Comparing the $i^{th}$, $j^{th}$
components of $(D-A)x=\lambda_{n}x$, we get

$\displaystyle\lambda_{n}x_{i}=d_{i}x_{i}-\sum_{k\sim_{s}i}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}i}x_{k}-\frac{1}{4}\sum_{k\sim_{|-|}i}x_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}i}lx_{k}$

and

$\displaystyle\lambda_{n}x_{j}=d_{j}x_{j}-\sum_{k\sim_{s}j}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}j}x_{k}-\frac{1}{4}\sum_{k\sim_{|-|}j}x_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}j}lx_{k}$

Rewriting the above two equations, we get

$\displaystyle\displaystyle\lambda_{n}x_{i}=$
$\displaystyle\;d_{i}x_{i}-\sum_{k\sim_{s}i;\;k\sim_{s}j}x_{k}-\sum_{k\sim_{s}i;\;k\nsim_{s}j}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}i;\;k\sim_{|-}j}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}i;\;k\nsim_{|-}j}x_{k}$
$\displaystyle-\frac{1}{4}\sum_{k\sim_{|-|}i;\;k\sim_{|-|}j}x_{k}-\frac{1}{4}\sum_{k\sim_{|-|}i;\;k\nsim_{|-|}j}x_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}i;\;k\sim_{l}j}lx_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}i;\;k\nsim_{l}j}lx_{k}$

and

$\displaystyle\displaystyle\lambda_{n}x_{j}=$
$\displaystyle\;d_{j}x_{j}-\sum_{k\sim_{s}j;\;k\sim_{s}i}x_{k}-\sum_{k\sim_{s}j;\;k\nsim_{s}i}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}j;\;k\sim_{|-}i}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}j;\;k\nsim_{|-}i}x_{k}$
$\displaystyle-\frac{1}{4}\sum_{k\sim_{|-|}j;\;k\sim_{|-|}i}x_{k}-\frac{1}{4}\sum_{k\sim_{|-|}j;\;k\nsim_{|-|}i}x_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}j;\;k\sim_{l}i}lx_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}j;\;k\nsim_{l}i}lx_{k}$

Subtract the second equation from the first

$\displaystyle\displaystyle\lambda_{n}(x_{i}-x_{j})=$ $\displaystyle
d_{i}x_{i}-\;d_{j}x_{j}-\sum_{k\sim_{s}i;\;k\nsim_{s}j}x_{k}+\sum_{k\sim_{s}j;\;k\nsim_{s}i}x_{k}-\frac{1}{2}\sum_{k\sim_{|-}i;\;k\nsim_{|-}j}x_{k}+\frac{1}{2}\sum_{k\sim_{|-}j;\;k\nsim_{|-}i}x_{k}$
$\displaystyle-\frac{1}{4}\sum_{k\sim_{|-|}i;\;k\nsim_{|-|}j}x_{k}+\frac{1}{4}\sum_{k\sim_{|-|}j;\;k\nsim_{|-|}i}x_{k}-\sum_{l=2}^{r-1}\sum_{k\sim_{l}i;\;k\nsim_{l}j}lx_{k}+\sum_{l=2}^{r-1}\sum_{k\sim_{l}j;\;k\nsim_{l}i}lx_{k}$
$\displaystyle\leq$
$\displaystyle\;\;d_{i}x_{i}-d_{j}x_{j}-\left(d^{S}_{i}-C_{S}(i,j)\right)x_{j}+\left(d^{S}_{j}-C_{S}(i,j)\right)x_{i}-\left(d^{\frac{1}{2}}_{i}-\frac{1}{2}C_{\frac{1}{2}}(i,j)\right)x_{j}$
$\displaystyle+\left(d^{\frac{1}{2}}_{j}-\frac{1}{2}C_{\frac{1}{2}}(i,j)\right)x_{i}-\left(d^{\frac{1}{4}}_{i}-\frac{1}{4}C_{\frac{1}{4}}(i,j)\right)x_{j}+\left(d^{\frac{1}{4}}_{j}-\frac{1}{4}C_{\frac{1}{4}}(i,j)\right)x_{i}$
$\displaystyle-\left(\sum_{l=2}^{r-1}d^{l}_{j}-lC_{l}(i,j)\right)x_{j}+\left(\sum_{l=2}^{r-1}d^{l}_{i}-lC_{l}(i,j)\right)x_{i}$

By simplifying and rewriting it, we get

$\displaystyle\displaystyle\lambda_{n}(x_{i}-x_{j})\leq$
$\displaystyle\;\;(d_{i}+d_{j})(x_{i}-x_{j})-C_{S}(i,j)(x_{i}-x_{j})-\frac{1}{2}C_{\frac{1}{2}}(i,j)(x_{i}-x_{j})$
$\displaystyle-\frac{1}{4}C_{\frac{1}{4}}(i,j)(x_{i}-x_{j})-\left(\sum_{l=2}^{r-1}lC_{l}(i,j)\right)(x_{i}-x_{j}).$

Thus, we get

$\lambda_{n}(x_{i}-x_{j})\leq\;\;(d_{i}+d_{j}-C(i,j))(x_{i}-x_{j})$

Note that $\lambda_{n}$ is not $0$ as our graph is connected having at least
of one edge. Thus, there is some $j$ such that $j^{th}$ vertex is adjacent to
$i^{th}$ vertex and $x_{i}>x_{j}$. Hence,
$\lambda_{n}\leq(d_{i}+d_{j}-C(i,j))$ ∎

######  Remark 3.4.

The proof is similar to the proof of [2, Theorem 4.13], and if $G$ is a graph,
we get the graph theory result as the consequence of above result.

##  4 Laplacian Eigenvalues of stars

In this section, we define different types of star semigraphs and study their
Laplacian eigenvalues. Consider a semigraph $S^{3}_{2,n}$ on $n+3$ vertices;
all edges are of size two except one edge, which has three vertices, as shown
in Fig. 2

$v_{2}$$v_{1}$$v_{3}$$v_{4}$$v_{r}$$v_{n+3}$$v_{r+1}$

$\text{Star semigraphs:}\;\;S^{3}_{2,n}$

Figure 2:

The Laplacian $L$ is as follows:

$\bordermatrix{&{v_{1}}&{v_{2}}&{v_{3}}&{v_{4}}&{v_{5}}&\cdots&{v_{n+3}}\cr
v_{1}&\frac{(n+4)}{2}&-1&-1&-\frac{1}{2}&-\frac{1}{2}&\cdots&-\frac{1}{2}\cr
v_{2}&-1&3&-2&0&0&\cdots&0\cr v_{3}&-1&-2&3&0&0&\cdots&0\cr
v_{4}&-\frac{1}{2}&0&0&\frac{1}{2}&0&\cdots&0\cr
v_{5}&-\frac{1}{2}&0&0&0&\frac{1}{2}&\cdots&0\cr\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\cr
v_{n+3}&-\frac{1}{2}&0&0&0&0&\cdots&\frac{1}{2}}\qquad$

######  Lemma 4.1.

The Laplacian spectrum of star semigraph $S^{3}_{2,n}$ is:

$\begin{pmatrix}0&0.5&\lambda_{1}&\lambda_{2}&\lambda_{3}\\\
1&n-1&1&1&1\end{pmatrix}$

where $\lambda_{1},\lambda_{2},\lambda_{3}$ are roots of the cubic polynomial
$\lambda^{3}-\frac{n+17}{2}\;\lambda^{2}+(19+3n)\lambda-\frac{5n+15}{2}.$

###### Proof.

Let $P_{n}(\lambda)=det(\lambda I-L)$ be the characteristic polynomial of
$S^{3}_{2,n}$.

$P_{n}(\lambda)=\begin{vmatrix}\lambda-\frac{n+4}{2}&1&1&\frac{1}{2}&\cdots&\frac{1}{2}&\frac{1}{2}\\\
1&\lambda-3&2&0&\cdots&0&0\\\ 1&2&\lambda-3&0&\cdots&0&0\\\
\frac{1}{2}&0&0&\lambda-\frac{1}{2}&\cdots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\frac{1}{2}&0&0&0&\cdots&\lambda-\frac{1}{2}&0\\\
\frac{1}{2}&0&0&0&\cdots&0&\lambda-\frac{1}{2}\end{vmatrix}$

Using cofactor expansion along the first column, we get

$\displaystyle P_{n}(\lambda)=$
$\displaystyle\left(\lambda-\frac{1}{2}\right)^{n}\left[\left((\lambda-3)^{2}-4\right)\left(\lambda-\frac{n+4}{2}\right)\right]-2\left(\lambda-\frac{1}{2}\right)^{n}(\lambda-5)$
$\displaystyle-\frac{n}{4}\left(\lambda-\frac{1}{2}\right)^{n-1}\left[(\lambda-3)^{2}-4\right]$
$P_{n}(\lambda)=\left(\lambda-\frac{1}{2}\right)^{n-1}\left[\left(\lambda^{2}-6\lambda+5\right)\left[\left(\lambda-\frac{1}{2}\right)\left(\lambda-\frac{n+4}{2}\right)-\frac{n}{4}\right]-2\left(\lambda-\frac{1}{2}\right)(\lambda-5)\right]$

Simplifying it further, we get

$P_{n}(\lambda)=\displaystyle\lambda\left(\lambda-\frac{1}{2}\right)^{n-1}\left(\lambda^{3}-\frac{n+17}{2}\;\lambda^{2}+(19+3n)\lambda-\frac{5n+15}{2}\right)$

Thus, the Laplacian spectra of star semigraphs
are:$\left\\{0,\frac{1}{2}\text{(n-1
times)},\;\lambda_{1},\lambda_{2},\lambda_{3}\right\\};$ where
$\lambda_{1},\lambda_{2},\lambda_{3}$ are roots of the cubic polynomial

$\lambda^{3}-\frac{n+17}{2}\;\lambda^{2}+(19+3n)\lambda-\frac{5n+15}{2}.$

∎

###  4.1 Laplacian eigenvalues of rooted 3-uniform semigraph tree

Here, we compute the Laplacian eigenvalues of the rooted 3-uniform semigraph
tree. Let $T^{3}_{n}$ denote the semigraph on $2n+1$ vertices with $n$ edges.
The edge set $E$ is given by $\\{(v_{1},v_{2i},v_{2i+1})\;\big{|}\;1\leq i\leq
n\\}$

$v_{1}$$v_{2n}$$v_{2n+1}$$v_{2}$$v_{3}$$v_{2r}$$v_{2r+1}$

$T^{3}_{n}$

Figure 3:

The Laplacian matrix $L$ of 3-uniform tree: $T^{3}_{n}$ is

$\bordermatrix{&{v_{1}}&{v_{2}}&{v_{3}}&{v_{4}}&{v_{5}}&\cdots&{v_{2n-2}}&{v_{2n-1}}&{v_{2n}}&{v_{2n+1}}\cr
v_{1}&3n&1&2&1&2&\cdots&1&2&1&2\cr v_{2}&1&2&1&0&0&\cdots&0&0&0&0\cr
v_{3}&2&1&3&0&0&\cdots&0&0&0&0\cr v_{4}&1&0&0&2&1&\cdots&0&0&0&0\cr
v_{5}&2&0&0&1&3&\cdots&0&0&0&0\cr\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\cr
v_{2n-2}&1&0&0&0&0&\cdots&2&1&0&0\cr v_{2n-1}&2&0&0&0&0&\cdots&1&3&0&0\cr
v_{2n}&1&0&0&0&0&\cdots&0&0&2&1\cr v_{2n+1}&2&0&0&0&0&\cdots&0&0&1&3}\qquad$

######  Lemma 4.2.

The Laplacian spectrum of star semigraph $T^{3}_{n}$ is:

$\begin{pmatrix}0&\frac{5\pm\sqrt{5}}{2}&\lambda_{1}&\lambda_{2}\\\
1&n-1&1&1\end{pmatrix}$

where $\lambda_{1},\lambda_{2}$ are roots of the quadratic polynomial
$\lambda^{2}-(3n+5)\lambda+10n+5.$

###### Proof.

Let $T_{n}(\lambda)=det(\lambda I-L)$ be the characteristic polynomial of
$T^{3}_{n}$.

$T_{n}(\lambda)=\begin{vmatrix}\lambda-3n&1&2&1&2&\cdots&1&2&1&2\\\
1&\lambda-2&1&0&0&\cdots&0&0&0&0\\\ 2&1&\lambda-3&0&0&\cdots&0&0&0&0\\\
1&0&0&\lambda-2&1&\cdots&0&0&0&0\\\ 2&0&0&1&\lambda-3&\cdots&0&0&0&0\\\
&&&\vdots&&\vdots&&&&\\\ 1&0&0&0&0&\cdots&\lambda-2&1&0&0\\\
2&0&0&0&0&\cdots&1&\lambda-3&0&0\\\ 1&0&0&0&0&\cdots&0&0&\lambda-2&1\\\
2&0&0&0&0&\cdots&0&0&1&\lambda-3\end{vmatrix}$

Using co-factor expansion along the first column, we get

$\displaystyle T_{n}(\lambda)=$
$\displaystyle(\lambda-3n)\left[(\lambda-2)(\lambda-3)-1\right]^{n}-(\lambda-5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}$
$\displaystyle+$ $\displaystyle
2(-2\lambda+5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}+\cdots+$
$\displaystyle-(\lambda-5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}+2(-2\lambda+5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}$
$\displaystyle=$
$\displaystyle(\lambda-3n)\left[(\lambda-2)(\lambda-3)-1\right]^{n}-n(\lambda-5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}$
$\displaystyle+2n(-2\lambda+5)\left[(\lambda-2)(\lambda-3)-1\right]^{n-1}$

Simplifying this further, we get

$T_{n}(\lambda)=\displaystyle\lambda\left(\lambda^{2}-5\lambda+5\right)^{n-1}\left(\lambda^{2}-(3n+5)\lambda+10n+5\right)$

Thus, the Laplacian spectra of star semigraphs
are:$\left\\{0,\frac{5\pm\sqrt{5}}{2}\text{(n-1
times)},\;\lambda_{1},\lambda_{2}\right\\};$ where $\lambda_{1},\lambda_{2}$
are roots of the quadratic polynomial

$\lambda^{2}-(3n+5)\lambda+10n+5.$

∎

##  5 Conclusion

We could provide evidence that shows that spectral theory for semigraphs
generalizes the spectral theory of graphs. The Laplacian matrix is symmetric
positive semi-definite which is a very well understood class of matrices, and
hence it opens doors to several research problems in spectral semigraph
theory.

Author Contributions: I declare that I carried out all work on my own.
Funding: No funding.
Availability of data and material All data generated or analyzed during this
study are included in this published article.

### Declarations:

There is no conflict of interest.

## References

  * [1] Pralhad M. Shinde, Adjacency spectra of semigraphs, Discrete Mathematics, Algorithms and Applications, 2023. https://doi.org/10.1142/s1793830923500118.
  * [2] Ravindra B Bapat, Graphs and matrices, vol. 27, Springer, 2010.
  * [3] Sampathkumar E.; et al, Semigraphs and their applications (2019), Academy of discrete mathematics and applications, India.
  * [4] Mohar, Bojan, Y. Alavi, G. Chartrand, and O. R. Oellermann, The Laplacian spectrum of graphs, Graph theory, combinatorics, and applications 2, no. 871-898 (1991): 12.
  * [5] YS Gaidhani, CM Deshpande, and BP Athawale, Adjacency matrix of a semigraph, Electronic Notes in Discrete Mathematics 63 (2017), 399–406.