# The Smallest Eigenvalue of Large Hankel Matrices Generated by a Deformed
Laguerre Weight

Mengkun<EMAIL_ADDRESS>Department of Mathematics, University of
Macau, Avenida da Universidade, Taipa, Macau, China  Niall
<EMAIL_ADDRESS>College of Information and Computer Sciences,
University of Massachusetts, Amherst, MA 01003, USA  Yang
<EMAIL_ADDRESS>Department of Mathematics, University of
Macau, Avenida da Universidade, Taipa, Macau, China  Charles
<EMAIL_ADDRESS>College of Information and Computer Sciences,
University of Massachusetts, Amherst, MA 01003, USA

###### Abstract

We study the asymptotic behavior of the smallest eigenvalue, $\lambda_{N}$, of
the Hankel (or moments) matrix denoted by
$\mathcal{H}_{N}=\left(\mu_{m+n}\right)_{0\leq m,n\leq N}$, with respect to
the weight $w(x)=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2}$. Based on
the research by Szegö, Chen, etc., we obtain an asymptotic expression of the
orthonormal polynomials $\mathcal{P}_{N}(z)$ as $N\rightarrow\infty$,
associated with $w(x)$. Using this, we obtain the specific asymptotic formulas
of $\lambda_{N}$ in this paper.

Applying the parallel algorithm discovered by Emmart, Chen and Weems, we get a
variety of numerical results of $\lambda_{N}$ corresponding to our theoretical
calculations.

##  1 Introduction

Random matrix theory (RMT) originated in multivariate statistics in the work
of Hsu, Wishart and others in the 1930s (see the monograph [23]). In 1950s,
Wigner put forward similar models for the regularity observed in the energy
level distribution of heavy nuclei, where the energy levels are the
eigenvalues of large random matrices. From the 1960s to 1970s, through the
fundamental work of Dyson, Mehta, Gaudin, des Cloizeaux, Widom, Tracy, Wilf
and others, RMT developed into a branch of Mathematical Physics. Its rapid
development from the 1990s is due a string of fundamental discoveries of Tracy
and Widom on the probability laws governing the largest and smallest
eigenvalues of two families of Hermitian random matrices, the Gaussian Unitary
Ensembles (GUE) and the Laguerre Unitary Ensembles (LUE).

RMT plays an important role in many diverse fields, multivariate statistics,
quantum physics, Multi-Input-Multi-Output (MIMO) wireless communication, and
stock movements in financial markets, etc. For a variety of theories and
applications of RMT, see [14, 22, 7, 24, 2, 6, 15, 16, 25] and related
references therein. RMT considers the properties, e.g. determinants,
eigenvalues, eigenvalue distributions, eigenvectors, spectra, inverse, etc.,
of matrices whose elements are random variables chosen from a given
distribution.

The analysis of Hankel matrices, occurs naturally in moment problems, which
plays an important role in RMT. On moment problems, please see the monographs
by Akhiezer [1] and by Krein [20]. The study of the largest and smallest
eigenvalues are important since they provide useful information about the
nature of the Hankel matrix generated by a given weight function, e.g. they
are related with the inversion of Hankel matrices, where the condition numbers
are enormously large.

Given $\left\\{\mu_{k}\right\\}$ the moment sequence of a weight function
$w(x)(>0)$ with infinite support $s$,

$\mu_{k}:=\int_{s}x^{k}w(x)dx,~{}~{}k=0,1,2,\ldots,$ (1.1)

the Hankel matrices, it is known that

$\mathcal{H}_{N}:=\left(\mu_{m+n}\right)_{m,n=0}^{N},~{}~{}N=0,1,2,\ldots$
(1.2)

are positive definite, see [19].

Let $\lambda_{N}$ denote the smallest eigenvalue of $\mathcal{H}_{N}$. The
asymptotic behavior of $\lambda_{N}$ for large $N$ has been investigated in
[26, 28, 29, 30, 12, 13, 17, 5, 8, 31]. Also see [4, 21], in which the authors
have studied the behavior of the condition number
$\kappa\left(\mathcal{H}_{N}\right):=\frac{\Lambda_{N}}{\lambda_{N}}$, where
$\Lambda_{N}$ denotes the largest eigenvalue of $\mathcal{H}_{N}$.

Szegö [26] studied the asymptotic behavior of $\lambda_{N}$ for the Hermite
(or Gaussion) weight ($w(x)={\rm e}^{-x^{2}},x\in\mathbb{R}$) and the Laguerre
weight ($w(x)={\rm e}^{-x},x\geq 0$). He found111 In all of this paper,
$a_{N}\simeq b_{N}$ means $\lim_{N\rightarrow\infty}a_{N}/b_{N}$=1.

$\lambda_{N}\simeq AN^{\frac{1}{4}}B^{\sqrt{N}},$

where $A,B$ are certain constants, satisfying $0<A,~{}0<B<1$. Also, Szegö [26]
showed that the largest eigenvalue $\Lambda_{N}$ corresponding to the Hankel
matrices $\left[\frac{1}{i+j+1}\right]_{i,j=0}^{N}$,
$\left[\Gamma\left(\frac{i+j+1}{2}\right)\right]_{i,j=0}^{N}$ and
$\left[\Gamma(i+j+1)\right]_{i,j=0}^{N}$ were approximated by $\frac{\pi}{2}$,
$\Gamma\left(N+\frac{1}{2}\right)$ and $(2N)!$ respectively.

In [29], Widom and Wilf investigated the case where $w(x)$ is supported in a
compact interval $[a,b]$, such that the Szegö condition

$\int_{a}^{b}\frac{\ln w(x)}{\sqrt{(b-x)(x-a)}}dx>-\infty,$ (1.3)

holds, then they obtained

$\lambda_{N}\simeq A\sqrt{N}B^{N}.$

Chen and Lawrence [12] found the asymptotic behavior of $\lambda_{N}$ with the
weight function $w(x)={\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\beta>\frac{1}{2}$. Berg, Chen and Ismail
[5] proved that the moment sequence (1.1) is determinate iff
$\lambda_{N}\rightarrow 0$ as $N\rightarrow\infty$. This is a new criteria for
the determinacy of the Hamburger moment problem. Also, in the same paper, they
obtained a lower bound of $\lambda_{N}$ for large $N$. In [13], Chen and
Lubinsky obtained the behavior of $\lambda_{N}$ when $w(x)={\rm
e}^{-|x|^{\alpha}},~{}x\in\mathbb{R},~{}\alpha>1$. Berg and Szwarc [8] proved
that $\lambda_{N}$ has exponential decay to zero for any measure which with
compact support.

Zhu, Chen, Emmart and Weems [31] studied the Jacobi case, i.e.
$w(x)=x^{\alpha}(1-x)^{\beta},~{}x\in[0,1],~{}\alpha>-1,~{}\beta>-1$ and
provided a asymptotic behavior of $\lambda_{N}$,

$\lambda_{N}\simeq
2^{\frac{15}{4}}\pi^{\frac{3}{2}}\left(1+2^{\frac{1}{2}}\right)^{-2\alpha}\left(1+2^{-\frac{1}{2}}\right)^{-2\beta}N^{\frac{1}{2}}\left(1+2^{\frac{1}{2}}\right)^{-4(N+1)},$

which reduces to Sezgö’s result [26], if $\alpha=\beta=0$.

The examples above show that the values of $\lambda_{N},N\rightarrow\infty$
are exponentially small, and the asymptotic behavior of $\lambda_{N}$ depends
on the $w(x)$ in a non-trivial way. We are motivated by this phenomenon and
the purpose of this paper is again to study the asymptotic behavior of
$\lambda_{N}$, here we choose an generalised Laguerre weight
$w(x)=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2}$.

The remainder of this paper is organized in 5 sections. In section 2 we
reproduce some known results (Refs. [26, 12, 13, 5], etc.) that will be
applied to find the estimation of $\lambda_{N}$. In section 3, by adopting a
previous result [11], we obtain the asymptotic formula for the polynomials
orthonormal with respect to $w(x)=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2}$, which is
then employed in sections 4 and 5 for the determination of the large $N$
behavior of $\lambda_{N}$. And finally, in section 6, we present a comparison
of the theoretical results to numeric calculations for the smallest
eigenvalue, for various values of $\alpha$, $\beta$ and $N$. The numerical
computations were performed using the parallel algorithms developed in [17].

##  2 Preliminaries

Consider the weight

$w(x):=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2},$

in this case, the moments are

$\mu_{n}:=\int_{0}^{\infty}x^{n}w(x)dx=\frac{1}{\beta}\Gamma\left(\frac{1+\alpha+n}{\beta}\right),$

and the positive Hankel matrix is

$\mathcal{H}_{N}:=\left(\mu_{m+n}\right)_{m,n=0}^{N}.$

The focus of this paper is to derive the asymptotic behavior of the smallest
eigenvalue $\lambda_{N}$ of $\mathcal{H}_{N}$.

It is well known that the smallest eigenvalue $\lambda_{N}$ can be found using
the classical Rayleigh quotient

$\lambda_{N}=\min\left\\{\frac{\sum_{m,n=0}^{N}\overline{x}_{m}\mu_{m+n}x_{n}}{\sum_{n=0}^{N}|x_{n}|^{2}}~{}\Bigg{|}~{}X:=\left(x_{0},x_{1},\ldots,x_{N}\right)^{T}\in\mathbb{C}^{N+1}\setminus\\{0\\}\right\\}.$
(2.1)

Let $P_{N}$ be the orthogonal polynomials associated with $w(x)$, and denote
by

$P_{N}(z):=\sum_{n=0}^{N}x_{n}z^{n},$

then

$\int_{0}^{\infty}|P_{N}(x)|^{2}w(x)dx=\sum_{m,n=0}^{N}\overline{x}_{m}\mu_{m+n}x_{n},$
(2.2)

If we denote the orthonomal polynomials associated with the weight $w(x)$ by
$\mathcal{P}_{N}(x)$, through

$P_{N}(z)=\sqrt{h_{N}}\mathcal{P}_{N}(z),$

where $h_{N}$ is the square of the $L^{2}$ norm of $P_{N}(z)$, such that

$\int_{0}^{\infty}|\mathcal{P}_{N}(x)|^{2}w(x)dx=1,$ (2.3)

then the expression for $\lambda_{N}$, (2.1), can be recast as

$\lambda_{N}=\min\left\\{\frac{2\pi}{\int_{-\pi}^{\pi}\left|\mathcal{P}_{N}({\rm
e}^{{\rm i}\theta})\right|^{2}d\theta}\right\\}.$ (2.4)

If we define

$P_{N}(z):=\sum_{n=0}^{N}\xi_{n}\mathcal{P}_{n}(z),~{}~{}~{}{\rm
and}~{}~{}~{}\mathcal{K}_{mn}:=\int_{-\pi}^{\pi}\mathcal{P}_{m}\left({\rm
e}^{{\rm i}\theta}\right)\mathcal{P}_{n}\left({\rm e}^{-{\rm
i}\theta}\right)d\theta,$

we can see that

$\int_{-\pi}^{\pi}\left|P_{N}\left({\rm e}^{{\rm
i}\theta}\right)\right|^{2}d\theta=\sum_{m,n=0}^{N}\overline{\xi}_{m}\mathcal{K}_{mn}\xi_{n},$

Hence, the formula (2.4) will be equivalent to

$\lambda_{N}=\min\left\\{\frac{2\pi}{\sum_{m,n=0}^{N}\overline{\xi}_{m}\mathcal{K}_{mn}\xi_{n}}:\sum_{n=0}^{N}\left|\xi_{n}\right|^{2}=1\right\\}.$
(2.5)

Based on the Cauchy-Schwarz inequality, we will find that

$\begin{split}\sum_{m,n=0}^{N}\overline{\xi}_{m}\mathcal{K}_{mn}\xi_{n}\leq\sum_{m,n=0}^{N}\mathcal{K}_{mm}^{\frac{1}{2}}\mathcal{K}_{nn}^{\frac{1}{2}}\left|\xi_{m}\right|\left|\xi_{n}\right|\leq\sum_{m=0}^{N}\mathcal{K}_{mm}\cdot\sum_{n=0}^{N}\left|\xi_{n}\right|^{2}\leq\sum_{n=0}^{N}\mathcal{K}_{nn}.\end{split}$

Therefore, a lower bound for the smallest eigenvalue of $\lambda_{N}$ is given
by

$\lambda_{N}\geq\frac{2\pi}{\sum_{n=0}^{N}\mathcal{K}_{nn}}.$ (2.6)

##  3 The orthonomal polynomials with respect to the weight
$w(x)=x^{\alpha}{\rm e}^{-x^{\beta}}$.

The purpose of this section is to find the asymptotics of the orthonomal
polynomials $\\{\mathcal{P}_{N}(z)\\}$ with respect to the weight
$w(x)=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2}$. Based on
the Coulomb fluid linear statistics method, it has been proved in [11], for
$N\rightarrow\infty$, that the monic orthogonal polynomials $P_{N}(z)$
associated with $w(x)={\rm e}^{-v(x)}$ can be approximated by

$P_{N}(z)\simeq\exp\left[-S_{1}(z)-S_{2}(z)\right],$ (3.1)

where

$S_{1}(z)=\frac{1}{4}\ln\left[\frac{16(z-a)(z-b)}{(b-a)^{2}}\left(\frac{\sqrt{z-a}-\sqrt{z-b}}{\sqrt{z-a}+\sqrt{z-b}}\right)^{2}\right],~{}\text{$z\notin[a,b]$},$

$\begin{split}S_{2}(z)&=-N\ln\left(\frac{\sqrt{z-a}+\sqrt{z-b}}{2}\right)^{2}\\\
&+\frac{1}{2\pi}\int_{a}^{b}\frac{v(x)}{\sqrt{(b-x)(x-a)}}\left[\frac{\sqrt{(z-a)(z-b)}}{x-z}+1\right]dx,~{}\text{$z\notin[a,b]$}.\end{split}$

Chen and his co-authors[9] also gave an equivalent representation for $S_{1}$:

${\rm
e}^{-S_{1}(z)}=\frac{1}{2}\left[\left(\frac{z-b}{z-a}\right)^{\frac{1}{4}}+\left(\frac{z-a}{z-b}\right)^{\frac{1}{4}}\right],~{}\text{$z\notin[a,b]$}.$

Consequently, we have,

######  Theorem 3.1.

For $N\rightarrow\infty$, the orthonomal polynomials associated with the
weight $w(x)=x^{\alpha}{\rm
e}^{-x^{\beta}},~{}x\in[0,\infty),~{}\alpha>-1,~{}\beta>\frac{1}{2}$ are
approximated by

$\mathcal{P}_{N}(z)\simeq(-z)^{-\frac{\alpha}{2}}\frac{(-1)^{N}}{\sqrt{2\pi
b}}\frac{\exp\left[-\mathcal{I}(z)+(2N+1+\alpha)\log\left(\sqrt{\eta}+\sqrt{\eta+1}\right)\right]}{\left[\eta(1+\eta)\right]^{\frac{1}{4}}},$

with

$\begin{split}\mathcal{I}(z):&=-\frac{2N+\alpha}{2\beta-1}\sqrt{\eta(1+\eta)}\cdot{{}_{2}F_{1}}\left(1,1-\beta;\frac{3}{2}-\beta;-\eta\right)-\frac{(-z)^{\beta}}{2}\cdot\sec(\pi\beta)\\\
&=-\frac{2N+\alpha}{2\beta}\sqrt{\frac{\eta}{1+\eta}}\cdot{{}_{2}F_{1}}\left(1,\frac{1}{2};1+\beta;\frac{1}{1+\eta}\right),\\\
\end{split}$ (3.2)

where $z\notin[0,b]$ and $\eta:=-\frac{z}{b}$, whilst

$b:=C(2N+\alpha)^{\frac{1}{\beta}}~{}~{}~{}{and}~{}~{}~{}C=C(\beta):=4\left[\frac{\Gamma(\beta+1)\Gamma(\beta)}{\Gamma(2\beta+1)}\right]^{\frac{1}{\beta}}.$

###### Proof.

For our problem, $a=0$, whilst $b(N,\alpha,\beta)$ follows from the
supplementary condition [11, 10]

$\int_{a}^{b}\frac{xv^{\prime}(x)}{\sqrt{(b-x)(x-a)}}=2\pi N,$

where

$v(x)=-\ln w(x)=-\alpha\ln x+x^{\beta}.$

Hence we have

$b=C(2N+\alpha)^{\frac{1}{\beta}}~{}~{}~{}{\rm
with}~{}~{}~{}C:=4\left[\frac{\Gamma(\beta+1)\Gamma(\beta)}{\Gamma(2\beta+1)}\right]^{\frac{1}{\beta}}.$

Let $\eta:=-\frac{z}{b},~{}z\notin[0,b]$, by taking the branch
$-b\eta=b\eta{\rm e}^{{\rm i}\pi}$, $-b\eta-b=b(1+\eta){\rm e}^{{\rm i}\pi}$
we have

$\begin{split}-S_{1}(z)=\ln\left[2^{-1}\cdot\left(\eta(\eta+1)\right)^{-\frac{1}{4}}\left(\sqrt{\eta+1}+\sqrt{\eta}\right)\right],\\\
\end{split}$
$\begin{split}-S_{2}(z)&=N\ln\left(\frac{\sqrt{-b\eta}+\sqrt{-b\eta-b}}{2}\right)^{2}-\frac{1}{2\pi}\int_{0}^{b}\frac{-\alpha\ln
x+x^{\beta}}{\sqrt{(b-x)x}}\left[\frac{\sqrt{z(z-b)}}{x-z}+1\right]dx\\\
&=N\ln\frac{-b\left(\sqrt{\eta}+\sqrt{\eta+1}\right)^{2}}{4}-f(z)-K,\\\
\end{split}$

where

$\begin{split}K:=\frac{1}{2\pi}\int_{0}^{b}\frac{-\alpha\ln
x+x^{\beta}}{\sqrt{(b-x)x}}dx=-\frac{\alpha}{2}\ln b+\alpha\ln
2+\frac{2N+\alpha}{2\beta},\end{split}$

and $f(z)$ is defined by

$f(z):=\frac{\sqrt{z(z-b)}}{2\pi}\int_{0}^{b}\frac{-\alpha\ln
x+x^{\beta}}{\sqrt{x(b-x)}(x-z)}dx,~{}\text{$z\notin[0,b]$}.$ (3.3)

Next, we will focus on the explicit formula of $f(z)$. From (3.3), we have

$\begin{split}&f(z):=\mathcal{I}_{1}(z)+\mathcal{I}(z)\\\
&=:-\frac{\alpha\sqrt{z(z-b)}}{2\pi}\int_{0}^{b}\frac{\ln
x}{\sqrt{x(b-x)}(x-z)}dx+\frac{\sqrt{z(z-b)}}{2\pi}\int_{0}^{b}\frac{x^{\beta}}{\sqrt{x(b-x)}(x-z)}dx.\\\
\end{split}$

With the aid of the integral identities in the Appendix, we get

$\begin{split}\mathcal{I}_{1}(z)=-\frac{\alpha\sqrt{z(z-b)}}{2\pi}\int_{0}^{b}\frac{\ln
x}{(x-z)\sqrt{x(b-x)}}dx=\frac{\alpha}{2}\ln(-z)-\alpha\ln\left(\sqrt{\eta+1}+\sqrt{\eta}\right).\end{split}$

From the definition and basic properties of the Hypergeometric function [18],

$\begin{split}\mathcal{I}(z)&=\frac{\sqrt{z(z-b)}}{2\pi}\int_{0}^{1}\frac{(by)^{\beta}}{(by-z)\sqrt{by(b-by)}}bdy\\\
&=-\sqrt{\frac{z(z-b)}{\pi}}\cdot\frac{b^{\beta}}{2z}\cdot\frac{\Gamma\left(\frac{1}{2}+\beta\right)}{\Gamma(1+\beta)}\cdot{{}_{2}F_{1}}\left(1,\frac{1}{2}+\beta;1+\beta;-\frac{1}{\eta}\right)\\\
&=-\frac{2N+\alpha}{2\beta-1}\sqrt{\eta(1+\eta)}\cdot{{}_{2}F_{1}}\left(1,1-\beta;\frac{3}{2}-\beta;-\eta\right)-\frac{(-z)^{\beta}}{2}\cdot\sec(\pi\beta)\\\
&=-\frac{2N+\alpha}{2\beta}\sqrt{\frac{\eta}{1+\eta}}\cdot{{}_{2}F_{1}}\left(1,\frac{1}{2};1+\beta;\frac{1}{1+\eta}\right).\\\
\end{split}$

Consequently, by (3.1), the monic orthogonal polynomials can be obtained as
follows:

$P_{N}(z)\simeq\frac{(-1)^{N}}{2^{\alpha+1}}\cdot\left(\frac{b}{4}\right)^{N}\cdot\left(\sqrt{\eta}+\sqrt{1+\eta}\right)^{2N+\alpha+1}\cdot\frac{\exp\left[-\frac{2N+\alpha}{2\beta}-\mathcal{I}(z)\right]}{\eta^{\frac{2\alpha+1}{4}}(1+\eta)^{\frac{1}{4}}}.$

Thus the orthonomal polynomials $\mathcal{P}_{N}(z)$ of Theorem 3.1 can be
obtained using the standard method, stated as the below Lemma. ∎

######  Lemma 3.1.

[11] The orthonomal polynomials $\mathcal{P}_{N}(z)$ with respect to the
weight $w(x)$, i.e.

$\int_{a}^{b}\left[\mathcal{P}_{N}(x)\right]^{2}w(x)dx=1,$

can be given by:

$\mathcal{P}_{N}(z)=\sqrt{\frac{2}{\pi(b-a)}}\exp\left[\frac{A}{2}\right]P_{N}(z),$

where

$A:=2\int_{a}^{b}\frac{v(x)dx}{2\pi\sqrt{(b-x)(x-a)}}-2N\log\left(\frac{b-a}{4}\right),$

and the orthogonal polynomials $P_{N}(z)$ is approximated by (3.1).

######  Remark 3.1.

Apparently, the first representation in (3.2) is more convenient for
sufficiently large $N$, where $|\eta|\ll 1$. However, it cannot be used for
$\beta=N+\frac{1}{2},~{}N=1,2,\ldots$ by the nature of the Hypergeometric
function, that is why the second expression in (3.2) is needed.

To make further progress, we will be continuing to simplify the representation
of $\mathcal{P}_{N}(z)$. Using the inverse hyperbolic sine and the formula in
[18] (cf. 9.121. 26), the following identity holds

$\log\left(\sqrt{\eta}+\sqrt{\eta+1}\right)={\rm
arcsinh}\sqrt{\eta}=\sqrt{\eta}\cdot{{}_{2}F_{1}}\left(\frac{1}{2},\frac{1}{2};\frac{3}{2};-\eta\right).$
(3.4)

According to this, if we denote $E[\beta-\frac{1}{2}]$111 Throughout this
paper, $E[x]$ denotes the integer part of $x$. by $E_{\beta}$, we have

######  Lemma 3.2.

The asymptotic expression of the polynomials for $z\notin[0,\infty)$,
$|\eta|\ll 1$, is,

$\begin{split}\mathcal{P}_{N}(z)\simeq\frac{(-1)^{N}\eta^{\frac{1}{4}}}{\sqrt{2\pi(-z)^{\alpha+1}}}\cdot\exp\left[-\mathcal{I}(z)+\frac{(-z)^{\beta}}{2\sqrt{\pi}C^{\beta}}\sum_{k=0}^{E_{\beta}}(-1)^{k}\cdot
a_{k}\cdot\eta^{k-\beta+\frac{1}{2}}\right],\end{split}$ (3.5)

where $\mathcal{I}(z)$ is given in (3.2) and $a_{k}$ is defined as

$a_{k}:=\frac{\Gamma\left(k+\frac{1}{2}\right)}{\left(k+\frac{1}{2}\right)\Gamma\left(k+1\right)}.$
(3.6)

###### Proof.

By (3.4), we find

$\begin{split}\left(2N+\alpha+1\right)&\log\left(\sqrt{\eta}+\sqrt{1+\eta}\right)\simeq\left(2N+\alpha\right)\sqrt{\eta}\cdot{{}_{2}F_{1}}\left(\frac{1}{2},\frac{1}{2};\frac{3}{2};-\eta\right)\\\
&=\frac{(-z)^{\beta}}{\eta^{\beta}}\frac{1}{C^{\beta}}\sqrt{\eta}\cdot\sum_{k=0}^{\infty}\frac{\left(\frac{1}{2}\right)_{k}\left(\frac{1}{2}\right)_{k}}{\left(\frac{3}{2}\right)_{k}k!}(-\eta)^{k}\\\
&\simeq\frac{(-z)^{\beta}}{2\sqrt{\pi}C^{\beta}}\sum_{k=0}^{E_{\beta}}(-1)^{k}\cdot\frac{\Gamma\left(k+\frac{1}{2}\right)}{\left(k+\frac{1}{2}\right)\Gamma\left(k+1\right)}\cdot\eta^{k-\beta+\frac{1}{2}},\end{split}$

where, the Pochhammer symbol (also called the shifted factorial) reads

$(x)_{k}:=\frac{\Gamma\left(k+x\right)}{\Gamma(x)}=x(x+1)\cdots(x+k-1).$

Hence the Lemma 3.2 is obtained immediately. ∎

In sections 4 and 5, we will follow the techniques of [26] and [12] to show
that using an appropriate selection of vectors $\left\\{\xi_{m}\right\\}$,
that the lower bound given by (2.6) is actually an asymptotic estimate of
$\lambda_{N}$ for sufficiently large $N$. Taking full advantage of the Laplace
method, we can obtain an estimation of $\sum_{n=0}^{N}\mathcal{K}_{nn}$.
Consequently, the asymptotic behavior of $\lambda_{N}$ follows.

As mentioned in the Remark 3.1, our problem will be discussed in two different
cases.

##  4 The approximation of $\lambda_{N}$ for $\beta\neq
n+\frac{1}{2},{n\in\\{1,2,3,\ldots\\}}$

To find the asymptotic estimate of $\sum_{n=0}^{N}\mathcal{K}_{nn}$ for
$\beta\neq n+\frac{1}{2},~{}n\in\\{1,2,3,\ldots\\}$, we will first deal with
the term $\mathcal{I}(z)$ in (3.5) by using the first form in equation (3.2).

######  Lemma 4.1.

For $\beta\neq n+\frac{1}{2},~{}n\in\\{1,2,3,\ldots\\}$, we have

$\begin{split}\mathcal{P}_{N}(z)&\simeq\frac{(-1)^{N}}{\sqrt{2\pi(-z)^{\alpha+\frac{1}{2}}}}\cdot\left[C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right]^{-\frac{1}{4}}\cdot\exp\left[\frac{(-z)^{\beta}}{2}\sec\pi\beta\right]\\\
&~{}~{}~{}~{}\cdot\exp\left[\frac{\left(2N+\alpha\right)^{1-\frac{1}{2\beta}}}{2\sqrt{\pi
C}}\sum_{k=0}^{E_{\beta}}(-1)^{k}A_{k}\frac{(-z)^{k+\frac{1}{2}}}{\left(C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right)^{k}}\right],\end{split}$
(4.1)

here

$A_{k}:=a_{k}+\frac{\Gamma\left(\frac{1}{2}-\beta\right)}{2\Gamma(1-\beta)}b_{k}~{}~{}~{}{\rm
with}~{}~{}~{}b_{k}:=\sum_{j=0}^{k}\frac{\Gamma\left(j-\frac{1}{2}\right)\Gamma\left(k-j+1-\beta\right)}{\Gamma\left(j+1\right)\Gamma\left(k-j+\frac{3}{2}-\beta\right)},$

where $a_{k}$ is same as that given in (3.6).

Specially,

$A_{0}=\frac{4\sqrt{\pi}\beta}{2\beta-1}.$ (4.2)

###### Proof.

For $|\eta|<1$, the hypergeometric function
${{}_{2}F_{1}}\left(1,1-\beta;\frac{3}{2}-\beta;-\eta\right)$ has the below
series expansion

${{}_{2}F_{1}}\left(1,1-\beta;\frac{3}{2}-\beta;-\eta\right)=\frac{\Gamma\left(\frac{3}{2}-\beta\right)}{\Gamma\left(1-\beta\right)}\sum_{k=0}^{\infty}(-1)^{k}\frac{\Gamma\left(k+1-\beta\right)}{\Gamma\left(k+\frac{3}{2}-\beta\right)}\eta^{k}.$

Applying the formula ([18], p1015)

${{}_{2}F_{1}}\left(-n,\beta;\beta;-z\right)=(1+z)^{n},$

then for $|\eta|<1$, $\sqrt{1+\eta}$ may be written as

$\sqrt{1+\eta}=\frac{1}{\Gamma\left(-\frac{1}{2}\right)}\sum_{k=0}^{\infty}(-1)^{k}\frac{\Gamma\left(k-\frac{1}{2}\right)}{\Gamma\left(k+1\right)}\eta^{k}.$
(4.3)

So as $\eta\rightarrow 0$, the expansion for $\mathcal{I}(z)$ is

$\begin{split}&\mathcal{I}(z)\simeq-\frac{1}{4\sqrt{\pi}}\left(\frac{-z}{C}\right)^{\beta}\frac{\Gamma\left(\frac{1}{2}-\beta\right)}{\Gamma(1-\beta)}\sum_{k=0}^{E_{\beta}}(-1)^{k}b_{k}\cdot\eta^{k-\beta+\frac{1}{2}}-\frac{(-z)^{\beta}}{2}\sec\pi\beta,\\\
\end{split}$ (4.4)

where

$b_{k}:=\sum_{j=0}^{k}\frac{\Gamma\left(j-\frac{1}{2}\right)\Gamma\left(k-j+1-\beta\right)}{\Gamma\left(j+1\right)\Gamma\left(k-j+\frac{3}{2}-\beta\right)}.$

Substituting (4.4) into (3.5), and bear in mind
$\eta=-zC^{-1}(2N+\alpha)^{-\frac{1}{\beta}}$, then the Lemma 4.1 follows. ∎

######  Remark 4.1.

Letting $\alpha=0,~{}\beta=1$, we find $C=2$ and $A_{0}=4\sqrt{\pi}$.
Consequently, the classical result for Laguerre polynomials due to Perron [27]
is recovered,

$\mathcal{P}_{N}(z)\simeq\frac{(-1)^{N}}{2\sqrt{\pi}}\left(-zN\right)^{-\frac{1}{4}}\exp\left[\frac{z}{2}+2\sqrt{-zN}\right],~{}~{}z\notin[0,\infty).$

######  Remark 4.2.

The Laplace method [3] gives,

$\int_{a}^{b}f(t){\rm e}^{-\lambda g(t)}dt\simeq{\rm e}^{-\lambda
g(c)}f(c)\sqrt{\frac{2\pi}{\lambda g^{\prime\prime}(c)}}~{},~{}~{}~{}~{}{\rm
as}~{}~{}\lambda\rightarrow\infty,$

where $g$ assumes a strict minimum over $[a,b]$ at an interior critical point
$c$, such that

$\begin{split}g^{\prime}(c)=0,~{}~{}~{}~{}~{}g^{\prime\prime}(c)>0~{}~{}~{}~{}~{}{\rm
and}~{}~{}~{}~{}~{}f(c)\neq 0.\\\ \end{split}$

An alternative expression for Laplace method may be stated as:

If for $x\in[a,b]$, the real continuous function $g(x)$ has as its maximum the
value $g(b)$, then as $N\rightarrow\infty$

$\int_{a}^{b}f(x){\rm e}^{Ng(x)}dx\simeq\frac{f(b){\rm
e}^{Ng(b)}}{Ng^{\prime}(b)}.$ (4.5)

######  Theorem 4.1.

For $\beta\neq n+\frac{1}{2},~{}n\in\\{1,2,3,\ldots\\}$, the smallest
eigenvalue $\lambda_{N}$ of the $\mathcal{H}_{N}$ can be approximated by

$\begin{split}&\lambda_{N}\simeq\\\
&2^{\frac{5}{2}}\pi^{\frac{5}{4}}C^{-\frac{1}{4}}A_{0}^{\frac{1}{2}}\left(2N+\alpha\right)^{\frac{1}{2}-\frac{1}{4\beta}}\exp\left[-\sec\pi\beta-\frac{\left(2N+\alpha\right)^{1-\frac{1}{2\beta}}}{\sqrt{\pi
C}}\sum_{k=0}^{E_{\beta}}(-1)^{k}\frac{A_{k}}{C^{k}}\left(2N+\alpha\right)^{-\frac{k}{\beta}}\right],\end{split}$
(4.6)

where

$C:=4\left[\frac{\Gamma(\beta+1)\Gamma(\beta)}{\Gamma(2\beta+1)}\right]^{\frac{1}{\beta}},~{}~{}A_{k}:=a_{k}+\frac{\Gamma\left(\frac{1}{2}-\beta\right)}{2\Gamma(1-\beta)}b_{k},~{}~{}~{}\beta>\frac{1}{2},$

with

$a_{k}:=\frac{\Gamma\left(k+\frac{1}{2}\right)}{\left(k+\frac{1}{2}\right)\Gamma\left(k+1\right)},~{}~{}~{}~{}b_{k}:=\sum_{j=0}^{k}\frac{\Gamma\left(j-\frac{1}{2}\right)\Gamma\left(k-j+1-\beta\right)}{\Gamma\left(j+1\right)\Gamma\left(k-j+\frac{3}{2}-\beta\right)}~{}.$

###### Proof.

Note that $A_{0}>0$ for $\beta>\frac{1}{2}$ by (4.2), so the essential
contribution to $\mathcal{K}_{\mu\nu}$ comes from a small neighborhood of
$z=-1$ as $\mu\rightarrow\infty$ and $\nu\rightarrow\infty$. Let $\omega>0$ be
a fixed number and restrict the values of $\mu$ and $\nu$ to satisfy

$N-\omega N^{\frac{1}{2\beta}}\leq\mu,\nu\leq N,~{}~{}N\rightarrow\infty,$
(4.7)

thus we have

$\mathcal{K}_{\mu\nu}\simeq\int_{-\varepsilon}^{\varepsilon}\mathcal{P}_{\mu}\left(-{\rm
e}^{{\rm i}\theta}\right)\mathcal{P}_{\nu}\left(-{\rm e}^{-{\rm
i}\theta}\right)d\theta.$ (4.8)

Expanding the integrand for $|\theta|\ll 1$, we obtain

$\begin{split}\mathcal{K}_{\mu\nu}\simeq&\frac{(-1)^{\mu+\nu}{\rm
e}^{\sec\pi\beta}}{2\pi\sqrt{C}}\cdot\left(2N+\alpha\right)^{-\frac{1}{2\beta}}\cdot\int_{-\varepsilon}^{\varepsilon}\exp{\Bigg{[}}\frac{1}{2\sqrt{\pi
C}}\sum_{k=0}^{E_{\beta}}(-1)^{k}\frac{A_{k}}{C^{k}}\\\
&\cdot\left(1-\frac{(2k+1)^{2}\theta^{2}}{8}\right)\cdot\left((2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}+(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}\right)\\\
&+\frac{(2k+1){\rm
i}\theta}{2}\left((2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}-(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}\right){\Bigg{]}}d\theta.\end{split}$
(4.9)

Note that
$(2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}-(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}$
remains bounded because of restricting $\mu$ and $\nu$ as in (4.7), so we can
get rid of the linear term in (4.9) for $\theta\ll 1$. As mentioned above,
contributions to the integral (4.9) from $(-\infty,\varepsilon)$ and
$(\varepsilon,\infty)$ are small enough compared with those from
$[-\varepsilon,\varepsilon]$ as $\mu\rightarrow\infty$ and
$\nu\rightarrow\infty$. Therefore, we can extend the integration interval to
$\mathbb{R}$ but without affecting the approximation of
$\mathcal{K}_{\mu\nu}$. Using the Laplace method given by Remark 4.2, we
obtain

$\begin{split}\mathcal{K}_{\mu\nu}\simeq&\frac{(-1)^{\mu+\nu}}{(\pi
C)^{\frac{1}{4}}}\sqrt{\frac{2}{A_{0}}}\left(2N+\alpha\right)^{-\frac{1}{2}-\frac{1}{4\beta}}{\rm
e}^{\sec\pi\beta}\\\ &\cdot\exp\left[\frac{1}{2\sqrt{\pi
C}}\sum_{k=0}^{E_{\beta}}(-1)^{k}\frac{A_{k}}{C^{k}}\left((2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}+(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}\right)\right].\end{split}$
(4.10)

Observing (4.10), we can find that when $\mu$ and $\nu$ satisfied (4.7) and
large enough,

$\mathcal{K}_{\mu\nu}\simeq(-1)^{\mu+\nu}\mathcal{K}_{\mu\mu}^{\frac{1}{2}}\mathcal{K}_{\nu\nu}^{\frac{1}{2}}.$
(4.11)

Using the approach of [26] and [12] with the following choices of
$\left\\{\xi_{\nu}\right\\}$, allows us to determine the asymptotic behavior
of $\lambda_{N}$ for large $N$,

$\xi_{\nu}=\begin{cases}(-1)^{\nu}\sigma\mathcal{K}_{\nu\nu}^{\frac{1}{2}},~{}{\rm
if}~{}N_{0}\leq\nu\leq N,\ \ \\\ \\\ 0,\ \
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm if}~{}\nu<N_{0}:=E\left[N-\omega
N^{\frac{1}{2\beta}}\right],\end{cases}$

and the positive number $\sigma$ is determined by the condition

$\sum_{\nu=0}^{N}|\xi_{\nu}|^{2}=\sigma^{2}\sum_{\nu=N_{0}}^{N}\mathcal{K}_{\nu\nu}=1.$
(4.12)

It follows from (4.11) and (4.12) that

$\begin{split}\sum_{\mu,\nu=0}^{N}\mathcal{K}_{\mu\nu}\xi_{\mu}\overline{\xi}_{\nu}=\sum_{\mu,\nu=N_{0}}^{N}(-1)^{\mu+\nu}\sigma^{2}\mathcal{K}_{\mu\nu}\mathcal{K}_{\mu\mu}^{\frac{1}{2}}\mathcal{K}_{\nu\nu}^{\frac{1}{2}}\simeq\sigma^{2}\left(\sum_{\nu=N_{0}}^{N}\mathcal{K}_{\nu\nu}\right)^{2}=\sum_{\nu=N_{0}}^{N}\mathcal{K}_{\nu\nu}.\end{split}$
(4.13)

This means the minimum value in equation (2.5) can be approximated by (2.6),
following (4.13), because of the arbitrariness of $\omega$, i.e.

$\lambda_{N}\simeq\frac{2\pi}{\sum_{\nu=0}^{N}\mathcal{K}_{\nu\nu}}.$

It follows that

$\lambda_{N}\simeq\frac{2\pi}{\int_{0}^{N}\mathcal{K}_{\nu\nu}d\nu}.$ (4.14)

Substituting (4.10) into (4.14), with a simple calculation by applying the
Laplace method, see Remark 4.2, then the asymptotic behavior of $\lambda_{N}$,
for $\beta\neq n+\frac{1}{2},n\in\\{1,2,3,\ldots\\}$, is obtained. ∎

######  Example 4.1.

If we take $\alpha=-\frac{1}{2}$, $\beta=\frac{7}{4}$, then

$\lambda_{N}\simeq
2^{\frac{5}{2}}\pi^{\frac{5}{4}}C^{-\frac{1}{4}}A_{0}^{\frac{1}{2}}\left(2N-\frac{1}{2}\right)^{\frac{5}{14}}\exp\left[-\sqrt{2}-\frac{\left(2N-\frac{1}{2}\right)^{\frac{5}{7}}}{\sqrt{\pi
C}}\left(A_{0}-\frac{A_{1}}{C}\left(2N-\frac{1}{2}\right)^{-\frac{4}{7}}\right)\right],$

where
$C=4\left[\frac{\Gamma\left(\frac{11}{4}\right)\Gamma\left(\frac{7}{4}\right)}{\Gamma\left(\frac{9}{2}\right)}\right]^{\frac{4}{7}}$,
$A_{0}=\frac{14\sqrt{\pi}}{5}$ and $A_{1}=\frac{7\sqrt{\pi}}{3}$.

######  Corollary 4.1.

For the classical Laguerre weight $x^{\alpha}{\rm e}^{-x},~{}x\in[0,\infty),$
$\alpha>-1$, i.e. taking $\beta=1$ for our weight $w(x)$, we have

$\lambda_{N}\simeq 2^{\frac{13}{4}}\pi^{\frac{3}{2}}{\rm
e}\left(2N+\alpha\right)^{\frac{1}{4}}\exp\left[-2^{\frac{3}{2}}\left(2N+\alpha\right)^{\frac{1}{2}}\right].$

######  Remark 4.3.

When $\alpha=0,~{}\beta=1$, Szegö’s [26]¶¶¶The original formula of
$\lambda_{N}$ in the last equation on page 461 missed a factor of 4. classical
result for the Laguerre weight ${\rm e}^{-x}$ is recovered:

$\begin{split}&\lambda_{N}\simeq 2^{\frac{7}{2}}\pi^{\frac{3}{2}}{\rm
e}N^{\frac{1}{4}}\exp\left[-4N^{\frac{1}{2}}\right].\end{split}$

######  Remark 4.4.

With the restriction of $\alpha=0,\beta\neq
n+\frac{1}{2},n\in\\{1,2,3,\ldots\\}$, Chen and Lawrence’s result on the
weight ${\rm e}^{-x^{\beta}},~{}x\in[0,\infty)$ is also recovered:

$\lambda_{N}\simeq
8\pi^{\frac{5}{4}}\widetilde{C}^{-\frac{1}{4}}\widetilde{A}_{0}^{\frac{1}{2}}N^{\frac{1}{2}-\frac{1}{4\beta}}\exp\left[-\sec\pi\beta-\frac{N^{1-\frac{1}{2\beta}}}{\sqrt{\pi\widetilde{C}}}\sum_{r=0}^{E_{\beta}}(-1)^{r}\frac{\widetilde{A}_{r}}{\widetilde{C}^{r}}N^{-\frac{r}{\beta}}\right],$

for details of $\widetilde{A}_{0},\widetilde{A}_{r},\widetilde{C}$, please see
[12].

From (4.6) we find that $\lambda_{N}$ is exponentially small for large $N$ and
tends to $0$ as $N\rightarrow\infty$.

##  5  The approximation of $\lambda_{N}$ for
$\beta=n+\frac{1}{2},{n\in\\{1,2,3,\ldots\\}}$

Our goal for this section is to find the approximation of $\lambda_{N}$ for
the cases where $\beta=n+\frac{1}{2},n\in\\{1,2,3,\ldots\\}$. Such cases, as
was illustrated in Remark 3.1, require the second representation of
$\mathcal{I}(z)$ in (3.2). Before obtaining the asmptotic behavior of
$\lambda_{N}$, we first establish the following lemma for $\mathcal{P}(z)$.

######  Lemma 5.1.

For $|\eta|\ll 1$, then as $N\rightarrow\infty$,

$\mathcal{I}(z)\simeq\frac{(-1)^{\beta+\frac{1}{2}}(-z)^{\beta}}{2\pi}\log\left[\frac{4}{\eta}\right]+\frac{(-z)^{\beta}}{4\pi^{\frac{3}{2}}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\delta_{\beta-\frac{1}{2}-k}\eta^{k-\beta+\frac{1}{2}}$

where

$L_{k}:=\frac{k}{\pi}C^{k}(k),~{}~{}~{}{\rm
and}~{}~{}~{}\delta_{k}:=\sum_{j=1}^{\beta-\frac{1}{2}}\frac{\gamma_{j-k}}{L_{j-\frac{1}{2}}},$

with

$\gamma_{k}:=\begin{cases}\frac{\Gamma\left(k-\frac{1}{2}\right)}{\Gamma(k+1)},~{}{\rm
if}~{}~{}k\geq 0,\\\ \\\ 0,\ \ ~{}~{}~{}~{}~{}~{}{\rm
if}~{}~{}k<0.\end{cases}$

###### Proof.

Based on the Gauss’ recursion relation [18], see (7.5) in the Appendix, Chen
and Lawrence [12] built the following version formula:

$\begin{split}{{}_{2}F_{1}}\left(1,\frac{1}{2};n+\frac{5}{2};z\right)&=\frac{\left(n+\frac{3}{2}\right)(z-1)}{(n+1)z}\left[{{}_{2}F_{1}}\left(1,\frac{1}{2};n+\frac{3}{2};z\right)-{{}_{2}F_{1}}\left(1,\frac{1}{2};n+\frac{1}{2};z\right)\right]\\\
&+\frac{n\left(n+\frac{3}{2}\right)}{(n+1)\left(n+\frac{1}{2}\right)}{{}_{2}F_{1}}\left(1,\frac{1}{2};n+\frac{3}{2};z\right),\end{split}$

together with the fact that

${{}_{2}F_{1}}\left(1,\frac{1}{2};\frac{5}{2};z\right)=\frac{3}{4}\frac{(z-1)}{z^{\frac{3}{2}}}\log\left[\frac{1+\sqrt{z}}{1-\sqrt{z}}\right]+\frac{3}{2}z,$

we can get

${{}_{2}F_{1}\left(1,\frac{1}{2};\beta+1;z\right)}=L_{\beta}\frac{(z-1)^{\beta-\frac{1}{2}}}{z^{\beta+\frac{1}{2}}}\left(\sqrt{z}\log\left[\frac{1+\sqrt{z}}{1-\sqrt{z}}\right]+\sum_{k=1}^{\beta-\frac{1}{2}}\frac{1}{L_{k-\frac{1}{2}}}\left(\frac{z}{z-1}\right)^{k}\right),$

where $\beta=n+\frac{1}{2},n=1,2,3,\ldots$ and $L_{k}$ is given by

$L_{k}:=\frac{k}{\pi}C^{k}(k).$

Consequently, we have

$\mathcal{I}(z)=\frac{(-1)^{\beta+\frac{1}{2}}}{2\pi}(-z)^{\beta}\left(\log\left[\frac{\sqrt{1+\eta}+1}{\sqrt{1+\eta}-1}\right]+\sqrt{1+\eta}\sum_{k=1}^{\beta-\frac{1}{2}}(-1)^{k}\frac{\eta^{-k}}{L_{k-\frac{1}{2}}}\right).$

By using (4.3) again, we find

$\begin{split}\mathcal{I}(z)&\simeq\frac{(-1)^{\beta+\frac{1}{2}}(-z)^{\beta}}{2\pi}\log\left[\frac{4}{\eta}\right]+\frac{(-1)^{\beta-\frac{1}{2}}(-z)^{\beta}}{4\pi^{\frac{3}{2}}}\left[\sum_{j=1}^{\beta-\frac{1}{2}}\frac{(-1)^{j}\eta^{-j}}{L_{j-\frac{1}{2}}}\right]\\\
&\cdot\left[\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k+j-\left(\beta-\frac{1}{2}\right)}\frac{\Gamma\left(k+j-\left(\beta-\frac{1}{2}\right)-\frac{1}{2}\right)}{\Gamma\left(k+j-\left(\beta-\frac{1}{2}\right)+1\right)}\eta^{k+j-\left(\beta-\frac{1}{2}\right)}\right]\\\
&=\frac{(-1)^{\beta+\frac{1}{2}}(-z)^{\beta}}{2\pi}\log\left[\frac{4}{\eta}\right]+\left[\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\sum_{j=1}^{\beta-\frac{1}{2}}\frac{\frac{\Gamma\left(k+j-\left(\beta-\frac{1}{2}\right)-\frac{1}{2}\right)}{\Gamma\left(k+j-\left(\beta-\frac{1}{2}\right)+1\right)}}{L_{j-\frac{1}{2}}}\eta^{k+\frac{1}{2}-\beta}\right].\\\
\end{split}$

With an easy simplification, the Lemma is obtained immediately. ∎

Substituting $\eta=-zC^{-1}(2N+\alpha)^{-\frac{1}{\beta}}$, together with a
simple calculation gives the following strong asymptotics of
$\mathcal{P}_{N}(z)$ for $z\notin[0,\infty)$,

######  Lemma 5.2.

For $z\notin[0,\infty)$, we have

$\begin{split}\mathcal{P}_{N}(z)&\simeq\frac{(-1)^{N}}{\sqrt{2\pi}}(-z)^{-\frac{\alpha}{2}-\frac{1}{4}}\left(C(2N+\alpha)^{\frac{1}{\beta}}\right)^{-\frac{1}{4}}\exp\left[\frac{(-1)^{\beta-\frac{1}{2}}(-z)^{\beta}}{2\pi}\log\left(\frac{4C(2N+\alpha)^{\frac{1}{\beta}}}{-z}\right)\right]\\\
&\cdot\exp\left[\frac{(2N+\alpha)^{1-\frac{1}{2\beta}}}{2\sqrt{\pi
C}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}B_{k}\frac{(-z)^{k+\frac{1}{2}}}{\left(C(2N+\alpha)^{\frac{1}{\beta}}\right)^{k}}\right],\\\
\end{split}$

where

$B_{k}:=a_{k}-\frac{L_{\beta}}{2\beta}\delta_{\beta-\frac{1}{2}-k},$

In particularly,

$B_{0}=\frac{4\sqrt{\pi}\beta}{2\beta-1}.$

######  Theorem 5.1.

For $\lambda_{N}$, we have

$\begin{split}\lambda_{N}\simeq&~{}2^{\frac{5}{2}}\pi^{\frac{5}{4}}C^{-\frac{1}{4}}B_{0}^{\frac{1}{2}}\left(2N+\alpha\right)^{\frac{1}{2}-\frac{1}{4\beta}}\left(4C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right)^{\frac{(-1)^{\beta+\frac{1}{2}}}{\pi}}\\\
&\cdot\exp\left[-\frac{(2N+\alpha)^{1-\frac{1}{2\beta}}}{\sqrt{\pi
C}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\frac{B_{k}}{C^{k}}\left(2N+\alpha\right)^{-\frac{k}{\beta}}\right].\end{split}$
(5.1)

###### Proof.

Since $B_{0}>0$ and by an argument like that in the Section 4, again we find
that the dominant contribution to $\mathcal{K}_{\mu\nu}$ is from the arc of
the unit circle around $z=-1$. Restricting $\mu,~{}\nu$ to the same range
given by (4.7), then
$(2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}-(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}$
and $\log\left[(2\mu+\alpha)/(2\nu+\alpha)\right]$ remain bounded and (4.8)
will also be true at here. By the Laplace method, we have

$\mathcal{K}_{\mu\nu}\simeq\int_{-\infty}^{\infty}\mathcal{P}_{\mu}\left(-{\rm
e}^{{\rm i}\theta}\right)\mathcal{P}_{\nu}\left(-{\rm e}^{-{\rm
i}\theta}\right)d\theta.$ (5.2)

As previously, we expand the exponential in the integrand for $|\theta|\ll 1$,
reserving terms up to the second order. We obtain

$\begin{split}\mathcal{K}_{\mu\nu}&\simeq\frac{(-1)^{\mu+\nu}}{(\pi
C)^{\frac{1}{4}}}\sqrt{\frac{2}{B_{0}}}\left(2N+\alpha\right)^{-\frac{1}{2}-\frac{1}{4\beta}}\left(4C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right)^{\frac{(-1)^{\beta-\frac{1}{2}}}{\pi}}\\\
&\cdot\exp\left[\frac{1}{2\sqrt{\pi
C}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\frac{B_{k}}{C^{k}}\left((2\mu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}+(2\nu+\alpha)^{1-\frac{1}{2\beta}-\frac{k}{\beta}}\right)\right],\end{split}$

For large enough $\mu$ and $\nu$, restricted by (4.7), again we will have

$\mathcal{K}_{\mu\nu}\simeq(-1)^{\mu+\nu}\mathcal{K}_{\mu\mu}^{\frac{1}{2}}\mathcal{K}_{\nu\nu}^{\frac{1}{2}}.$

As per the discussion in the previous section, it follows that

$\lambda_{N}\simeq\frac{2\pi}{\int_{0}^{N}\mathcal{K}_{\nu\nu}d\nu}.$

Taking an application of the Laplace method and doing the same argument as
before, we get the asymptotic behavior for the integration,

$\begin{split}\int_{0}^{N}\mathcal{K}_{\nu\nu}d\nu\simeq&~{}2^{-\frac{3}{2}}\pi^{-\frac{1}{4}}C^{\frac{1}{4}}B_{0}^{-\frac{1}{2}}\left(2N+\alpha\right)^{-\frac{1}{2}+\frac{1}{4\beta}}\left(4C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right)^{\frac{(-1)^{\beta-\frac{1}{2}}}{\pi}}\\\
&\cdot\exp\left[\frac{(2N+\alpha)^{1-\frac{1}{2\beta}}}{\sqrt{\pi
C}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\frac{B_{k}}{C^{k}}\left(2N+\alpha\right)^{-\frac{k}{\beta}}\right],\end{split}$
(5.3)

which completes the proof of this theorem. ∎

######  Example 5.1.

If we take $\alpha=-\frac{3}{4}$, $\beta=\frac{3}{2}$, then

$\lambda_{N}\simeq
2^{\frac{5}{2}+\frac{2}{\pi}}\pi^{\frac{5}{4}}C^{\frac{1}{\pi}-\frac{1}{4}}B_{0}^{\frac{1}{2}}\left(2N-\frac{3}{4}\right)^{\frac{1}{3}+\frac{2}{3\pi}}\exp\left[-\frac{\left(2N-\frac{3}{4}\right)^{\frac{2}{3}}}{\sqrt{\pi
C}}\left(B_{0}-\frac{B_{1}}{C}\left(2N-\frac{3}{4}\right)^{-\frac{2}{3}}\right)\right]$

where $C=\left(\frac{\pi}{2}\right)^{\frac{2}{3}}$, $B_{0}=3\sqrt{\pi}$ and
$B_{1}=-\frac{\sqrt{\pi}}{6}$.

######  Remark 5.1.

Putting $\alpha=0$, Chen and Lawrence’s result for
$\beta=n+\frac{1}{2},n=1,2,3,\ldots$ is recovered.

$\begin{split}\lambda_{N}\simeq
8\pi^{\frac{1}{4}}\widetilde{C}^{-\frac{1}{4}}\widetilde{B}_{0}^{\frac{1}{2}}N^{\frac{1}{2}-\frac{1}{4\beta}}\left(4\widetilde{C}N^{\frac{1}{\beta}}\right)^{\frac{(-1)^{\beta+\frac{1}{2}}}{\pi}}\exp\left[-\frac{2N^{1-\frac{1}{2\beta}}}{\sqrt{\pi\widetilde{C}}}\sum_{k=0}^{\beta-\frac{1}{2}}(-1)^{k}\frac{\widetilde{B}_{k}}{\widetilde{C}^{k}}N^{-\frac{k}{\beta}}\right],\end{split}$

where

$\widetilde{C}=2^{-\frac{1}{\beta}}C~{}~{}~{}{\rm
and}~{}~{}~{}\widetilde{B}_{k}=B_{k}.$

Comparing (4.6) with (5.1), we note that the essential difference between them
is the term $\exp(-\sec\pi\beta)$ becomes
$\left[4C\left(2N+\alpha\right)^{\frac{1}{\beta}}\right]^{\frac{(-1)^{\beta+\frac{1}{2}}}{\pi}}$.
The alternating behavior of the second term depends on whether
$\beta+\frac{1}{2}$ is even or odd. Anyway, $\lambda_{N}\rightarrow 0$ as
$N\rightarrow\infty$.

On the basis of the standard theory [1], the moment problem with respect to
$w(x),~{}x\in[0,\infty)$ is indeterminate if

$\int_{0}^{\infty}\frac{\log w(x)}{\sqrt{x}(1+x)}dx>-\infty.$

For our weight $w(x)=x^{\alpha}{\rm e}^{-x^{\beta}},x\in[0,\infty)$,

$\int_{0}^{\infty}\frac{-\alpha\log
x+x^{\beta}}{\sqrt{x}(1+x)}dx=\int_{0}^{\infty}\frac{x^{\beta}}{\sqrt{x}(1+x)}dx=\pi\sec\left(\pi\beta\right),$

Therefore, $\beta=\frac{1}{2}$ is the critical point at which the moment
problem becomes indeterminate. If we assume the approximation of
$\mathcal{P}_{N}(z)$ given in (3.5) holds, we see that

$\mathcal{P}_{N}(z)\simeq\frac{(-1)^{N}}{\sqrt{2}\pi}(-z)^{-\frac{\alpha}{2}-\frac{1}{4}}\left(2N+\alpha\right)^{-\frac{1}{2}}\exp\left[\frac{\sqrt{-z}}{\pi}\left(\log\left[\frac{2\pi\left(2N+\alpha\right)}{\sqrt{-z}}\right]+1\right)\right].$
(5.4)

We assume that both $\mu$ and $\nu$ are large, however $\mu-\nu$ is bounded by
a constant, and thus the asymptotic expression holds. Again, we see that the
main contributions to $\mathcal{K}_{\mu\nu}$ come from the arc of the unit
circle around $z=-1$. However, for $|\eta|\ll 1$, it follows the behavior of
$\mathcal{P}_{N}$ given by (5.4):

$\begin{split}\mathcal{K}_{\mu\nu}&\simeq\int_{-\varepsilon}^{\varepsilon}\mathcal{P}_{\mu}(-{\rm
e}^{{\rm i}\theta})\mathcal{P}_{\nu}(-{\rm e}^{-{\rm i}\theta})d\theta\\\
&\simeq\frac{(-1)^{\mu+\nu}}{2\pi^{2}}{\rm e}^{\frac{2}{\pi}+\frac{2}{\pi}\log
2\pi}(2\mu+\alpha)^{-\frac{1}{2}+\frac{1}{\pi}}(2\nu+\alpha)^{-\frac{1}{2}+\frac{1}{\pi}}\\\
&~{}\cdot\int_{-\varepsilon}^{\varepsilon}\left[1+\frac{2-2\log
2\pi-\log(2\mu+\alpha)-\log(2\nu+\alpha)}{8\pi}\theta^{2}\right]d\theta.\end{split}$

Quite obviously, $|\mathcal{K}_{\mu\nu}|$ decreases as $\mu$ and $\nu$
increase, which invalidates the argument of the previous section. However, it
is possible to get an approximative lower bound for the smallest eigenvalue
using (2.6).

Using the Christoffel-Darboux formula ([19], Theorem 2.2.2), which reads:

$\sum_{j=0}^{N-1}\frac{P_{j}(x)P_{j}(y)}{h_{j}}=\frac{P_{N}(x)P_{N-1}(y)-P_{N}(y)P_{N-1}(x)}{h_{N-1}(x-y)},$

and is valid for monic orthogonal polynomials $\left\\{P_{n}(z)\right\\}$,
where $h_{j}$ is the square of the $L^{2}$ norm of $P_{N}(z)$, and the result
presented in [10] for large $N$ off-diagonal recurrence coefficients, we have

$\begin{split}\sum_{\nu=0}^{N}\mathcal{K}&{}_{\nu\nu}=\int_{-\pi}^{\pi}\sum_{\nu=0}^{N}\mathcal{P}_{\nu}\left(-{\rm
e}^{{\rm i}\theta}\right)\mathcal{P}_{\nu}\left(-{\rm e}^{-{\rm
i}\theta}\right)d\theta\\\
&\simeq\frac{\pi^{2}\left(2N+\alpha\right)^{2}}{4}\int_{-\pi}^{\pi}\frac{\mathcal{P}_{N}\left(-{\rm
e}^{{\rm i}\theta}\right)\mathcal{P}_{N+1}\left(-{\rm e}^{-{\rm
i}\theta}\right)-\mathcal{P}_{N}\left(-{\rm e}^{-{\rm
i}\theta}\right)\mathcal{P}_{N+1}\left(-{\rm e}^{{\rm i}\theta}\right)}{{\rm
e}^{{\rm i}\theta}-{\rm e}^{-{\rm i}\theta}}d\theta.\end{split}$

As a result, applying the Laplace method, gives

$\sum_{\nu=0}^{N}\mathcal{K}_{\nu\nu}\simeq\frac{\left[2\pi(2N+\alpha){\rm
e}\right]^{\frac{2}{\pi}}}{4\sqrt{\log\left[2\pi(2N+\alpha){\rm e}\right]}}.$

We found the smallest eigenvalue for $\beta=\frac{1}{2}$ decreases
algebraically rather than exponentially, since
$\lambda_{N}\simeq\frac{2\pi}{\sum_{\nu=0}^{N}\mathcal{K}_{\nu\nu}}$.

##  6 Numerical results

It is well known that Hankel matrices (moment matrices) of this form are
extremely ill-conditioned. This can be observed directly from the terms on the
main diagonal of $\mathcal{H}_{N}$ as follows. The condition number,
$\kappa(\mathcal{H}_{N})=\frac{\Lambda_{N}}{\lambda_{N}}$ where $\Lambda_{N}$
and $\lambda_{N}$ are the largest and smallest eigenvalues of
$\mathcal{H}_{N}$ respectively. By applying the Rayleigh quotient, we know
$\Lambda_{N}$ is greater than all elements on main diagonal and $\lambda_{N}$
is less than all elements on the main diagonal. Thus, for some constant $c>0$:

$\displaystyle\kappa(\mathcal{H}_{N})\geq\frac{\mu_{2N}}{\mu_{0}}=\frac{\Gamma(\frac{\alpha+1+2N}{\beta})}{\Gamma(\frac{\alpha+1}{\beta})}>c\
\Gamma\Big{(}\frac{2N}{\beta}\Big{)},~{}~{}~{}\text{if~{}~{}$\frac{2N}{\beta}\geq\frac{3}{2}$}.$

We note that the condition number is of order
$\Gamma\left(\frac{2N}{\beta}\right)$. Due to the ill-conditioned nature of
these matrices, standard eigensolver packages based double precision floating
values can solve only small instances, i.e. $N<20$, before they exhaust the
available precision (53 bit in the mantissa, 11 bits in the exponent).

In [17], Emmart, Chen and Weems developed an efficient parallel algorithm
based on arbitrary precision arithmetic and the Secant method that can handle
the extreme ill-conditioning and we employ their algorithms here for our
numerical computations. We use the numerical results to test the convergence
of our asymptotic formulas to the actual smallest eigenvalues for various $N$
and several values of the parameters $\alpha$ and $\beta$. Even with efficient
software, the computation times for the largest size, $N=1000$, require almost
10 hours of CPU time on a modern Core i7 processor.

Figure 1: The percentage error of the theoretical values of $\lambda_{N}$ vs. those obtained numerically, for various $\alpha$ and $\beta$.  Table 1: List of numerical results vs. theoretical values, for $\alpha=0,~{}\beta=\frac{1}{2}$. Size $N$ | Numerical $\lambda_{N}$ | Theoretical $\lambda_{N}$ | error
---|---|---|---
100 | $0.27397$ | $0.40360$ | $47.32\%$
300 | $0.15837$ | $0.21365$ | $34.91\%$
500 | $0.12047$ | $0.15855$ | $31.61\%$
1000 | $0.082087$ | $0.10555$ | $28.58\%$
1500 | $0.065295$ | $0.083130$ | $27.33\%$
2000 | $0.055431$ | $0.070108$ | $26.48\%$
2500 | $0.048788$ | $0.061430$ | $25.91\%$
3000 | $0.043940$ | $0.055135$ | $25.48\%$

######  Remark 6.1.

In Figure 1 and Tables 1-3,

$\%~{}error:=\left|\frac{{\rm Theoretical}~{}\lambda_{N}-~{}{\rm
Numerical}~{}\lambda_{N}}{{\rm Numerical}~{}\lambda_{N}}\times 100\right|.$
(6.1)

Table 2: List of numerical results vs. theoretical values, for $\beta\neq n+\frac{1}{2},n\in\mathbb{N}^{+}$ $\alpha$ | $\beta$ | Size $N$ | Numerical $\lambda_{N}$ | Theoretical $\lambda_{N}$ | error
---|---|---|---|---|---
$-\frac{1}{2}$ | $1$ | 100 | $2.2434\times 10^{-15}$ | $2.4171\times 10^{-15}$ | $0.07745$
|  | 200 | $1.7127\times 10^{-22}$ | $1.8059\times 10^{-22}$ | $0.05445$
|  | 300 | $5.7241\times 10^{-28}$ | $5.9779\times 10^{-28}$ | $0.04435$
|  | 400 | $1.3647\times 10^{-32}$ | $1.4170\times 10^{-32}$ | $0.03835$
|  | 500 | $1.1453\times 10^{-36}$ | $1.1845\times 10^{-36}$ | $0.03427$
|  | 600 | $2.3530\times 10^{-40}$ | $2.4265\times 10^{-40}$ | $0.03126$
|  | 700 | $9.5340\times 10^{-44}$ | $9.8098\times 10^{-44}$ | $0.02893$
|  | 800 | $6.6167\times 10^{-47}$ | $6.7956\times 10^{-47}$ | $0.02705$
|  | 900 | $7.1306\times 10^{-50}$ | $7.3123\times 10^{-50}$ | $0.02549$
|  | 1000 | $1.1110\times 10^{-52}$ | $1.1378\times 10^{-52}$ | $0.02417$
$1$ | $1$ | 100 | $2.0119\times 10^{-15}$ | $2.0845\times 10^{-15}$ | $0.03610$
|  | 200 | $1.5845\times 10^{-22}$ | $1.6258\times 10^{-22}$ | $0.02605$
|  | 300 | $5.3703\times 10^{-28}$ | $5.4855\times 10^{-28}$ | $0.02145$
|  | 400 | $1.2911\times 10^{-32}$ | $1.3153\times 10^{-32}$ | $0.01867$
|  | 500 | $1.0898\times 10^{-36}$ | $1.1081\times 10^{-36}$ | $0.01676$
|  | 600 | $2.2486\times 10^{-40}$ | $2.2831\times 10^{-40}$ | $0.01534$
|  | 700 | $9.1416\times 10^{-44}$ | $9.2716\times 10^{-44}$ | $0.01423$
|  | 800 | $6.3614\times 10^{-47}$ | $6.4462\times 10^{-47}$ | $0.01333$
|  | 900 | $6.8707\times 10^{-50}$ | $6.9572\times 10^{-50}$ | $0.01258$
|  | 1000 | $1.0725\times 10^{-52}$ | $1.0853\times 10^{-52}$ | $0.01195$
$-\frac{1}{2}$ | $\frac{7}{4}$ | 100 | $2.0753\times 10^{-45}$ | $2.1203\times 10^{-45}$ | $0.02168$
|  | 200 | $4.6281\times 10^{-76}$ | $4.7027\times 10^{-76}$ | $0.01613$
|  | 300 | $1.7181\times 10^{-102}$ | $1.7412\times 10^{-102}$ | $0.01344$
|  | 400 | $1.6945\times 10^{-126}$ | $1.7144\times 10^{-126}$ | $0.01177$
|  | 500 | $7.6149\times 10^{-149}$ | $7.6955\times 10^{-149}$ | $0.01059$
|  | 600 | $5.9500\times 10^{-170}$ | $6.0077\times 10^{-170}$ | $0.00970$
|  | 700 | $4.4336\times 10^{-190}$ | $4.4735\times 10^{-190}$ | $0.00899$
|  | 800 | $2.0973\times 10^{-209}$ | $2.1149\times 10^{-209}$ | $0.00842$
|  | 900 | $4.7024\times 10^{-228}$ | $4.7398\times 10^{-228}$ | $0.00794$
|  | 1000 | $4.0152\times 10^{-246}$ | $4.0455\times 10^{-246}$ | $0.00753$
$2$ | $2$ | 100 | $1.5626\times 10^{-54}$ | $1.3738\times 10^{-54}$ | $0.12082$
|  | 200 | $4.0862\times 10^{-93}$ | $3.7101\times 10^{-93}$ | $0.09204$
|  | 300 | $4.6575\times 10^{-127}$ | $4.2866\times 10^{-127}$ | $0.07964$
|  | 400 | $2.7728\times 10^{-158}$ | $2.5723\times 10^{-158}$ | $0.07230$
|  | 500 | $1.2618\times 10^{-187}$ | $1.1769\times 10^{-187}$ | $0.06729$
|  | 600 | $1.5155\times 10^{-215}$ | $1.4191\times 10^{-215}$ | $0.06358$
|  | 700 | $2.4610\times 10^{-242}$ | $2.3117\times 10^{-242}$ | $0.06067$
|  | 800 | $3.4223\times 10^{-268}$ | $3.2228\times 10^{-268}$ | $0.05831$
|  | 900 | $2.9306\times 10^{-293}$ | $2.7654\times 10^{-293}$ | $0.05635$
|  | 1000 | $1.2053\times 10^{-317}$ | $1.1394\times 10^{-317}$ | $0.05467$
Table 3: List of numerical results vs. theoretical values, for $\beta=n+\frac{1}{2},n\in\mathbb{N}^{+}$ $\alpha$ | $\beta$ | Size $N$ | Numerical $\lambda_{N}$ | Theoretical $\lambda_{N}$ | error
---|---|---|---|---|---
$-\frac{3}{4}$ | $\frac{3}{2}$ | 100 | $7.8618\times 10^{-36}$ | $8.1371\times 10^{-36}$ | $0.03502$
|  | 200 | $3.3759\times 10^{-58}$ | $3.4638\times 10^{-58}$ | $0.02605$
|  | 300 | $5.3913\times 10^{-77}$ | $5.5084\times 10^{-77}$ | $0.02172$
|  | 400 | $8.6803\times 10^{-94}$ | $8.8455\times 10^{-94}$ | $0.01902$
|  | 500 | $3.1289\times 10^{-109}$ | $3.1825\times 10^{-109}$ | $0.01713$
|  | 600 | $1.1225\times 10^{-123}$ | $1.1402\times 10^{-123}$ | $0.01571$
|  | 700 | $2.4313\times 10^{-137}$ | $2.4668\times 10^{-137}$ | $0.01459$
|  | 800 | $2.2724\times 10^{-150}$ | $2.3035\times 10^{-150}$ | $0.01368$
|  | 900 | $7.2147\times 10^{-163}$ | $7.3079\times 10^{-163}$ | $0.01292$
|  | 1000 | $6.5115\times 10^{-175}$ | $6.5914\times 10^{-175}$ | $0.01227$
$-\frac{1}{2}$ | $\frac{5}{2}$ | 100 | $1.7527\times 10^{-68}$ | $1.8456\times 10^{-68}$ | $0.05303$
|  | 200 | $1.6233\times 10^{-121}$ | $1.6918\times 10^{-121}$ | $0.04223$
|  | 300 | $1.9900\times 10^{-169}$ | $2.0635\times 10^{-169}$ | $0.03693$
|  | 400 | $2.8604\times 10^{-214}$ | $2.9564\times 10^{-214}$ | $0.03356$
|  | 500 | $5.9391\times 10^{-257}$ | $6.1240\times 10^{-257}$ | $0.03114$
|  | 600 | $5.5030\times 10^{-298}$ | $5.6642\times 10^{-298}$ | $0.02928$
|  | 700 | $1.0780\times 10^{-337}$ | $1.1080\times 10^{-337}$ | $0.02779$
|  | 800 | $2.6691\times 10^{-376}$ | $2.7400\times 10^{-376}$ | $0.02655$
|  | 900 | $5.7436\times 10^{-414}$ | $5.8901\times 10^{-414}$ | $0.02550$
|  | 1000 | $8.0870\times 10^{-451}$ | $8.2859\times 10^{-451}$ | $0.02460$
$2$ | $\frac{5}{2}$ | 100 | $3.5614\times 10^{-69}$ | $3.5767\times 10^{-69}$ | $0.00428$
|  | 200 | $3.9629\times 10^{-122}$ | $4.0207\times 10^{-122}$ | $0.01460$
|  | 300 | $5.3740\times 10^{-170}$ | $5.4660\times 10^{-170}$ | $0.01711$
|  | 400 | $8.2704\times 10^{-215}$ | $8.4184\times 10^{-215}$ | $0.01790$
|  | 500 | $1.8070\times 10^{-257}$ | $1.8397\times 10^{-257}$ | $0.01809$
|  | 600 | $1.7433\times 10^{-298}$ | $1.7748\times 10^{-298}$ | $0.01803$
|  | 700 | $3.5306\times 10^{-338}$ | $3.5937\times 10^{-338}$ | $0.01787$
|  | 800 | $8.9908\times 10^{-377}$ | $9.1495\times 10^{-337}$ | $0.01766$
|  | 900 | $1.9823\times 10^{-414}$ | $2.0168\times 10^{-414}$ | $0.01743$
|  | 1000 | $2.8512\times 10^{-451}$ | $2.9002\times 10^{-451}$ | $0.01719$
$0$ | $\frac{7}{2}$ | 100 | $7.0602\times 10^{-89}$ | $6.8217\times 10^{-89}$ | $0.03379$
|  | 200 | $9.5989\times 10^{-164}$ | $9.3315\times 10^{-164}$ | $0.02786$
|  | 300 | $1.5672\times 10^{-233}$ | $1.5286\times 10^{-233}$ | $0.02464$
|  | 400 | $3.4926\times 10^{-300}$ | $3.4140\times 10^{-300}$ | $0.02251$
|  | 500 | $1.3836\times 10^{-364}$ | $1.3546\times 10^{-364}$ | $0.02096$
|  | 600 | $3.0405\times 10^{-427}$ | $2.9804\times 10^{-427}$ | $0.01976$
|  | 700 | $1.7488\times 10^{-488}$ | $1.7160\times 10^{-488}$ | $0.01879$
|  | 800 | $1.5603\times 10^{-548}$ | $1.5322\times 10^{-548}$ | $0.01798$
|  | 900 | $1.4700\times 10^{-607}$ | $1.4446\times 10^{-607}$ | $0.01729$
|  | 1000 | $1.0901\times 10^{-665}$ | $1.0719\times 10^{-665}$ | $0.01669$

##  7 Appendix

The integral identities listed below, which are relevant to our derivation and
can be found in [14], [18] and [15].

$\int_{a}^{b}\frac{dx}{\sqrt{(b-x)(x-a)}}=\pi.$ (7.1)
$\int_{a}^{b}\frac{dx}{(x+t)\sqrt{(b-x)(x-a)}}=\frac{\pi}{\sqrt{(t+a)(t+b)}}.$
(7.2)
$\int_{a}^{b}\frac{\log(x+t)}{\sqrt{(b-x)(x-a)}}dx=2\pi\log\left(\frac{\sqrt{t+a}+\sqrt{t+b}}{2}\right).$
(7.3)
$\int_{a}^{b}\frac{\log(1-x)}{\sqrt{(b-x)(x-a)}(x+t)}dx=\pi\frac{\log\left(\frac{(t+1)^{2}-\left(\sqrt{(t+a)(t+b)}-\sqrt{(1-a)(1-b)}\right)^{2}}{\left(\sqrt{t+a}+\sqrt{t+b}\right)^{2}}\right)}{\sqrt{(t+a)(t+b)}}.$
(7.4)

Gauss’ recursion functions ([18], P1019, 9.1377, 1):

$\begin{split}&\gamma\left[\gamma-1-(2\gamma-\alpha-\beta-1)z\right]F(\alpha,\beta;\gamma;z)+(\gamma-\alpha)(\gamma-\beta)zF(\alpha,\beta;\gamma+1;z)\\\
&+\gamma(\gamma-1)(z-1)F(\alpha,\beta;\gamma-1;z)=0.\end{split}$ (7.5)

##  8 Acknowledgements

The financial support of the Macau Science and Technology Development Fund
under grant number FDCT 130/2014/A3 and FDCT 023/2017/A1 are gratefully
acknowledged. We would also like to thank the National Science Foundation
(NSF): CCF-1525754 and the University of Macau for generous support: MYRG
2014-00011 FST, MYRG 2014-00004 FST.

## References

  * [1] N. I. Akhiezer, _The classical moment problem and some related questions in analysis_ , English translation, Oliver and Boyd, Edinburgh, 1965.
  * [2] G. W. Anderson, A. Guionnet and O. Zeitouni, _An introduction to random matrices_ , The University Press, Cambridge, 2010.
  * [3] N. G. de Bruijn, _Asymptotic methods in analysis_. New York: Interscience, 1958.
  * [4] B. Beckermann, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math. 85 (2000), 553-557.
  * [5] C. Berg, Y. Chen and M. E. H. Ismail, Small eigenvalues of large Hankel matrices: The indeterminate case, Math. Scand., 91 (2002), 67-81.
  * [6] G. Blower, _Random Matrices: High dimensional phenomena_ , The University Press, Cambridge, 2009.
  * [7] Z. Bai, Y. Chen and Y. C. Liang, Random matrix theory and its applications, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, 2009.
  * [8] C. Berg and R. Szwarc, The smallest eigenvalue of Hankel matrices, Constructive Approximation, 34 (2011), 107-133.
  * [9] M. Chen and Y. Chen, Singular linear statistics of the Laguerre unitary ensemble and Painlevé. III. Double scaling analysis, J. Math. Phys. 56 (2015), 063506.
  * [10] Y. Chen and M. E. H. Ismail, Thermodynamic relations the Hermitian matrix ensembles. J. Phys. A: Math. Gen. 30 (1997), 6633-6654.
  * [11] Y. Chen and N. Lawrence, On the linear statistics of Hermitian random matrices, J. Phys. A: Math. Gen. 31 (1998), 1141-1152.
  * [12] Y. Chen and N. D. Lawrence, Small eigenvalues of large Hankel matrices, J. Phys. A: Math. Gen., 32 (1999), 7305-7315.
  * [13] Y. Chen and D. S. Lubinsky, Smallest eigenvalues of Hankel matrices for exponential weights, J. Math. Anal. Appl. 293 (2004), 476-495.
  * [14] Y. Chen and M. R. McKay, Coulumb fluid, Painlevé transcendents, and the information theory of MIMO systems, IEEE Trans. Inform. Theory 58 (2012), 4594-4634.
  * [15] Y. Chen, N. S. Haq and M. R. McKay, Random matrix models, double-time Painlevé equations, and wireless relaying, J. Math. Phys. 54 (2013), 063506(55pp).
  * [16] P. Dharmawansa, M. McKay and Y. Chen, Distributionsof Demmel and Related Condition Numbers, Siam J. Matrix Anal., 34 (2012), 257-279.
  * [17] N. Emmart, Y. Chen and C. C. Weems, Computing the smallest eigenvalue of large ill-conditioned Hankel matrices, Commun. Comput. Phys. 18 (2015), 104-124.
  * [18] I. S. Gradshteyn and I. M. Ryzhik, _Table of integrals, series, and products_ , seventh ed. (Elsevier/ Academic Press, Amsterdam, 2007) pp. xlviii+1171, translated from the Russian, Translation edited and with a preface by Alan Jeffrey and Daniel Zwillinger, With one CD-ROM (Windows, Macintosh and UNIX).
  * [19] M. E. H. Ismail, Classical and Quantum Orthogonal Polynomials in One Variable, Encyclopedia of Mathematics and its Applications, Vol. 98, Cambridge University Press, Cambridge, 2005.
  * [20] M. G. Krein and A. A. Nudelman, _Markov moment problems and extremal problems_ , American Mathematical Society, 1977.
  * [21] D. S. Lubinsky, Condition numbers of Hankel matrices for exponential weights, J. Math. Anal. Appl. 314 (2006), 266-285.
  * [22] S. Li, M. Mckay and Y. Chen, On the distribution of MIMO mutual information: An indepth Painlevé based characterization, IEEE Trans. Information Theory, 59 (2013), 5271-5296.
  * [23] R. J. Muirhead, _Aspects of Multivariate Statistical Theory_ , John Wiley & Sons, Inc., Hoboken, New Jersey, 2005.
  * [24] M. L. Meta, _Random Matrices_ , 3rd edition. Elsevier, Singapore, 2006.
  * [25] A. A. Quadeer, R. H. Louie, K. Shekhar, A. K. Chakraborty, M. Hsing, M. R. Mckay, Statistical linkage analysis of substitutions in patient-derived sequences of genotype 1a Hepatitis C Virius non-structural protein 3 exposes targets for immunogen design. J. Virol. 88 (2014), 7628-7644.
  * [26] G. Szegö, On some Hermitian forms associated with two given curves of the complex plane, Trans. Amer. Math. Soc. 40 (1936), 450-461. In: Collected papers (volume 2), 666-678. Birkhaüser, Boston, Basel, Stuttgart, 1982.
  * [27] G. Szegö, Orthogonal Polynomials, 4th edn, 1975.
  * [28] J. Todd, Contributions to the solution of systerms of linear equations and the determination of eigenvalues, Nat. Bur. Standards Appl. Math. Ser. 39 (1959), 109-116.
  * [29] H. Widom and H. S. Wilf, Small eigenvalues of large Hankel matrices, Proc. Amer. Math. Soc. 17 (1966), 338-344.
  * [30] H. Widom and H. S. Wilf, Errata: Small Eigenvalues of Large Hankel Matrices, Proc. Amer. Math. Soc. 19 (1968), 1508.
  * [31] M. Zhu, Y. Chen, N. Emmart and C. Weems, The smallest eigenvalue of large Hankel matrices, Preprint.


# A Note Related to Graph Theory

Jinfeng Li

###### Abstract

This article foucuses on $(P_{3}\cup P_{2},K_{4})$-free graph. In this paper,
we prove that if G is $(P_{3}\cup P_{2},K_{4})$-free, then $\chi(G)\leq 7$. We
then use this result to obtain the upper bound of order and chromatic number
of $(4K_{1},\overline{P_{3}\cup P_{2}},K_{\omega})$-free graph .

Keywords: coloring; chromatic number; clique number; $\chi$-binding function;
$P_{3}\cup P_{2}$-free; $K_{4}$-free.

##  1 Introduction

A graph $G$ consists of its vertex set $V(G)$ and edge set $E(G)\subseteq
V(G)\times V(G)$. The order of $G$, denoted by $n$, is the size of $V(G)$. The
complement of a graph $G$, denoted by $\overline{G}$ or $co-G$, is a graph
with the same vertex set while whose edge set consists of the edges not
present in $E(G)$.

All graphs in this paper are finite and have no loops or parallel edges. A
graph $G$ contains $H$ if $H$ is isomorphic to an induced subgraph of $G$. If
$H_{1}$ is isomorphic to $H_{2}$, then we say $H_{1}\simeq H_{2}$. For a
collection of graphs $H_{t},t=1,2,...,n$, $G$ is
$(H_{1},H_{2},...,H_{n})$-free if it does not contain $H_{t},t=1,2,...,n$. In
this paper, if $G$ does not contain $P_{2}$, we will say that $G$ is edge-
free.

Path and cycle on $n$ vertex is denoted by $P_{n}$ and $C_{n}$, respectively.
The complete graph on that has $n$ vertex is denoted bu $K_{n}$. We use $G\cup
H$ to denote the disjoint union of $G$ and $H$.

A $k$-coloring of a graph $G$ is a function
$\phi:V(G)\rightarrow\\{1,...,k\\}$ such that $\phi(u)\neq\phi(v)$ whenever
$u$ and $v$ are adjacent in $G$. We say that $G$ is $k$-colorable if $G$
admits a $k$-coloring. The chromatic number of $G$ is denoted by $\chi(G)$
which represents the minimum positive integer $k$ such that $G$ is
$k$-colorable. The clique number is denoted by $\omega(G)$ which represents
the size of the largest clique in $G$.

A family $\mathbb{G}$ of graphs is said to be $\chi$-bounded if there exists a
function f such that for every graph $G\in\mathbb{G}$ and every induced
subgraph $H$ of $G$ it holds that $\chi(H)\leq f(\omega(H))$. The function $f$
is called a $\chi$-binding function for $G$. The class of perfect graphs (a
graph $G$ is perfect if for every induced subgraph $H$ of $G$ it holds that
$\chi(H)=\omega(H))$, for instance, is a $\chi$-bounded family with
$\chi$-binding function $f(x)=x$. Therefore, $\chi$-boundedness is a
generalization of perfection. The notion of $\chi$-bounded families was
introduced by Gyárfás who make the following conjecture.

######  conjecture 1.1.

[3] For every forest T, the class of $T$-free graphs is $\chi$-bounded.

For $\omega=3$, Esperet, Lemoine, Maffray and Morel[2] obtained the optimal
bound on the chromatic number: every $(P_{5},K_{4})$-free graph is
5-colorable. Serge Gaspers and Shenwei Huang[6] obtained the optimal bound of
the chromatic number: every $(2P_{2},K_{4})$-free graph is 4-colorable.
Karthick and S. Mishra obtained the optimal bound of the chromatic number:
every $(P_{6},diamond,K_{4})$-free graph is 6-colorable. Rui Li,Jinfeng Li and
Di Wu claimed that [5] $(P_{3}\cup P_{2},K_{4})$-free graph is $9$-colorable.
We follow the methods in this paper and sharper the bound to $7$.

Partition $V(G)$ into two following parts:

  * •

$D_{1}:=\\{x\in V(G)|\omega(G-N(x))\leq 2\\}$

  * •

$D_{2}:=G-D_{1}$

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$-hole. We use $co-donino$ to
denote a graph obtained from $C$ by connecting edges $v1v3$ and $u1u3$.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$-hole. We use $co-A$ to denote
a graph obtained from $C$ by connecting edges $v_{1}v_{3}$ ,$u_{1}u_{3}$ and
$u_{1}v_{3}$.

Our proof includes three major theorem:

######  theorem 1.1.

If $G[D_{1}]$ contains $P_{2}\cup P_{1}$, then $\chi(G)\leq 7$.

######  theorem 1.2.

If $G$ contains $co-domino$ or $co-A$, then $\chi(G)\leq 7$.

######  theorem 1.3.

If $G$ is $(co-domino,co-A)$-free and $G[D_{2}]$ is not an induced subgraph of
$K_{3}$, then $\chi(G)\leq 7$.

Finally, we obtain a theorem for $(4K_{1},\overline{P_{3}\cup P_{2}})$-free
graphs:

######  theorem 1.4.

If $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$-free with clique number
$\omega$ and order n, then $n\leq 7\omega$ and $\chi(G)\leq 4\omega$.

##  2 Structure Around $K_{3}$

Suppose there is a $K_{3}$ in $G$ and its vertex set is
$\\{v_{1},v_{2},v_{3}\\}$. Naturally, we can divide $V(G)$ into following
three sets:

  * •

$A_{0}:=\\{v|v\text{ is not adjacent to any vertex in
}\\{v_{1},v_{2},v_{3}\\}\\}$.

  * •

$A_{1}:=\\{v|v\text{ is adjacent to one vertex in
}\\{v_{1},v_{2},v_{3}\\}\text{ only}\\}$.

  * •

$A_{2}:=\\{v|v\text{ is adjacent to two vertex in
}\\{v_{1},v_{2},v_{3}\\}\text{ only}\\}$.

we need to combine $A_{0}$ and $A_{1}$ and divide it into three disjoint sets:
$B_{1},B_{2},B_{3}$. The set $B_{1}$ includes vertices that is only adjacent
to $u_{1}$ and vertices in $A_{0}$. The set $B_{j},j=2,3$ includes vertices
that are only adjacent to $u_{j}$. Since $G[B_{i}]$ is anticomplete to an edge
in $G[\\{v_{1},v_{2},v_{3}\\}]$, $G[B_{i}],i=1,2,3$ is $P_{3}$-free.

$A_{2}\cup\\{v_{1},v_{2},v_{3}\\}$ can be partitioned in to $(N(v_{i})\cap
N(_{i-1}))\cup\\{v_{i+1}\\}$(mod3) for $i=1,2,3$. It is easy to obtain that
$\chi((N(v_{i})\cap N(_{i-1}))\cup\\{v_{i+1}\\})\leq 1$(mod3) for $i=1,2,3$.

##  3 main theorem

We first introduce a lemma provided by Rui Li, Jinfeng Li and Di Wu.

######  lemma 3.1.

[5] If $G$ contains $P_{2}\cup K_{3}$, then $\chi(G)\leq 6$.

Define $D_{1}:=\\{x|\omega(G-N(x))\leq 2\\}$ and $D_{2}:=G-D_{1}$.

######  claim 3.2.

For any two nonadjacent vertex $y_{1},y_{2}$ in $D_{1}$,
$\omega(G[N(y_{1})-N(y_{2})])\leq 1$ and $\omega(G[N(y_{2})-N(y_{1})])\leq 1$.

Proof. If there is an edge in $G[N(y_{1})-N(y_{2})]$(or
$G[N(y_{2})-N(y_{1})]$), then $\omega(G[N(y_{1})-N(y_{2})])=3$(or
$\omega(G[N(y_{2})-N(y_{1})])=3$), which contradicts definition of $y_{1}$(or
$y_{2}$).∎

We fisrt introduce a lemma to help us slightly determine the structure of
$G[D_{1}]$.

######  theorem.

(1.1) If $G[D_{1}]$ contains $P_{2}\cup P_{1}$, then $\chi(G)\leq 7$.

Proof. Suppose $G[\\{v_{1},v_{2}\\}\cup\\{v_{3}\\}]\simeq P_{2}\cup P_{1}$,
$M(v_{1},v_{2})=G-\\{v_{1},v_{2}\\}-(N(v_{1})\cup N(v_{2}))$. we can divide
$G$ into $\\{v_{1},v_{2}\\}\cup(N(v_{1})\cup N(v_{2}))\cup M(v_{1},v_{2})$.
Since $G$ is $(P_{3}\cup P_{2},P_{2}\cup K_{3})$-free, $G[M(v_{1},v_{2})]$ is
unions of clique and $\omega(M(v_{1},v_{2}))\leq 2$. Therefore,
$\\{v_{1},v_{2}\\}\cup M(v_{1},v_{2})\leq 2$.

We will prove $\chi(N(v_{1})\cup N(v_{2}))\leq 5$ and hence $\chi(G)\leq 7$.
$N(v_{1})\cup N(v_{2})$ can be divided into $N(v_{1})-N(v_{3})$,
$(N(v_{1})\cap N(v_{3}))-N(v_{2})$, $N(v_{2})-N(v_{3})$, $(N(v_{2})\cap
N(v_{3}))-N(v_{1})$ and $N(v_{1})\cap N(v_{2})$. We apply claim 3.3 to prove
that the clique number of first four sets are at most 1. If the last set has
edge, then $\omega(G)\geq 4$. Therefore, $\chi(N(v_{1})\cup N(v_{2}))\leq 5$.
∎

######  observation 1.

If $G[D_{1}]$ is $P_{2}\cup P_{1}$-free, then $\overline{G[D_{1}]}$ is
$P_{3}$-free.

Now we introduce a lemma which is important in the proof of theorem1.2.

######  claim 3.3.

Suppose $V(G)$ can be partitioned into three nonempty subsets $V_{1}$ ,
$V_{2}$ and $V_{3}$ such that $G[V_{1}]$ and $G[V_{2}]$ are
$(K_{3},P_{3})$-free graph, $G[V_{3}]$ is a stable set , $G[V_{1}\cup V_{2}]$
is $K_{3}$-free , $G[V_{j}\cup V_{3}]$ is $(K_{3},P_{3})$-free graph for
$j=1,2$ and any vertex $v$ in $V_{i},i=1,2$, $M(v)-V_{i}$ has no edge.
Furthermore, for any vertex $v\in V_{3}$, if $N(v)\cap V_{i}\neq\emptyset$,
then $N(v)\cap V_{i}=\\{x\in V_{i}|x\text{ is not complete to }N(v)\cap
N_{3-i}\\},i=1,2$. If $G[V_{1}]$ has at most one edge, then $\chi(G)\leq 3$.

###### Proof.

If $V_{1}$ has no edge, then randomly select one vertex $v\in V_{1}$. We
partition $V(G)$ accoding to $\\{v\\}$, that is $V(G)=\\{v\\}\cup N(v)\cup
M(v)$. $|N(v)\cap V_{3}|\leq 1$. Now we partition $V(G)$ into three stable
set: $(N(v)\cap V_{3})\cup(V_{1}\cap M(v))$, $N(v)\cap V_{2}$ and
${v}\cup(M(v)-V_{1})$. $(N(v)\cap V_{3})\cup(V_{1}\cap M(v))$ is stable set as
$G[V_{3}\cup V_{1}]$ is $P_{3}$-free. According to definition, the rest two
sets are stable sets.

If $V_{1}$ has one edge, then set one vertex of the vertex set of that edge
$v$. We partition $V(G)$ into three part: $V(G)=\\{v\\}\cup N(v)\cup M(v)$. It
is obvious that $N(v)\subseteq V_{2}$, otherwise $G[V_{1}\cup V_{2}]$ induces
an $P_{3}\cup P_{2}$ or $K_{3}\cup P_{2}$. Therefore, as $G[V_{1}\cup V_{2}]$
is $K_{3}$-free, we can conclude that $\chi(N(v))\leq 1$.
$\chi(M(v))\leq\chi(M(v)\cap V_{1})+\chi(M(v)-V_{1})\leq 2$ and hence
$\chi(G)\leq\chi(N(v))+\chi(\\{v\\}\cup M(v))\leq 3$. ∎

######  observation 2.

If $G$ contains $co-domino$, then according to section 2.1, $V(G)$ can be
partitioned into $B_{1},B_{2},B_{3}$ and $A_{2}$.

######  lemma 3.4.

If $G$ contains $co-domino$, then $\chi(G)\leq 7$.

Proof.

$\omega(G[B_{2}])\leq 1$. Otherwise there exists an edge in $G[B_{2}]$. We
call the edge $G[\\{y_{1},y_{2}\\}]$. If $y_{1}\sim u_{2}$, then
$G[\\{v_{1},v_{3}\\}\cup\\{y_{2},y_{1},u_{2}\\}]\simeq P_{3}\cup P_{2}$ or
$G[\\{v_{1},v_{3}\\}\cup\\{y_{2},y_{1},u_{2}\\}]\simeq K_{3}\cup
P_{2}$(depending on whether $y_{2}$ is adjacent to $u_{2}$). As a consequence,
both $y_{1}$ and $y_{2}$ are not adjacent to $u_{2}$. However, $y_{1}$ is
complete to $\\{u_{1},u_{3}\\}$, which can be proven through making use of
$P_{2}\cup P_{3}$-free. Similarly, $y_{2}$ is complete to $\\{u_{1},u_{3}\\}$.
As a consequence, $G[\\{y_{1},y_{2},u_{3},u_{1}\\}]\simeq K_{4}$, which
contradicts the fact that $\omega(G)\leq 3$. As a consequence,
$\chi(B_{2})\leq 1$.

For any $x\in B_{2}$, $N(x)$ must be one of four following sets:
$\\{u_{1},u_{2}\\}$,$\\{u_{2},u_{3}\\}$,$\\{u_{2}\\}$ and $\\{u_{3},u_{1}\\}$.
We partition $B_{2}$($\\{u_{1},u_{2}\\}$) into
$C_{1}$($\\{u_{2},u_{3}\\}$),$C_{2}$($\\{u_{2},u_{3}\\}$),$C_{3}$($\\{u_{2}\\}$)
and $C_{4}$($\\{u_{3},u_{1}\\}$) accoding to their neigbors in
$\\{u_{1},u_{2},u_{3}\\}$. Trivially , $C_{i}\cap C_{j}=$ for $i\neq
j\in\\{1,2,3,4\\}$.

If $C_{1}\neq\emptyset$, then there is no edge in $G[B_{3}]$. Suppose
$\\{y_{1},y_{2}\\}\in E(B_{3})$ and $x\in C_{1}$, we are going to prove
$y_{i},i=1,2$ are complete to $\\{v_{1},x\\}$ and anticomplete to
$\\{u_{2},u_{3}\\}$ and hence $G[\\{y_{1},y_{2},u_{1},x\\}]\simeq K_{4}$,
which contradicts $\omega(G)\textless 4$. If $y_{1}$ is adjacent to $u_{2}$,
then $G[\\{y_{1},u_{3},u_{2}\\}\cup\\{v_{2},v_{1}\\}]$ is isomorphic to
$P_{2}\cup P_{3}$ or $P_{2}\cup K_{3}$. Symmetrically, $y_{2}$ is anticomplete
to $\\{u_{2},u_{3}\\}$. As consequence, $y_{1}$ must be complete to
$\\{u_{1},x\\}$, or $G[\\{u_{2},u_{1},x,v_{2},v_{3},y_{1}\\}]$ will induce
$P_{3}\cup P_{2}$. Symmetrically, $y_{2}$ is complete to $\\{x,u_{1}\\}$. As
consequence, we get the contradiction that $G[\\{y_{1},y_{2},u_{1},x\\}]\simeq
K_{4}$. Therefore, $\omega(B_{3})\leq 1$.

If $C_{2}\neq\emptyset$, then there is no edge in $G[B_{1}-A_{0}]$, which is
similar to the proof for $C_{1}\neq\emptyset.$

From dicussion above, if $C_{1}\cup C_{2}\neq\emptyset$, then $\chi(B_{1}\cup
B_{2}\cup B_{3})\leq 4$ and hence $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup
B_{3})+\chi(A_{2}\cup\\{v_{1},v_{2},v_{3}\\})\leq 4+3=7$.

Suppose $C_{1}\cup C_{2}=\emptyset$ and $x\in C_{3}$. Furthermore,
$|C_{3}|\leq 1$. Otherwise, $G[\\{u_{2}\\}\cup\\{v_{1},v_{3}\\}\cup C_{3}]$
induces $P_{3}\cup P_{2}$ or $P_{2}\cup K_{3}$. According to the definition,
$A_{2}$ can be partitioned into $N(v_{1})\cap N(v_{2})$, $N(v_{1})\cap
N(v_{3})$ and $N(v_{2})\cap N(v_{3})$.

Suppose there is a vertex in $(N(v_{2})\cap N(v_{3})$ has only one neighbor in
$\\{u_{1},u_{2},u_{3}\\}$. It is not difficult to obtain that the only
neighbor is $v_{2}$. If we exchange $\\{v_{1},v_{2},v_{3}\\}$ and
$\\{u_{1},u_{2},u_{3}\\}$ in $co-domino$, then we can prove $\chi(G)\leq 7$ in
the same way as what we did when $C_{1}\cup C_{2}\neq\emptyset$.

Suppose evrey vertex in $A_{2}\cap N(v_{2})$ has two neighbors in
$\\{u_{1},u_{2},u_{3}\\}$.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\\{u,x\\}$ be two
vertex outside $C$. We use co-donino1 to denote a family of graphs obtained
from $\\{u,x\\}\cup C$ by connecting edges
$uu_{1},uu_{2},uv_{1},uv_{2},xv_{2},xu_{2}$ and $xu$ can be connected or
disconnected.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\\{u,x\\}$ be two
vertex outside $C$. We use co-domino2 to denote a graph obtained from $C$ by
connecting edges $uu_{1},uu_{2},uv_{1},uv_{3},xv_{2},xu_{2}$ and $xu$. Suppose
$u\in N(v_{2})\cap N(v_{1})$. The following case shows that if $u$ is complete
to $\\{u_{1},u_{2}\\}$ or complete to $\\{u_{2},u_{3},x\\}$, then $\chi(G)\leq
7$. In other words, if $G$ contains co-domino1 or co-domino2, then
$\chi(G)\leq 7$.

Recalling that $G[B_{3}]$ is anticomplete to $u_{2}$ , $B_{3}-\\{u_{3}\\}$ is
anticomplete to $u_{2}$.

case1: $G$ contains $co-domino1$ or $co-domino2$.

Suppose $G$ contains $co-domino1$.

$G[B_{3}]$ contains at most one edge. Otherwise, suppose $G[B_{3}]$ contains
more than one edge. Since $G[B_{3}]$ is $P_{3}$ -free and complete to
$\\{u_{1}\\}$ and anticomplete to $\\{u_{3}\\}$, there exists an $m$ such that
these edges are isomorphic to $mK_{2},m\textgreater 1$ and $u$ has at most one
neighbor in every edges or $G[\\{u,u_{1}\\}\cup B_{3}]$ induces $K_{4}$.
However, $m\textgreater 1$ leads to a contradiction that
$G[\\{B_{3}-N(u)\\}\cup\\{u,u_{2}\\}]$ induces $P_{3}\cup P_{2}$.

Let
$G[B_{1}-A_{0}]=V_{1}^{\prime},G[B_{3}]=V_{2}^{\prime},G[A_{0}]=V_{3}^{\prime}$.
According to claim3.3, $\chi(B_{3}\cup B_{1})\leq 3$. Therefore,
$\chi(G)\leq\chi(B_{1}\cup B_{3})+\chi(B_{2})+\chi(A_{2})\leq 3+1+3=7$.

Suppose $G$ is $co-domino1$-free and contains $co-domino2$.

$G[B_{1}-A_{0}]$ contains at most one edge. Since $G[B_{1}-A_{0}]$ is $P_{3}$
-free and complete to $\\{u_{1}\\}$ and anticomplete to $\\{u_{3}\\}$, this
union of edges is isomorphic to $mK_{2},m\textgreater 1$ for some $m$ and $u$
has at most one neighbor in every edge or $G[\\{u,x\\}\cup B_{3}]$ induces
$K_{4}$. However, $m\textgreater 1$ leads to a contradiction that
$G[\\{B_{3}-N(u)\\}\cup\\{u,u_{2}\\}]$ induces $P_{3}\cup P_{2}$.

Let
$G[B_{1}-A_{0}]=V_{1}^{\prime},G[B_{3}]=V_{2}^{\prime},G[A_{0}]=V_{3}^{\prime}$,
then according to claim3.3, $\chi(B_{3}\cup B_{1})\leq 3$. Furthermore,
$\chi(G)\leq\chi(B_{1}\cup B_{3})+\chi(B_{2})+\chi(A_{2})\leq 3+1+3=7$. Let
Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\\{u,x\\}$ be two
vertex outside $C$. We use co-domino3 to denote a graph obtained from $C$ by
connecting edges $uu_{1},uu_{2},uv_{1},uv_{3},xv_{2}$ and $xu_{2}$.

Suppose $u\in N(v_{1})\cap N(v_{2})$ and $u\sim u_{2},u\sim u_{3},u\not\sim
x$. The following case shows that if $u$ exists, then $\chi(G)\leq 7$. In
other words, if $G$ contains $co-domino3$, then $\chi(G)\leq 7$.

Partition $A_{2}=(N(v_{1})\cap N(v_{2}))\cup(N(v_{2})\cap
N(v_{3}))\cup(N(v_{1})\cup N(v_{3}))$ into following five vertex sets.

$D_{1}:=N(v_{1})\cap N(v_{2})\cap N(u_{2})\cap N(u_{3})$.
$D_{2}:=N(v_{1})\cap N(v_{2})\cap N(u_{1})\cap N(u_{3})$.
$D_{3}:=N(v_{2})\cap N(v_{3})\cap N(u_{1})\cap N(u_{2})$.
$D_{4}:=N(v_{2})\cap N(v_{3})\cap N(u_{1})\cap N(u_{3}).$
$D_{5}:=N(v_{1})\cap N(v_{3}).$

case2: Suppose $G$ contains $co-domino3$.

Suppose $\\{u,u^{\prime}\\}\subseteq E[D_{1},D_{3}]$.

$\chi(B_{1}\cup B_{3}-\\{u_{1},u_{3}\\})\leq 3$. Define $I:=B_{1}\cup
B_{3}-\\{u_{1},u_{2},u_{3}\\}$. Recalling that $B_{1}\cup B_{3}-A_{0}$ is
anticomplete to $\\{u_{2}\\}$ and that $A_{0}$ is anticomplete to
$\\{v_{1},v_{2},v_{3}\\}$, $I$ is anticomplete to $\\{v_{2},u_{2}\\}$.
Therefore, $I-N(u)$ is anticomplete to $\\{v_{2},u,u_{2}\\}$. Since
$G[\\{v_{2},u,u_{2}\\}]\simeq P_{3}$, $I-N(u)$ is a stable set and hence
$\chi(I-N(u))\leq 1$. Similarly, $\chi((I\cap N(u))-N(u^{\prime}))\leq 1$.
Trivially, $(I\cap N(u)\cap N(u^{\prime}))\cup\\{u_{2}\\}$ is stable set and
hence the chromatic number is less than 2. Therefore,
$\chi(G)\leq\chi(I-N(u))+\chi((I\cap N(u))-N(u^{\prime}))+\chi((I\cap N(u)\cap
N(u^{\prime}))\cup\\{u_{2}\\})\leq 1+1+1=3.$

$G[D_{1}\cup\\{u_{1}\\}\cup\\{x\\}\cup\\{v_{3}\\}]$ is a stable set. If
$E[\\{x\\},D_{1}]\neq\emptyset$, then $G$ contains $co-domino2$. Accoding to
definition, $E[\\{u_{1}\\},D_{1}\cup\\{x\\}]=\emptyset$. The rest is obvious.

$G[D_{2}\cup D_{4}\cup(B_{2}-\\{x\\})]$ is a stable set. Recalling that
$|C_{3}|\leq 1$ and $C_{1}=C_{2}=\emptyset$, $B_{2}-\\{x\\}=C_{4}$. According
to definition $D_{2}\cup D_{4}\cup(B_{2}-\\{x\\})$ is complete to
$\\{u_{1},u_{3}\\}$ and the rest is obvious.

$G[D_{3}\cup\\{u_{3}\\}\cup\\{v_{1}\\}]$ is a stable set. According to
definition, $E[D_{3},u_{3}]=\emptyset$ and $G[E_{3}]$ is a stable set. The
rest is obvious.

Let $D_{5}^{\prime}$ be $D_{5}\cup\\{v_{2}\\}$. $\chi(G)\leq\chi(B_{1}\cup
B_{3}-\\{u_{1},u_{3}\\})+\chi(D_{1}\cup\\{u_{1}\\}\cup\\{x\\}\cup\\{v_{3}\\})+\chi(D_{2}\cup
D_{4}\cup(B_{2}-\\{x\\}))+\chi(D_{3}\cup\\{u_{3}\\}\cup\\{v_{1}\\})\leq
4+1+1+1=7.$

Suppose $E[D_{1},D_{3}]=\emptyset$.

$G[D_{1}\cup D_{3}\cup\\{x\\}]$ is a stable set. If $E[\\{x\\},D_{1}\cup
D_{3}]\neq\emptyset$, then $G$ contains $co-domino2$. Since
$E[D_{1},D_{3}]=\emptyset$, $G[D_{1}\cup D_{3}\cup\\{x\\}]$ .

$\chi(G)\leq\chi(D_{1}\cup D_{3}\cup\\{x\\})+\chi(D_{2}\cup
D_{4}\cup(B_{2}-\\{x\\}))+\chi(B_{1}\cup\\{v_{2},v_{3}\\})+\chi(B_{3}\cup\\{v_{1}\\})+\chi(D_{5})\leq
1+1+2+2+1\leq 7$.

Combining $co-domino2$-free, $do-domino3$-free and our supposition that evrey
vertex in $A_{2}\cap N(v_{2})$ has two neighbors in $\\{u_{1},u_{2},u_{3}\\}$,
if $u\in N(v_{1})\cap N(v_{2})$, then $u$ is complete to $\\{u_{1},u_{3}\\}$.
Similarly, if $u\in N(v_{2})\cap N(v_{3})$ ,then $u$ is complete to
$\\{u_{1},u_{3}\\}$. Therefore, $G[(N(v_{1})\cap N(v_{2}))\cup(N(v_{2})\cap
N(v_{3}))]$ is a stable set.

Furthermore,$\chi(N(v_{2})-\\{v_{1},v_{3}\\})\leq 2$. Noticing that
$N(v_{2})=(N(v_{1})\cap N(v_{2}))\cup(N(v_{3})\cap N(v_{2}))\cup C_{3}\cup
C_{4}$, the proof is easy.

$\chi(G)\leq\chi(N(v_{2})-\\{v_{1},v_{3}\\})+\chi(B_{1}\cup\\{v_{2},v_{3}\\})+\chi(B_{3}\cup\\{v_{1}\\})+\chi(N(v_{1})\cap
N(v_{3}))\leq 2+2+2+1=7.$

Therefore, if $C_{3}\neq\emptyset$, $\chi(G)\leq 7.$

Suppose $C_{1}=C_{2}=C_{3}=\emptyset$. We continue to use notations
$D_{1},D_{2},...,D_{5}$. Similar to case2, $\chi(G)\leq 7$.(The proof does not
depend on the existence on {x}.)∎

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$-hole and $\\{u\\}$ be a vertex
outside the $6$-hole. We use $X_{1}$ to denote a graph obtained from
$\\{u\\}\cup C$ by connecting edges $v_{1}v_{3},uv_{1}$ and $uu_{2}$.

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$-hole and $\\{u\\}$ be a vertex
outside the $6$-hole. We use $X_{2}$ to denote a graph obtained from
$\\{u\\}\cup C$ by connecting edges
$v_{1}v_{3},v_{3}u_{1}$,$u_{1}u_{3},v_{2}u$ and $uu_{2}$.

The following figures are $X_{1}$ and $X_{2}$( from left to right).

######  lemma 3.5.

Suppose $G$ is $co-domino$-free and contains $X_{1}$ or $X_{2}$, then
$\chi(G)\leq 7$.

Proof.

case1:G contains $X_{1}$.

$G[B_{1}-A_{0}-\\{u_{1}\\}]$ is anticomplete to $\\{u_{1},u_{2}\\}$ and
complete to $\\{u,u_{3}\\}$.Suppose $y\in B_{1}-A_{0}$ and $y\sim u_{1}$(or
$u_{2}$) only, then $G[\\{y,u_{1},u_{2}\\}\cup\\{v_{3},v_{1}\\}]\simeq
P_{3}\cup P_{2}$. Therefore, $y$ must complete to both $u_{2}$ and $u_{1}$ and
hence we get $G[\\{y,u_{1},u_{2}\\}\cup\\{v_{1},v_{3}\\}]\simeq K_{3}\cup
P_{2}$,which contradics our assumption. $G[B_{2}]$ is complete to
$\\{u_{3}\\}$(or $u$) or
$G[(B_{2}-A_{0})\cup\\{v_{1},v_{2}\\}\cup\\{u_{3},u_{2}\\}]$ will induce an
$P_{3}\cup P_{2}$($G[(B_{2}-A_{0})\cup\\{v_{1},v_{2}\\}\cup\\{u,u_{2}\\}]$
will induce a $P_{3}\cup P_{2}$).

Symmetrically , $G[B_{3}-\\{u_{3}\\}]$ is anticomplete to $\\{u_{2},u_{3}\\}$
and complete to $\\{u,u_{1}\\}$ and $G[B_{2}]-\\{u\\}$ is anticomplete to
$\\{u_{1},u_{3}\\}$ and anticomplete to $\\{u,u_{2}\\}$.

Either $G[B_{1}-A_{0}]$ or $G[B_{3}]$ is edge-free. According to the above
paragraph, $G[(B_{1}-A_{0})\cup B_{3}]$ is complete to $u$ and hence it is
$K_{3}$-free. Suppose there is an edge in $G[B_{1}-A_{0}]$($y_{1},y_{2}$) and
an edge in $G[B_{3}]$($y_{3},y_{4}$).

We prove $G[v_{4},y_{1},y_{2},y_{3},y_{4},v_{6}]\simeq co-domino$ to obtain a
contradicion. It is easy to see that $y_{3}$ should have at least one neighbor
in $\\{y_{2},y_{1}\\}$. So does $y_{4}$. Consequently,
$G[\\{y_{1},y_{2},y_{3},y_{4}\\}]\simeq C_{4}$, otherwise
$G[\\{x_{1},x_{2},y_{1},y_{2}\\}]$ must contain $K_{3}$.

Symmetrically, either $G[B_{1}-A_{0}]$ or $G[B_{2}]$ is edge-free and either
$G[B_{2}]$ or $G[B_{3}]$ is edge-free.

$\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$. Recalling that $G[B_{i}]$ is
$P_{3}$-free. Suppose $G[B_{1}-A_{0}]$ has edge, then $\chi(B_{2})\leq
1,\chi(B_{3})\leq 1$. If $G[B_{2}]$ or $G[B_{3}]$ contains edge, then we can
prove $\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$. If $G[B_{1}-A_{0}]$,$G[B_{2}]$
and $G[B_{3}]$ are all edge-free, then it is trvial that $\chi(B_{1}\cup
B_{2}\cup B_{3})\leq 4$.

Therefore, $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})+\chi(A_{2})\leq 4+3=7.$

case2: $G$ is $X_{1}$-free and contains $X_{2}$.

Accoring to section 2.1, we partition $V(G)$ around
$G[\\{v_{1},v_{2},v_{3}\\}]$.

Every vertex in $B_{2}-\\{u\\}$ is adjacent to $u_{3}$ and not adjacent to
$u_{2}$. If there is $x\in B_{2}-\\{u\\}$ such that $x$ is not adjacent to
$u_{3}$, then $x$ is adjacent to $u_{2}$. Otherwise
$G[\\{v_{1},v_{2},x\\}\cup\\{u_{2},u_{3}\\}]\simeq P_{3}\cup P_{2}$ or
$K_{3}\cup P_{2}$. Therefore, we can simply suppose there is $x\in
B_{2}-\\{u\\}$ such that $x$ is adjacent to $u_{2}$. However,
$G[\\{u,u_{2},x\\}\cup\\{v_{1},v_{3}\\}]\simeq P_{3}\cup P_{2}$ or $K_{3}\cup
P_{2}$(depending on the adjacency of $u$ and $x$). Therefore, such $x$ does
not exist.

Every vertex in $B_{1}-A_{0}$ is adjacent to $\\{u_{3}\\}$.

Every vertex in $B_{3}$ is anticomplete to $\\{u_{2},u_{3}\\}$.

Partition $B_{1}\cup B_{2}\cup B_{3}-A_{0}$ into the folloing six sets.

  * •

$D_{1}:=\\{x\in(B_{2}-\\{u\\})|x\text{ is adjacent to }u_{1}\text{ and
}u_{3}\\}$.

  * •

$D_{2}:=\\{x\in(B_{2}-\\{u\\})|x\text{ is adjacent to }u_{3}\text{ only}\\}$.

  * •

$D_{3}:=\\{x\in(B_{1}-A_{0})|x\text{ is adjacent to }u_{3}\text{ only}\\}$.

  * •

$D_{4}:=\\{x\in(B_{1}-A_{0})|x\text{ is adjacent to }u_{1}\text{ and
}u_{3}\\}.$

  * •

$D_{5}:=\\{x\in B_{3}|x\text{ is adjacent to }u_{1}\\}.$

  * •

$D_{6}:=\\{x\in B_{3}|x\text{ has no neighbor in }\\{u_{1},u_{2},u_{3}\\}\\}.$

Since $D_{1}\cup D_{4}$ is compete to $\\{u_{1},u_{3}\\}$ and $u_{1}\sim
u_{3}$, $G[D_{1}\cup D_{4}]$ has no edge and hence $\chi(D_{1}\cup D_{4})\leq
1$.

Since $D_{2}$ and $D_{3}$ anticomplete to $\\{v_{3},u_{1},u_{2}\\}$,
$G[D_{2}\cup D_{3}]$ is $P_{2}$-free and hence $\chi(D_{2}\cup D_{3})\leq 1$.

$E[\\{u\\},A_{0}\cup D_{6}]=\emptyset$. Since $\\{u\\}\cup D_{6}$ is
anticomplete to $\\{v_{1},u_{1},u_{3}\\}$ and
$G[\\{v_{1},u_{1},u_{3}\\}]\simeq P_{3}$, $G[\\{u\\}\cup D_{6}]$ has no edge.
Since $\\{u\\}\cup A_{0}$ is anticomplete $v_{1},v_{3},u_{3}$ and
$G[\\{v_{1},v_{3},u_{3}\\}]\simeq P_{3}$(It is trivial that $u_{3}$ is
anticomplete to $A_{0}$), $G[\\{u\\}\cup A_{0}]$ has no edge.

Since $D_{6}\cup A_{0}$ is anticomplete to $\\{v_{2},v_{1},u_{1}\\}$ and
$G[\\{v_{2},v_{1},u_{1}\\}]\simeq P_{3}$, $G[A_{0}\cup D_{6}]$ has no edge and
hence $G[\\{u\\}\cup D_{6}\cup A_{0}]$ has no edge.

$\chi(B_{1}\cup B_{2}\cup B_{3})\leq\chi(D_{1}\cup D_{4})+\chi(D_{2}\cup
D_{3})+\chi(A_{0}\cup\\{u\\}\cup D_{6})+\chi(D_{5})\leq 4$. Therefore,
$\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})+\chi(A_{2})\leq 7.$∎

Suppose all graphs are $(co-domino,K_{3}\cup P_{2},X_{1},X_{2})$-free.

Let $C=v_{1}v_{2}v_{3}v_{4}v_{5}$ be a $5$-hole. We use $co-twin-C_{5}$ to
denote a graph obtained from $C$ by adding a vertex $\\{v_{6}\\}$ which is
only adjacent $\\{v_{3},v_{4},v_{5}\\}$.

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$-hole and $\\{u\\}$ be a vertex
outside the $6$-hole. We use $\mathcal{Y}$ to denote a family of graphs
obtained from $\\{u\\}\cup C$ by connecting edge $uv_{1},uv_{2}$ and $uu_{2}$
and it does not matter whether $uu_{1}$ is connected or not.

Define $M(v_{1},v_{2}):=G-N(v_{1})-N(v_{2})-\\{v_{1},v_{2}\\}$. In this lemma,
$N(v_{1})$ does not include $\\{v_{2}\\}$ and $N(v_{2})$ does not include
$\\{v_{1}\\}$. We introduce a partition which is useful in the following
lemma.

######  observation 3.

If $G$ contains $co-twin-C_{5}$. $V(G)$ can be partitioned into
$\\{v_{1},v_{2}\\},N(v_{2})\cup N(v_{1})$ and $M(v_{1},v_{2})$.

######  lemma 3.6.

If $G$ contains $co-twin-C_{5}$, then $\chi(G)\leq 7$.

Proof.

case1: G contains an element of $\mathcal{Y}$.

$G[B_{1}-A_{0}]$ is complete to $\\{u_{3}\\}$ and anticomplete to
$\\{u_{1},u_{2}\\}$. Otherwise, suppose there is $x\in G[B_{1}-A_{0}]$ which
is not adjacent to $\\{u_{3}\\}$ or has neighbor in $\\{u_{1},u_{2}\\}$. If
$x$ has neighbor in $\\{u_{1},u_{2}\\}$, then
$G[\\{x,u_{1},u_{2}\\}\cup\\{v_{2},v_{3}\\}]$ induces $P_{3}\cup P_{2}$ or
$K_{3}\cup P_{2}$. Therefore, $x$ is not adjacent to $u_{3}$ and hence
$G[\\{v_{2},x\\}]\simeq P_{2}$ is anticomplete to
$G[\\{u_{1},u_{2},u_{3}\\}]\simeq P_{3}$. Therefore, such $x$ does not exist.

Similarly, $G[B_{3}]$ is complete to $\\{u_{1}\\}$ and anticomplete to
$\\{u_{3},u_{2}\\}$.

Either $G[B_{1}-A_{0}]$ or $G[B_{3}]$ has no edge. Otherwise, suppose there is
an edge($y_{1},y_{2}$) in $G[B_{1}-A_{0}]$ and an edge($y_{3},y_{4}$) in
$G[B_{3}]$. If $G[\\{y_{1},y_{2},y_{3},y_{4}\\}]$ induces $diamond$ or
$C_{4}$, then $G[\\{u_{1},u_{2},u_{3},y_{1},y_{2},y_{3},y_{4}\\}]$ induces
$X_{1}$ or $X_{2}$. Therefore, $G[\\{y_{1},y_{2},y_{3},y_{4}\\}]$ is not
isomorphic to $diamond$, $C_{4}$ and $K_{4}$. However, such condition requires
$G[\\{y_{1},y_{2},y_{3},y_{4}\\}]$ to be isomorphic to $P_{4}$ or $2K_{2}$.
Therefore, there must be a vertex has degree one in
$G[\\{y_{1},y_{2},y_{3},y_{4}\\}]$. Suppose $d(y_{1})=1$ in
$G[\\{y_{1},y_{2},y_{3},y_{4}\\}$. Then $y_{1}$ is anticomplete to
$\\{y_{3},y_{4}\\}$ and hence
$G[\\{u_{2},u_{3},y_{1}\\}\cup\\{y_{3},y_{4}\\}]\simeq P_{3}\cup P_{2}$.
Therefore, either $y_{1},y_{2}$ does not exist or $\\{y_{3},y_{4}\\}$ does not
exists.

$G[B_{2}]$ is complete to $\\{u_{3}\\}$. Otherwise, suppose there exists $z\in
G[B_{2}]$ such that z is not adjacent to $\\{u_{3}\\}$. $z$ is adjacent to
$u_{2}$, otherwise $G[\\{v_{1},v_{2},z\\}\cup\\{u_{2},u_{3}\\}]\simeq
P_{3}\cup P_{2}$. Since $G[\\{x,u_{1},u_{2},u_{3},v_{1},v_{2},v_{3}\\}]\simeq
X_{1}$, $z$ is adjacent to $u_{1}$. However, if $z$ is adjacent to $u_{1}$,
then $G[\\{z,u_{1},u_{2},v_{1},v_{2},v_{3}\\}]\simeq co-domino$. Therefore,
such $z$ does not exist.

$G[B_{2}]$ contains at most one edge. Suppose there are two edges in
$G[B_{3}]$($\\{y_{1},y_{2}\\}$ and $\\{y_{3},y_{4}\\}$ ). Because $v_{2}$ is
complete to $\\{u,y_{1},y_{2},y_{3},y_{4}\\}$. $u$ has at most one neighbor in
$\\{y_{1},y_{2}\\}$ and $\\{y_{3},y_{4}\\}$. Suppose $u\not\sim
y_{2},u\not\sim y_{3}$. Since both $y_{2},y_{3}$ are not adjacent to $v_{1}$,
$G[\\{y_{3},u_{3},y_{2}\\}\cup\\{u,v_{1}\\}]\simeq P_{3}\cup P_{2}$, which
causes contradiction. Therefore, $G[B_{2}]$ has at most one edge.

Suppose $B_{1}-A_{0}$ has no edge. Let $B_{2}=V_{1},B_{3}=V_{2},A_{0}=V_{3}$,
then we can apply claim3.3 to get $\chi(B_{1}\cup B_{2}\cup
B_{3})\leq\chi(B_{1}-A_{0})+\chi(B_{2}\cup B_{3}\cup A_{0}\leq 4$ and hence
$\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4+3=7$.

case2: G is $\mathcal{Y}$-free and contains a $co-tiwn-C_{5}$.

According to observation 3, $V(G)=\\{v_{1},v_{2}\\}\cup(N(v_{2})\cup
N(v_{1}))\cup M(v_{1},v_{2})$.

Noticing that vertices in $N(v_{1})\cup N(v_{2})-\\{v_{3},v_{5}\\}$ have
neighbor in $\\{v_{4},v_{6}\\}$, we can divide $N(v_{1})\cup
N(v_{2})-\\{v_{3},v_{5}\\}$ to make the structure more clearly. We difine two
disjoint sets as following:

  * •

$D_{1}:=\\{y|y\in N(v_{1})\cup N(v_{2})-\\{v_{3},v_{5}\\},y$ is adjacent to
only one vertex in $\\{v_{3},v_{4},v_{5},v_{6}\\}\\}$

  * •

$D_{2}:=\\{y|y\in N(v_{1})\cup N(v_{2})-\\{v_{3},v_{5}\\},y$ is adjacent to
more than one vertices in $\\{v_{3},v_{4},v_{5},v_{6}\\}\\}$

$|D_{1}|=\emptyset$. Otherwise, suppose $y_{1}\in D_{1}$ and $y_{1}\sim
v_{1}$. Suppose $y_{1}$ is adjacent to $\\{v_{4}\\}$. Because if the only
neighbor of $y_{1}$ belongs to $\\{v_{3},v_{5}\\}$ , then
$G[\\{v_{1},v_{2},y_{1},v_{4},v_{6}\\}]$ induces $K_{3}\cup P_{2}$ or
$P_{3}\cup P_{2}$.

If $y_{1}$ is not adjacent to $v_{2}$, then
$G[\\{v_{1},y_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}]$ is isomorphic to an
element in $\mathcal{Y}$(when $u_{1}$ is not adjacent to $u$. However, if
$y_{1}$ is not adjacent to $v_{2}$, then
$G[\\{v_{1},y_{1},v_{2},v_{4},v_{5},v_{6}\\}]\simeq co-domino$. Therefore,
such $y_{1}$ does not exist.

Any vertex in $D_{2}$ is complete to an edge in
$G[\\{v_{3},v_{4},v_{5},v_{6}\\}]$. Otherwise, there is $z\in D_{2}$ which is
not complete to any edge in $G[\\{v_{3},v_{4},v_{5},v_{6}\\}]$. $z$ must be
adjacent to $\\{v_{3},v_{5}\\}$, which leads to the contradiction that
$G[\\{v_{1},v_{2},z,v_{4},v_{6}\\}]$ induces $K_{3}\cup P_{2}$ or $P_{2}\cup
P_{3}$.

$\\{v_{1},v_{2}\\}\cup M(v_{1},v_{2})$ can be colored with no more than $2$
colors.

Recalling that points in $D_{2}$ are at least adjacent to one edge in
$G[\\{v_{3},v_{4},v_{5},v_{6}\\}]$, it is trivial that $\chi(D_{2})\leq 5$. In
summary, $\chi(G)\leq\chi(\\{v_{1},v_{2}\\}\cup
M(v_{1},v_{2}))+\chi(D_{2}\cup\\{v_{3},v_{4},v_{5},v_{6}\\})\leq 2+5\leq 7$. ∎

Suppose all graphs are $(co-domino,K_{3}\cup P_{2},X_{1},X_{2},co-twin-
C_{5})$-free.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$-hole. We use $\chi 37$ to
denote a graph obtained from $C$ by connecting edge $v1v3$.

######  lemma 3.7.

If $G$ contains $\chi 37$ or $co$-$A$, then $\chi(G)\leq 7$.

Proof.

case1: $G$ contains $\chi 37$.

We prove $G[B_{2}]$ is edge-free. We obtain contradiction by proving
$G[\\{v_{1},v_{3},u_{1},u_{3},x_{1},x_{2}\\}]\simeq co-twin-C_{5}$. In other
words, contradiction comes out if $x_{1},x_{2}$ are anticomplete to
$\\{u_{2}\\}$ and complete to $\\{u_{1},u_{3}\\}$. Suppose there is an edge in
$G[B_{2}]$ and we call them $G[x_{1},x_{2}]$. If $x_{1}$(or $x_{2}$),
$G[\\{v_{1},v_{3}\\}\cup\\{x_{1},x_{2},u_{2}\\}]$ would induce $K_{3}\cup
P_{2}$ or $P_{3}\cup P_{2}$. Furthermore, we can prove $\\{x_{1},x_{2}\\}$ is
complete to $\\{u_{1},u_{3}\\}$ without much difficulty and hence we finish
our proof of proposion that $G[B_{2}]$ is edge-free.

Furthermore, either $G[B_{3}]$ or $G[B_{1}-A_{0}]$ has no edge. Otherwise,
suppose there is $\\{y_{1},y_{2}\\}\in E(B_{1}-A_{0})$, $\\{y_{3},y_{4}\\}\in
E(B_{3})$. Since $B_{1}-A_{0}$ is complete to $\\{u_{3}\\}$ and anticomplete
to $\\{u_{1},u_{2}\\}$ and $B_{3}$ is complete to $\\{u_{1}\\}$ and
anticomplete to $\\{u_{2},u_{3}\\}$, $G[y_{1},y_{3},u_{1},u_{3},u_{2},y_{2}]$
induces $co-domino$ or $co-twin-C_{5}$.

According to claim3.3, $\chi(B_{1}\cup B_{3})\leq 3$. Therefore,
$\chi(G)\leq\chi(B_{2})+\chi(B_{1}\cup B_{3})+\chi(A_{2})\leq 7$.

case2: $G$ is $\chi 37$-free and contains a $co$-$A$.

$G[B_{2}]$ is complete to $\\{v_{4},v_{6}\\}$ and hence $G[B_{2}]$ is edge-
free. Otherwise, there is $x\in B_{2}$ such that $x$ has only one neighbor in
$\\{v_{4},v_{6}\\}$. If $x\sim v_{4}$, then $x\sim v_{5}$. Otherwise,
$G[\\{v_{1},v_{2},x\\}\cup\\{v_{5},v_{6}\\}]$ induces $P_{3}\cup P_{2}$.
However, $G[\\{x,v_{2},v_{3},v_{6},v_{5},v_{1}\\}]$ induces $\chi 37$.
Therefore, $x\sim v_{6}$. Now $v\not\sim v_{5}$, otherwise
$G[\\{v_{1},v_{2},v_{3},x,v_{6},v_{5}\\}]$ induces $co-domino$. However,
$G[\\{v_{1},v_{2},x,v_{6},v_{4},v_{5}\\}]$ induces $co-A$. Therefore, such $x$
does not exist.

every edge in $G[B_{1}-A_{0}]$ includes one vertex which is complete to
$\\{v_{4},v_{6}\\}$. Otherwise, there is an edge in $G[B_{1}-A_{0}]$ whose
vertices has at most one neighbor in $\\{v_{4},v_{6}\\}$. If one of them($x$)
is adjacent to $\\{v_{4}\\}$ rather than $\\{v_{6}\\}$,then
$G[\\{v_{2},v_{1},x\\}\cup\\{v_{5},v_{6}\\}]$ induces $P_{3}\cup P_{2}$.
Therefore, none of these vertices is adjacent to $\\{v_{4}\\}$ and hence
$G[\\{v_{3},v_{4},v_{5}\\}\cup B_{1}-A_{0}]$ induces $P_{3}\cup P_{2}$. We
already obtain a contradiction.

According to the above discussion, $G[(B_{1}-A_{0})\cup B_{2}]$ can be
partitioned into two stable sets: the vertices which are complete to
$\\{v_{4},v_{6}\\}$ and the rest of vertices in $B_{1}-A_{0}$. Therefore,
$\chi((B_{1}-A_{0})\cup B_{2})\leq 2$.

Therefore, $\chi(G)\leq\chi(B_{2}\cup(B_{1}-A_{0}))+\chi(B_{3}\cup
A_{0})+\chi(A_{2})\leq 2+2+3=7.$∎

Combining lemma3.4 and lemma3.7, we obtain theorem1.2 straightly.

######  theorem.

1.2 If $G$ contains $co-domino$ or $co-A$, then $\chi(G)\leq 7$.

Suppose $G$ is $(K_{3}\cup P_{2},co-domino,co-A)$-free with
$\overline{G[D_{1}]}$ is $P_{3}$-free.

######  claim 3.8.

If $v_{1},v_{2}\in D_{1}$ and $v_{1}\not\sim v_{2}$, then either
$G[N(v_{1})-N(v_{2})]$ or $G[N(v_{2})-N(v_{1})]$ has no edge.

Proof.

Suppose both sets have edges. The vertex sets in $G[N(v_{1})-N(v_{2})]$ is
$\\{u_{1},u_{2}\\}$ and that of edge in $G[N(v_{2})-N(v_{1})]$ is
$\\{u_{3},u_{4}\\}$. $G[\\{v_{1},v_{2},u_{1},u_{2},u_{3},u_{4}\\}]$ must
induce $co-domino$ or $co-A$ or $P_{3}\cup P_{2}$. Therefore, either
$G[N(v_{1})-N(v_{2})]$ or $G[N(v_{2})-N(v_{1})]$ is edge-free. ∎

######  theorem.

(1.3) If $G[D_{2}]$ is not a clique, then $\chi(G)\leq$7.

Proof.

Since $G[D_{2}]$ is not a clique, $G[D_{2}]$ has two nonadjacent vertices
$\\{v_{1},v_{2}\\}$. According to claim3.8, either $G[N(v_{1})-N(v_{2})]$ or
$G[N(v_{2})-N(v_{1})]$ has no edge. Without loss of generality, we suppose
$G[N(v_{1})-N(v_{2})]$ is edge-free and hence $\chi(N(v_{1})\cup N(v_{2}))\leq
1$.

If $\omega(N(v_{1})\cap N(v_{2}))\leq 1$, then $\chi(N(v_{1})-N(v_{2}))\leq 1$
or $\chi(N(v_{2})-N(v_{1}))\leq 1$. We suppose $\chi(N(v_{1})-N(v_{2}))\leq
1$, then $\chi(v_{1})\leq 2$. If $G[N(v_{1})]$ has edge($\\{v_{2},v_{3}\\}$),
then accoring to section 2.1, $G[\\{v_{1},v_{2},v_{3}\\}]$ can be divided into
$B_{1}\cup B_{2}\cup B_{3}\cup(N(v_{1})\cap N(v_{2}))\cup(N(v_{1})\cap
N(v_{3}))\cup(N(v_{2})\cap N(v_{3}))$.

$\chi(N(v_{1}))\leq\chi(N(v_{1})\cap N(v_{2}))+\chi(N(v_{1})-N(v_{2}))\leq 2$.
The vertex sets left to be colored are:$A_{0},N(v_{2})\cap N(v_{3}),B_{2}$ and
$B_{3}$. Since $\chi(B_{2}\cup A_{0})\leq 2$, $\chi(B_{3})\leq 2$ and
$\chi(N(v_{2})\cap N(v_{3}))\leq 1$. Therefore, $\chi(G)\leq 7.$

Suppose $\omega(N(v_{1})\cap N(v_{2}))=2$.

We partition $V(G)$ into three parts: $\\{v_{1},v_{2}\\}$, $N(v_{1})\cup
N(v_{2})$ and $G-\\{v_{1},v_{2}\\}-N(v_{1})-N(v_{2})$. Define
$A:=G-\\{v_{1},v_{2}\\}-N(v_{1})-N(v_{2})$.

$\chi(A)\leq 3$. Suppose there is an edge($x_{1}x_{2}$) in $G[A]$. Then $A$
can be divided into $A-N(x_{1})$ and $(A-N(x_{2}))\cap N(x_{1})$ and $A\cap
N(x_{1})\cap N(x_{2})$. Since $A-N(x_{1})$ is anticomplete to
$\\{v_{1},x_{1},v_{2}\\}$ and $G[\\{v_{1},x_{1},v_{2}\\}]\simeq P_{3}$,
$G[A-N(x_{1})]$ must be $P_{2}$-free and hence $\chi(A-N(x_{1}))\leq 1$.
Similarly, $\chi((A-N(x_{2}))\cap N(x_{1}))\leq 1$. Because $x_{1}\sim x_{2}$
and $\omega(G)\leq 3$, $\chi(A\cap N(x_{1})\cap N(x_{2}))\leq 1$. Therefore
,$\chi(A)\leq 3$.

$\chi(N(v_{2}))\leq 3$. According to definition of $D_{2}$, there is a
$K_{3}(\\{u_{1},u_{2},u_{3}\\})$ induced in $G[G-N(v_{2})]$. Define
$E_{i}:=\\{x\in N(v_{2})|x\text{ only adjacent to }\\{u_{i}\\}\\}$ and
$E_{i,j}:=\\{x\in N(v_{2})|x\text{ only adjacent to }\\{u_{i}\\}\text{ and
}\\{u_{j}\\}\\}$. Since $G$ is $co$-$A$-free, $E_{i}$ is anticomplete to
$E_{i,i+1}$(mod$3$). Obviously, $|E_{i}|\leq 1$ for $i=1,2,3$ and $G[E_{i,j}]$
is edge-free. Therefore $\chi(N(v_{2}))\leq\sum_{i=1}^{3}\chi(E_{i}\cup
E_{i,i+1})\leq 3$.

Because $\chi(N(v_{2}))\leq 3$, $\chi(N(v_{2})\cup
N(v_{1}))\leq\chi(N(v_{1})-N(v_{2}))+\chi(N(v_{2}))\leq 1+3=4$. Consequently,
$\chi(G)\leq\chi(N(v_{1})\cup N(v_{2}))+\chi(\\{v_{1},v_{2}\\}\cup A)\leq
4+3$=7. ∎

Therefore, combining theorem1.1, theorem1.2 and theorem1.3, we obtain our
major theorem.

######  theorem.

If $G$ is $(P_{3}\cup P_{2},K_{4})$-free, then $\chi(G)\leq 7$.

Finally, we prove a simple theorem using the above theorem.

######  theorem.

(1.4) If $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$-free with order $n$ and
clique number $\omega$, then $n\leq 7\omega$ and $\chi(G)\leq 4\omega$.

Proof.

Suppose $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$-free.

If $\overline{G}$ is connected, then we apply the above theorem to obtain that
$\chi(\overline{G})\leq 7$. Therefore, $V(\overline{G})$ can be partitioned
into $7$ stable sets and hence $V(G)$ can be partitioned into $7$ cliques.
Therefore, $n\leq 7\omega$.

If $\overline{G}$ is not connnected, then there is $G_{1}$ such that
$G=G_{1}+G_{2}$ and hence $|V(G)|=|V(G_{1})|+|V(G_{2})|$. Such decomposition
will last until each $G_{i}$ satidfied $\overline{G_{i}}$ is connected.
Suppose $G=G_{1}+...G_{k}$. Since $V|G_{i}|\leq 7\omega(G_{i})$ and
$\omega=\sum_{j=1}^{k}\omega(G_{i})$, $|V(G)|=n\leq 7\omega$.

It is trivial that the complement of bipartite graph is perfect graph.
Therefore $V(G)$ can be partitioned into $3$ perfect graphs and one clique.
Therefore, $\chi(G)\leq 4\omega$.∎

##  4 acknowledge

I try to go further on $(P_{3}\cup P_{2},K_{4})$-free graphs. However, I fail
and 7 is the best upper bound I obtain. I know this is not a well-written
paper. If you are confused about some details in the proof, you can email me
at<EMAIL_ADDRESS>or<EMAIL_ADDRESS>
## References

  * [1] A. Bharathi,S. Choudum. Colouring of $(P_{3}\cup P_{2})$-free graphs.Graphs and Combinatorics 34(1):97–107,2018.
  * [2] L. Esperet, L. Lemoine, F. Maffray, and G. Morel. The chromatic number of $(P_{5},K_{4})$-free
  * [3] A. Gyárfás. On ramsey covering numbers. Coll. Math. Soc. János Bolyai, 10:801–816, 1973. graphs. Discrete Math, 313:743–754, 2013.
  * [4] T. Karthick and S. Mishra. Coloring ($P_{6}$, diamond, $K_{4}$)-free graphs.arXiv:1703.00606, 2017.
  * [5] Rui Li, Jinfeng Li and Di Wu. On the chromatic number of some ($P_{3}\cup P_{2}$)-free graphs, arXiv: 2308.15248, 2023.
  * [6] G. Serge and S. Huang. $(2P_{2},K_{4})$-Free Graphs are 4-Colorable. SIAM Joural on Discrete Mathematics 33:1095–1120,2019.