# On the construction of cospectral nonisomorphic bipartite graphs111The
contents of this article are included in the last author’s MS thesis [14].

M. Rajesh Kannan Department of Mathematics, Indian Institute of Technology
Kharagpur, Kharagpur 721 302, India. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Shivaramakrishna Pragada Department of Aerospace
Engineering, Indian Institute of Technology Kharagpur, Kharagpur 721 302,
India. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Hitesh Wankhede
Department of Mathematics, Indian Institute of Science Education and Research
Pune, Pune 411 008, India. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this article, we construct bipartite graphs which are cospectral for both
the adjacency and normalized Laplacian matrices using the notion of
partitioned tensor products. This extends the construction of Ji, Gong, and
Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the
proof of the bipartite case of Godsil and McKay’s construction [4], and shows
that the corresponding normalized Laplacian matrices are also cospectral. We
partially characterize the isomorphism in Godsil and McKay’s construction, and
generalize Ji et al.’s characterization of the isomorphism to biregular
bipartite graphs. The essential idea in characterizing the isomorphism uses
Hammack’s cancellation law as opposed to Hall’s marriage theorem used by Ji et
al.

AMS Subject Classification(2010): 05C50.

Keywords. Adjacency matrix, Normalized Laplacian matrix, Cospectral bipartite
graphs, Hammack’s cancellation law, Partitioned tensor product.

##  1 Introduction

We consider simple and undirected graphs. Let $G=(V(G),E(G))$ be a graph with
the vertex set $V(G)=\\{1,2,\ldots,n\\}$ and the edge set $E(G)$. If two
vertices $i$ and $j$ of $G$ are adjacent, we denote it by $i\sim j$. For a
graph $G$ on $n$ vertices, the adjacency matrix $A(G)=[a_{ij}]$ is the
$n\times n$ matrix defined by

$a_{ij}=\begin{cases}1,&\mbox{if}~{}\ i\sim j,\\\
0,&\mbox{otherwise}.\end{cases}$

The spectrum of a graph $G$ is the set of all eigenvalues of $A(G)$, with
corresponding multiplicities. Two graphs are cospectral for the adjacency
matrices if they have the same adjacency spectrum. It has been a longstanding
problem to characterize graphs that are determined by their spectrum [12, 13].
If any graph which is cospectral with $G$ is also isomorphic to it, then $G$
is said to be determined by its spectrum (DS graph for short), otherwise we
say that the graph $G$ has a cospectral mate or we say that $G$ is not
determined by its spectrum (NDS for short). To show that a graph is NDS, we
provide a construction of a cospectral mate. In [11], Schwenk proved that
almost all trees are NDS. In [5], Godsil and McKay provided a method for
constructing cospectral nonisomorphic graphs. In [12], van Dam and Haemers
mentioned that: If we were to bet, it would be for: ‘almost all graphs are
DS’. Later Haemers conjectured the same in [6]. For each vertex $i$ of a graph
$G$, let $d_{i}$ denote the degree of the vertex $i$. Let $D(G)$ denote the
diagonal  degree matrix whose $(i,i)$-th entry is $d_{i}$. Then the matrix
$L(G)=D(G)-A(G)$ is the Laplacian matrix of the graph $G$, and if $G$ has no
isolated vertices, then the matrix
$\mathcal{L}(G)=I-D(G)^{-\frac{1}{2}}A(G)D(G)^{-\frac{1}{2}}$ is the
normalized Laplacian matrix of $G$. The normalized Laplacian specturm of a
graph $G$ is the spectrum of $\mathcal{L}(G)$. Two graphs are cospectral for
the normalized Laplacian matrices if they have the same normalized Laplacian
spectrum. For more details, we refer to [1, 3, 5, 12, 13].

In [4], Godsil and McKay constructed cospectral graphs for the adjacency
matrices using the notion of partitioned tensor products of matrices (See
Section 2 for the definition). Recently, Ji, Gong, and Wang proposed a
construction for cospectral bipartite graphs for the adjacency and normalized
Laplacian matrices using the unfolding technique [9]. This construction is a
generalization of the unfoldings of a bipartite graph considered by Butler[2].
In this paper, first, we note that the proof of the construction of cospectral
bipartite graphs [9, Theorem 2.1] can be done by expressing the matrices
involved as the partitioned tensor products, and our proof works for larger
classes of graphs. This is done in Theorem 3.1 (for adjacency matrices) and
Theorem 3.3 (for normalized Laplacian matrices). Also, the proof of Theorem
3.1 provides an alternate proof of Godsil and McKay’s result for the bipartite
graphs.

Weichsel proved that if $G_{1}$ and $G_{2}$ are two connected bipartite
graphs, then their direct product $G_{1}\times G_{2}$ has exactly two
connected bipartite components [15]. Jha, Klavžar and Zmazek [8] showed that
if either $G_{1}$ or $G_{2}$ admits an automorphism that interchanges its
partite sets, then the components of $G_{1}\times G_{2}$ are isomorphic.
Hammack [7] proved that the converse is also true. Hammack’s proof uses a
cancellation property (see Theorem 2.2), which we call Hammack’s cancellation
law. Surprisingly, we are able to use this result to prove the isomorphism of
the cospectral graphs that we construct in Section 3. The characterization
theorem for isomorphism of Ji et al. [9, Theorem 3.1], is a particular case of
our result. Also, their proof uses Hall’s Marriage theorem, whereas we do not.

The outline of this paper is as follows: In Section 2, we include some needed
known results for graphs and matrices. In Section 3, the main results about
the construction of cospectral bipartite graphs for the adjacency and
normalized Laplacian matrices are stated and proved. Section 4 is devoted to
the study of the existence of isomorphisms between the cospectral pairs
constructed in Section 3.

##  2 Preliminaries

The notion of partitioned tensor products of matrices is used extensively in
this article. This is closely related to the well known Kronecker product of
matrices. The _Kronecker product_ of matrices $A=[a_{ij}]$ of size $m\times n$
and $B$ of size $p\times q$, denoted by $A\otimes B$, is the $mp\times nq$
block matrix $[a_{ij}B]$. The partitioned tensor product of two partitioned
matrices $M=\begin{bmatrix}U&V\\\ W&X\\\ \end{bmatrix}$ and
$H=\begin{bmatrix}A&B\\\ C&D\\\ \end{bmatrix}$, denoted by
$M\underline{\otimes}H$, is defined as $\begin{bmatrix}U\otimes A&V\otimes
B\\\ W\otimes C&X\otimes D\\\ \end{bmatrix}.$ Given the matrices $U$, $V$, $W$
and $X$, define $\mathcal{I}(U,X)=\begin{bmatrix}U&0\\\ 0&X\end{bmatrix}$ and
$\mathcal{P}(V,W)=\begin{bmatrix}0&V\\\ W&0\end{bmatrix}$ where $0$ is the
zero matrix of appropriate order. A $2\times 2$ block matrix is diagonal
(resp., an anti diagonal) block matrix if it is of the form $\mathcal{I}(U,X)$
(resp., $\mathcal{P}(V,W)$). The above notions were introduced by Godsil and
McKay [4]. The following proposition is easy to verify.

######  Proposition 2.1.

Let $Q$ and $R$ be the matrices of the form $\mathcal{I}(Q_{1},Q_{2})$ and
$\mathcal{I}(R_{1},R_{2})$, respectively. If $M=\begin{bmatrix}U&V\\\ W&X\\\
\end{bmatrix}$ and $H=\begin{bmatrix}A&B\\\ C&D\\\ \end{bmatrix}$ are $2\times
2$ block matrices, then

$(Q\underline{\otimes}R)(M\underline{\otimes}H)=(QM)\underline{\otimes}(RH).$

The same holds true when the matrices $Q$ and $R$ are both of the form
$\mathcal{P}(Q_{1},Q_{2})$ and $\mathcal{P}(R_{1},R_{2})$, respectively.

Two matrices $A$ and $B$ are said to be equivalent, if there exists invertible
matrices $P$ and $Q$ such that $Q^{-1}AP=B$. If the matrices $P$ and $Q$ are
orthogonal, then matrices $A$ and $B$ are said to be orthogonally equivalent.
If the matrices $P$ and $Q$ are permutation matrices, then matrices $A$ and
$B$ are said to be permutationally equivalent. Using the singular value
decomposition, it is easy to see that any square matrix is orthogonally
equivalent to its transpose.

A square matrix $A$ is said to be a PET matrix if it is permutationally
equivalent to its transpose. If the set of row sums of an $n\times n$ matrix
$A$ is different from the set of columns sums of $A$, then $A$ is non-PET.

We recall the cancellation law of matrices given by Hammack.

######  Theorem 2.2.

[7, Lemma 3] Let $A$, $B$ and $C$ be $(0,1)$-matrices. Let $C$ be a non-zero
matrix and $A$ be a square matrix with no zero rows. Then, the matrices
$C\otimes A$ and $C\otimes B$ are permutationally equivalent if and only if
$A$ and $B$ are permutationally equivalent. Similarly, the matrices $A\otimes
C$ and $B\otimes C$ are permutationally equivalent if and only if $A$ and $B$
are permutationally equivalent.

An isomorphism of two graphs $G_{1}$ and $G_{2}$ is a bijection
$f:V(G_{1})\longrightarrow V(G_{2})$ such that any two vertices $u$ and $v$
are adjacent in $G_{1}$ if and only if $f(u)$ and $f(v)$ are adjacent in
$G_{2}$. Two graphs $G_{1}$ and $G_{2}$ are isomorphic if there exists an
isomorphism between them. It is easy to see that $G_{1}$ and $G_{2}$ are
isomorphic if and only if the corresponding adjacency matrices are
permutationally similar. An automorphism of a graph $G$ is an isomorphism from
the graph $G$ to itself and the set of automorphisms $\operatorname{Aut}(G)$
of a graph is a group with respect to the composition of functions. Every
automorphism of a graph $G$ on $n$ vertices can be represented by an $n\times
n$ permutation matrix. Thus $\operatorname{Aut}(G)$ can be identified with the
set of permutation matrices $P$ such that $P^{T}A(G)P=A(G)$.

A graph $G$ is bipartite if its vertex set can be partitioned into two parts
$X$ and $Y$ such that every edge has one end in $X$ and the other end in $Y$.
We refer to $V(G)=X\cup Y$ as a bipartition of $G$, and $X$ and $Y$ as the
partite sets of $G$. A bipartite graph is balanced if its partite sets have
the same number of elements. If $G$ is a bipartite graph with the adjacency
matrix $\begin{bmatrix}0&B\\\ B^{T}&0\end{bmatrix}$, then the matrix $B$ is
the biadjacency matrix of $G$. Let $G_{1}$ and $G_{2}$ be two isomorphic
bipartite graphs, and let $V(G_{i})=X_{i}\cup Y_{i}$ be the bipartition of
$G_{i}$ for $i\in\\{1,2\\}$. An isomorphism $f$ from $G_{1}$ to $G_{2}$
respects the partite sets if it satisfies either $f(X_{1})=X_{2}$ and
$f(Y_{1})=Y_{2}$ or $f(X_{1})=Y_{2}$ and $f(Y_{1})=X_{2}$. If $G_{1}$ and
$G_{2}$ are two connected isomorphic bipartite graphs, then any isomorphism
between them respects the partite sets.

Let $G$ be a bipartite graph whose partite sets are $X$ and $Y$. An
automorphism $f$ of $G$ fixes the partite sets if $f(X)=X$ and $f(Y)=Y$, and
interchanges the partite sets if $f(X)=Y$ and $f(Y)=X$.

######  Definition 2.3.

[7] A connected bipartite graph has property $\pi$ if it admits an
automorphism that interchanges its partite sets.

The next proposition connects PET matrices to automorphisms of bipartite
graphs. We skip the proof.

######  Proposition 2.4.

Let $G$ be a bipartite graph with the adjacency matrix $\begin{bmatrix}0&B\\\
B^{T}&0\end{bmatrix}$. Then the biadjacency matrix $B$ is PET if and only if
there exists an automorphism $f\in\operatorname{Aut}(G)$ that interchanges its
partite sets, where the partite sets are induced by the biadjacency matrix
$B$.

The direct product or tensor product $G_{1}\times G_{2}$ of graphs $G_{1}$ and
$G_{2}$ is the graph with vertex set $V(G_{1})\times V(G_{2})$(the cartesian
product $V(G_{1})$ and $V(G_{2})$) and two vertices $(g,h)$ and
$(g^{\prime},h^{\prime})$ are adjacent in $G_{1}\times G_{2}$ if and only if
$g$ is adjacent to $g^{\prime}$ in $G_{1}$ and $h$ is adjacent to $h^{\prime}$
in $G_{2}$. The adjacency matrix of the graph $G_{1}\times G_{2}$ is given by
$A(G_{1})\otimes A(G_{2})$. Here $A(G_{i})$ denotes the adjacency matrix of
the graph $G_{i}$ (for $i=1,2$), and $\otimes$ denotes the Kronecker product.

##  3 Construction of the cospectral pairs

In this section, we give a construction of cospectral bipartite graphs for
both the adjacency and the normalized Laplacian matrices. Let $I_{m}$ and
$0_{n}$ denote the identity and zero matrices of orders $m$ and $n$,
respectively. Let $V$ be an $m\times n$ matrix and $B$ be a $p\times q$
matrix. Define the matrices $L=\begin{bmatrix}0&V\\\ V^{T}&0\end{bmatrix}$,
$H=\begin{bmatrix}0&B\\\ B^{T}&0\end{bmatrix}$ and
$H^{\\#}=\begin{bmatrix}0&B^{T}\\\ B&0\end{bmatrix}$. Note that the matrices
$L\underline{\otimes}H=\begin{bmatrix}0&V\otimes B\\\ V^{T}\otimes
B^{T}&0\end{bmatrix}$ and
$L\underline{\otimes}H^{\\#}=\begin{bmatrix}0&V\otimes B^{T}\\\ V^{T}\otimes
B&0\end{bmatrix}$ are of orders $mp+nq$ and $mq+np$, respectively.

For an $n\times n$ symmetric $(0,1)$ matrix $A$ with zero diagonal entries,
let $G_{A}$ denote the simple graph whose adjacency matrix is $A$. The $(0,1)$
matrices $V$, $B$ and $B^{T}$ are the biadjacency matrices for the bipartite
graphs $G_{L}$, $G_{H}$ and $G_{H^{\\#}}$, respectively. Since $H$ and
$H^{\\#}$ are permutationally similar, the graphs $G_{H}$ and $G_{H^{\\#}}$
are isomorphic. The next theorem is about a construction of cospectral graphs
for the adjacency matrices. The proof of this theorem could found in [4]. Our
proof gives an alternate simple proof for this result, and the proof idea
could be extended for normalized Laplacian matrices as well.

######  Theorem 3.1.

The bipartite graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are cospectral for the adjacency matrices if
and only if at least one of the bipartite graphs $G_{L}$ or $G_{H}$ is
balanced.

###### Proof.

First let us show if either $m=n$ or $p=q$, the matrices
$L\underline{\otimes}H$ and $L\underline{\otimes}H^{\\#}$ are orthogonally
similar, and hence they are cospectral.

Case 1: Let $m=n$. Then $V$ is a square matrix and $V$ is orthogonally
equivalent to $V^{T}$. Thus there exist two orthogonal matrices $R_{1}$ and
$R_{2}$ such that $R_{1}^{T}VR_{2}=V^{T}$. Define
$R=\mathcal{P}(R_{1},R_{2})$. Now,

$\displaystyle R^{T}LR=\begin{bmatrix}0&R_{1}\\\
R_{2}&0\end{bmatrix}^{T}\begin{bmatrix}0&V\\\
V^{T}&0\end{bmatrix}\begin{bmatrix}0&R_{1}\\\
R_{2}&0\end{bmatrix}=\begin{bmatrix}0&R_{2}^{T}V^{T}R_{1}\\\
R_{1}^{T}VR_{2}&0\end{bmatrix}$ $\displaystyle=\begin{bmatrix}0&V\\\
V^{T}&0\end{bmatrix}=L.$

Let $Q=\mathcal{P}(I_{p},I_{q})$ and $P=R\underline{\otimes}Q$. Then $Q$ is a
permutation matrix, $P$ is an orthogonal matrix and $Q$ satisfies
$Q^{T}HQ=H^{\\#}$. Now

$\displaystyle P^{T}(L\underline{\otimes}H)P$
$\displaystyle=(R\underline{\otimes}Q)^{T}(L\underline{\otimes}H)(R\underline{\otimes}Q)$
$\displaystyle=(R^{T}LR)\underline{\otimes}(Q^{T}HQ)$
$\displaystyle=L\underline{\otimes}H^{\\#}.$

Note that the second step uses Proposition 2.1. Thus
$G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$ are
cospectral. Case 2: Let $p=q$. Then the matrix $B$ is orthogonally equivalent
to $B^{T}$. Hence, there exist two orthogonal matrices $Q_{1}$ and $Q_{2}$
such that $Q_{1}^{T}BQ_{2}=B^{T}$. Let $Q=\mathcal{I}(Q_{1},Q_{2})$. Then
$Q^{T}HQ=H^{\\#}.$ Let $R=\mathcal{I}(I_{m},I_{n})$ and
$P=R\underline{\otimes}Q$. Then $R^{T}LR=L$. Rest of the proof of this case is
similar to that of Case 1.

Conversely, let the matrices $L\underline{\otimes}H$ and
$L\underline{\otimes}H^{\\#}$ have the same spectrum. Then $mp+nq=mq+np$, and
hence $(m-n)(p-q)=0$. Thus the result follows. ∎

Next, we establish an identity for the partitioned tensor product for the
normalized Laplacian matrices, which is useful in the construction of
cospectral graphs for the normalized Laplacian matrices.

######  Lemma 3.2.

Let $G_{1}$ and $G_{2}$ be two bipartite graphs with no isolated vertices. If
the matrices $A(G_{1})$ (resp., $A(G_{2})$) and $\mathcal{L}(G_{1})$ (resp.,
$\mathcal{L}(G_{2})$) are partitioned into $2\times 2$ matrices conformally
with the partite sets, then
$\mathcal{L}(G_{A(G_{1})\underline{\otimes}A(G_{2})})=2I-(\mathcal{L}(G_{1})\underline{\otimes}\mathcal{L}(G_{2}))$.

###### Proof.

Let $D({G_{1}})$ and $D({G_{2}})$ denote the degree matrices corresponding to
the graphs $G_{1}$ and $G_{2}$ respectively. Then,

$\displaystyle\mathcal{L}(G_{A(G_{1})\underline{\otimes}A(G_{2})})$
$\displaystyle=I-\bigg{(}D(G_{A(G_{1})\underline{\otimes}A(G_{2})})^{-1/2}(A(G_{1})\underline{\otimes}A(G_{2}))D(G_{A(G_{1})\underline{\otimes}A(G_{2})})^{-1/2}\bigg{)}$
$\displaystyle=I-\bigg{(}D(G_{1})^{-1/2}A(G_{1})D(G_{1})^{-1/2}\bigg{)}\underline{\otimes}\bigg{(}D(G_{2})^{-1/2}A(G_{2})D(G_{2})^{-1/2}\bigg{)}$
$\displaystyle=I-\bigg{(}(I-\mathcal{L}(G_{1}))\underline{\otimes}(I-\mathcal{L}(G_{2}))\bigg{)}$
$\displaystyle=2I-(\mathcal{L}(G_{1})\underline{\otimes}\mathcal{L}(G_{2})).\qed$

In the next theorem, we establish the cospectrality for the normalized
Laplacian matrices of partitioned tensor products graphs
$G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$.

######  Theorem 3.3.

Let $G_{L}$ and $G_{H}$ be two bipartite graphs with no isolated vertices. The
bipartite graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are cospectral for the normalized Laplacian
matrices if and only if at least one of $G_{L}$ or $G_{H}$ is balanced.

###### Proof.

Let $D(G_{L})$, $D(G_{H})$ and $D(G_{H^{\\#}})$ denote the degree matrices for
the graphs $G_{L}$, $G_{H}$ and $G_{H^{\\#}}$, respectively. Let either $m=n$
or $p=q$.

Case 1: Suppose $m=n$. Then $V$ is an $n\times n$ matrix. Let
$D(G_{L})=\mathcal{I}(C_{1},C_{2})$ where $C_{1}$ and $C_{2}$ are $n\times n$
diagonal degree matrices of the respective partite sets. Since $G_{L}$ does
not have any isolated vertices, $C_{1}^{-1/2}$ and $C_{2}^{-1/2}$ exist. Let
$E=C_{1}^{-1/2}VC_{2}^{-1/2}$. Then there exist two orthogonal matrices
$R_{1}$ and $R_{2}$ such that $E=R_{2}^{T}E^{T}R_{1}$. Set
$R=\mathcal{P}(R_{1},R_{2})$. Now,

$\displaystyle\mathcal{L}(G_{L})$
$\displaystyle=I-D(G_{L})^{-1/2}A(G_{L})D(G_{L})^{-1/2}$
$\displaystyle=I-\begin{bmatrix}0&E\\\ E^{T}&0\end{bmatrix}$
$\displaystyle=I-\begin{bmatrix}0&R_{2}^{T}E^{T}R_{1}\\\
R_{2}ER_{1}^{T}&0\end{bmatrix}$ $\displaystyle=\begin{bmatrix}0&R_{1}\\\
R_{2}&0\end{bmatrix}^{T}\left(I-\begin{bmatrix}0&E\\\
E^{T}&0\end{bmatrix}\right)\begin{bmatrix}0&R_{1}\\\ R_{2}&0\end{bmatrix}$
$\displaystyle=R^{T}\mathcal{L}(G_{L})R.$

The permutation matrix $Q=\mathcal{P}(I_{p},I_{q})$ satisfies
$Q^{T}\mathcal{L}(G_{H})Q=\mathcal{L}(G_{H^{\\#}})$, and
$P=R\underline{\otimes}Q$ is an orthogonal matrix. By Proposition 2.1, it
follows that
$P^{T}(\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H}))P=\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H^{\\#}})$.

Case 2: Suppose $p=q$. Then $B$ is a $p\times p$ matrix. Let
$D(G_{H})=\mathcal{I}(D_{1},D_{2})$ where $D_{1}$ and $D_{2}$ are $p\times p$
diagonal matrices. Then, $D(G_{H^{\\#}})=\mathcal{I}(D_{2},D_{1})$. Since
$G_{H}$ does not have any isolated vertices, $D_{1}^{-1/2}$ and $D_{2}^{-1/2}$
exist. Let $F=D_{1}^{-1/2}BD_{2}^{-1/2}$. Then there exist two orthogonal
matrices $Q_{1}$ and $Q_{2}$ such that $Q_{1}^{T}FQ_{2}=F^{T}$. Let
$Q=\mathcal{I}(Q_{1},Q_{2})$, $R$ be the identity matrix such that
$R^{T}\mathcal{L}(G_{L})R=\mathcal{L}(G_{L})$ and $P=R\underline{\otimes}Q$.
Then
$P^{T}(\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H}))P=\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H^{\\#}})$.

In both the cases, the matrices
$\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H})$ and
$\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H^{\\#}})$ are
orthogonally similar. By Lemma 3.2, we have
$\mathcal{L}(G_{L\underline{\otimes}H})=2I-\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H})$
and
$\mathcal{L}(G_{L\underline{\otimes}H^{\\#}})=2I-\mathcal{L}(G_{L})\underline{\otimes}\mathcal{L}(G_{H^{\\#}})$.
Then the matrices $\mathcal{L}(G_{L\underline{\otimes}H})$ and
$\mathcal{L}(G_{L\underline{\otimes}H^{\\#}})$ are orthogonally similar, and
hence they are cospectral.

Converse is easy to verify. ∎

######  Remark 3.4.

By taking $V=J_{m,n},J_{1,n}$, and $J_{1,2}$, in Theorem 3.1 and Theorem 3.3,
we get the constructions of Ji et al. given in [9, Theorem 2.1], Kannan and
Pragada given in [10, Theorem 3.1], and Butler given in [2, Theorem 2.1],
respectively.

##  4 Property $\eta$ and Isomorphism

We assume from here on that the bipartite graphs $G_{L}$ and $G_{H}$ have no
isolated vertices, and they are not necessarily connected. In this section, we
investigate the existence of isomorphism between the cospectral pair obtained
in Theorem 3.1 and Theorem 3.3. We show that, under appropriate restrictions,
the isomorphism is closely related to the PET matrices and the automorphisms
of bipartite graphs.

If a bipartite graph $G$ is disconnected, then $G$ has more than one
bipartition. Next we extend the property $\pi$ for disconnected bipartite
graphs. Let $G$ be a bipartite graph with biadjacency matrix $B$. We say that
$G$ has property $\pi$ with respect to $B$, if $B$ is a PET matrix. We define
the canonical partite sets of the partitioned tensor product graph
$G_{L\underline{\otimes}H}$ (resp., $G_{L\underline{\otimes}H^{\\#}}$) to be
the bipartition induced by the biadjacency matrix $V\otimes B$ (resp.,
$V\otimes B^{T}$), where $V$ and $B$ are biadjacency matrices of $G_{L}$ and
$G_{H}$, respectively.

The next theorem connects the property $\pi$ with the isomorphism between the
graphs $G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$.

######  Theorem 4.1.

Let $G_{L}$ and $G_{H}$ be bipartite graphs (not necessarily connected) with
biadjacency matrices $V$ and $B$, respectively. Then the following statements
are equivalent:

  * (a)

There exists an isomorphism between the graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ which respects the partite sets of the
canonical bipartitions.

  * (b)

At least one of $G_{L}$ or $G_{H}$ has property $\pi$.

###### Proof.

(a)$\implies$(b) By assumption, there exists a permutation matrix $P$ of the
form either $\mathcal{I}(P_{1},P_{4})$ or $\mathcal{P}(P_{2},P_{3})$, where
$P_{i}$ is a permutation matrix for $i\in\\{1,2,3,4\\}$, such that

$P^{T}\begin{bmatrix}0&V\otimes B\\\ V^{T}\otimes
B^{T}&0\end{bmatrix}P=\begin{bmatrix}0&V\otimes B^{T}\\\ V^{T}\otimes
B&0\end{bmatrix}.$

If $P=\mathcal{I}(P_{1},P_{4})$, then $P_{1}^{T}(V\otimes B)P_{4}=V\otimes
B^{T}$. The matrices $V\otimes B$ and $V\otimes B^{T}$ are permutationally
equivalent. Then, by Theorem 2.2, $B$ is PET. If $P=\mathcal{P}(P_{2},P_{3})$,
then $P_{3}^{T}(V^{T}\otimes B^{T})P_{2}=V\otimes B^{T}$. Hence $V$ is PET.

(b)$\implies$(a) Let either $G_{L}$ or $G_{H}$ has property $\pi$. Suppose
$G_{L}$ has the property $\pi$, that is, $G_{L}$ admits an automorphism that
interchanges its partite sets. Then, there exist two permutation matrices
$R_{2}$ and $R_{3}$ such that $R^{T}LR=L$ where $R=\mathcal{P}(R_{2},R_{3})$.
Set $Q=\mathcal{P}(I_{p},I_{q})$ and $P=R\underline{\otimes}Q$. Then
$Q^{T}HQ=H^{\\#}$, and

$\displaystyle P^{T}(L\underline{\otimes}H)P$
$\displaystyle=(R\underline{\otimes}Q)^{T}(L\underline{\otimes}H)(R\underline{\otimes}Q)$
$\displaystyle=(R^{T}LR)\underline{\otimes}(Q^{T}HQ)$
$\displaystyle=L\underline{\otimes}H^{\\#}.$

Thus the graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are isomorphic, and the isomorphism induced
by the permutation matrix $P$ respects the partite sets.

Proof idea of the other case is similar. ∎

Weichsel proved that if $G_{L}$ and $G_{H}$ are two connected bipartite
graphs, then $G_{L}\times G_{H}$ has exactly two connected bipartite
components [15]. Godsil and McKay noted that the disjoint union of the
bipartite graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ is the direct product $G_{L}\times G_{H}$
[4]. Hence, if $G_{L}$ and $G_{H}$ are connected, then the two connected
components of $G_{L\otimes H}$ are $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$. Using these observations, we obtain
Hammack’s result as a corollary of Theorem 4.1.

######  Corollary 4.2.

[7, Theorem 1] Suppose $G_{1}$ and $G_{2}$ are connected bipartite graphs. The
two components of $G_{1}\times G_{2}$ are isomorphic if and only if at least
one of $G_{1}$ or $G_{2}$ has the property $\pi.$

The bipartite graphs constructed by Ji, Gong and Wang have the property that
any isomorphism between them respects the partite sets [9, Lemma 3.2]. From
Theorem 4.1, we observe that respecting partite sets is the key property for
characterizing isomorphism in terms of PET matrices (property $\pi$). To this
end, we define property $\eta$, which relaxes the connectedness assumption in
the Hammack’s result and includes a broader class of bipartite graphs.

######  Definition 4.3.

Two bipartite graphs $G_{L}$ and $G_{H}$ are said to have property $\eta$, if
whenever the bipartite graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are isomorphic, there exists an isomorphism
between $G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$ that
respects the partite sets of the canonical bipartitions.

Next we show that any pair of connected bipartite graphs have property $\eta$
and thus property $\eta$ is relaxation of connectedness requirement from
Hammack’s result [7, Theorem 1].

######  Theorem 4.4.

Let $G_{L}$ and $G_{H}$ be connected bipartite graphs. Then, they have
property $\eta$.

###### Proof.

Suppose $G_{L}$ and $G_{H}$ are connected, and $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are isomorphic. Since
$G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$ are
connected bipartite graphs, thus any isomorphism between them respects the
partite sets. Hence $G_{L}$ and $G_{H}$ have property $\eta$. ∎

A biregular bipartite graph is a bipartite graph $G$ for which any two
vertices in the same partite sets have the same degree as each other. If
degree of the vertices in one of the partite sets is $k$ and degree of the
vertices in the other partite set is $l$, then the graph is said to be
$(k,l)$-biregular. We say that a biregular bipartite graph has distinct
degrees if $k\neq l$. Next we prove that property $\eta$ is satisfied if one
of the bipartite graphs is biregular with distinct degrees.

######  Theorem 4.5.

Let $G_{L}$ and $G_{H}$ be bipartite graphs. If $G_{L}$ is a non-empty
$(k,l)$-regular bipartite graph with $k\neq l$, then $G_{L}$ and $G_{H}$ have
property $\eta$.

###### Proof.

Let the graphs $\Gamma_{1}=G_{L\underline{\otimes}H}$ and
$\Gamma_{2}=G_{L\underline{\otimes}H^{\\#}}$ be isomorphic. Then, $\Gamma_{1}$
and $\Gamma_{2}$ are cospectral. By Theorem 3.1, the graph $G_{H}$ is
balanced, since $G_{L}$ cannot be balanced as $k\neq l$.

Let $V(\Gamma_{i})=X_{i}\cup Y_{i}$ be the canonical vertex partitions of the
graphs $\Gamma_{i}$ for $i={1,2}$. Without loss of generality, assume that
$k<l$. Let $f$ be an isomorphism from $\Gamma_{1}$ to $\Gamma_{2}$. Let
$b_{i}$ and $b_{i}^{\prime}$ denote the $i^{th}$ row sum of the matrices $B$
and $B^{T}$, respectively. Let $x_{1}$ be the vertex of maximum degree in
$X_{1}$. Suppose that $f(x_{1})\in Y_{2}$. Then $d_{\Gamma_{1}}(x_{1})=lb_{i}$
for some $1\leq i\leq p$, and $d_{\Gamma_{2}}(f(x_{1}))=kb_{j}$ for some
$1\leq j\leq p$. Since the isomorphism preserves the degrees, we have
$lb_{i}=kb_{j}$. Since $x_{1}$ has maximum degree in $X_{1}$, $b_{i}\geq
b_{j}$ for any $1\leq j\leq p$, and hence $kb_{j}\geq lb_{j}$. If $b_{j}\neq
0$, then $k\geq l$, a contradiction to the initial assumption that $k<l$.
Hence, if $x_{1}\in X_{1}$, then $f(x_{1})\in X_{2}$. If $b_{j}=0$ then
$lb_{i}=kb_{j}$, $b_{i}=0$. But $x_{1}$ is a vertex of maximum degree $lb_{i}$
in the set $X_{1}$ and thus $B=0$. So we could choose $f(x_{1})\in X_{2}$. In
any case, $f(x_{1})\in X_{2}$.

Let $x_{1},\ldots,x_{rm}$ be the vertices of $X_{1}$ with the same maximum
degree such that
$d_{\Gamma_{1}}(x_{1+(s-1)m})=\ldots=d_{\Gamma_{1}}(x_{m+(s-1)m})=lb_{i_{s}}$
for $s\in\\{1,2,\ldots,r\\}$ where $b_{i_{1}}=\ldots=b_{i_{r}}$ for $1\leq
i_{1},\ldots,i_{r}\leq p$. Then, using the previous argument,
$f(x_{1}),\ldots,f(x_{rm})\in X_{2}$ such that
$d_{\Gamma_{2}}(f(x_{1+(s-1)m}))=\ldots=d_{\Gamma_{2}}(f(x_{m+(s-1)m}))=lb^{\prime}_{j_{s}}$
for $s\in\\{1,2,\ldots,r\\}$ where
$b_{j_{1}}^{\prime}=\ldots=b_{j_{r}}^{\prime}$ for $1\leq
j_{1},\ldots,j_{r}\leq p$. Define $B{{}^{\prime}}$ to be the matrix obtained
by removing the $i_{s}^{th}$ row and $j_{s}^{th}$ column of $B$ for all
$s\in\\{1,2,\ldots,r\\}$. Define $\Gamma_{1}^{\prime}$ and
$\Gamma_{2}^{\prime}$ to be the induced bipartite graphs corresponding to the
biadjacency matrices $V\otimes B{{}^{\prime}}$ and $V\otimes
B{{}^{\prime}}^{T}$, respectively. Since $\Gamma_{1}^{\prime}$ and
$\Gamma_{2}^{\prime}$ are isomorphic as well, apply the same argument for
$\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$ until all the rows and columns
of $B$ are exhausted. Thus $f(X_{1})=X_{2}$ and hence $f(Y_{1})=Y_{2}$.

Similarly, if $k>l$, then consider the set of vertices of maximum degree in
$Y_{1}$ and show that $f(Y_{1})=Y_{2}$ and hence $f(X_{1})=X_{2}$. Hence,
$G_{L}$ and $G_{H}$ satisfy property $\eta$. ∎

Note that at each step, the vertices from both the partite sets of the induced
bipartite graphs of $\Gamma_{1}$ and $\Gamma_{2}$ are being removed. This is
justified since our motive is to first show just $f(X_{1})=X_{2}$. Ji, Gong
and Wang in Lemma 3.2. [9] remove vertices from only $X_{1}$ and $X_{2}$ at
each step.

Since we are interested in the construction of cospectral nonisomorphic
graphs, we use this result to construct cospectral graphs that are not
isomorphic.

######  Theorem 4.6.

Let $G_{L}$ and $G_{H}$ be bipartite graphs. Let $G_{L}$ be a biregular
bipartite graph with distinct degrees and let $G_{H}$ be balanced. Then the
graphs $G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$ are
nonisomorphic if and only if $G_{H}$ does not admit an automorphism that
interchanges its partite sets.

###### Proof.

Since $G_{L}$ is a biregular bipartite graph with distinct degrees, the
corresponding $m\times n$ biadjacency matrix $V$ has constant row sum $k$ and
constant column sum $l$. Since the sum of row sums must be the same as the sum
of column sums, we have $km=ln$. But $k\neq l$, hence $m\neq n$. Hence,
$G_{L}$ has unequal partition sizes. Since $G_{H}$ has equal partition sizes,
by Theorem 3.1 and Theorem 3.3, the graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are cospectral. Now, as $G_{L}$ has unequal
partitions sizes, it doesn’t admit an automorphism that interchanges its
partite sets. Hence, the condition for non-isomorphism follows from Theorems
4.1 and 4.5. ∎

Now as a corollary, we obtain the result of Ji, Gong and Wang.

######  Corollary 4.7.

[9, Theorem 3.1] Let $V=J_{m,n}$ such that $m\neq n$ and let $B$ is a square
matrix. Then, the bipartite graphs $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$ are cospectral for the adjacency as well as
the normalized Laplacian matrices, and they are isomorphic if and only if $B$
is PET.

###### Proof.

Since $V=J_{m,n}$ and $m\neq n$, the corresponding bipartite graph $G_{L}$ is
a biregular bipartite graph with distinct degrees. Hence, the result follows
from Theorem 4.6. ∎

Now, let us illustrate the construction given in Theorem 4.6 with an example.

######  Example.

The following pair of matrices $V$ and $B$ satisfy all the conditions stated
in Theorem 4.5 and corresponding graphs are illustrated below.

$\displaystyle V=\begin{bmatrix}1&0\\\ 1&0\\\ 0&1\\\ 0&1\end{bmatrix}\text{and
}\;B=\begin{bmatrix}1&1&0\\\ 1&0&1\\\ 1&0&0\end{bmatrix}.$

In the following figure, $G_{L}$ and $G_{H}$ denote the bipartite graphs with
biadjacency matrices $V$ and $B$, respectively. The graphs
$G_{L\underline{\otimes}H}$ and $G_{L\underline{\otimes}H^{\\#}}$ are the
cospectral nonisomorphic pairs. Note that this example of cospectral bipartite
graphs is not obtainable from the results of Ji et al. and Hammack.

Figure 1: $G_{L}$, $G_{H}$, $G_{L\underline{\otimes}H}$ and
$G_{L\underline{\otimes}H^{\\#}}$

### Acknowledgment:

We are indebted to the referees for the comments and suggestions. M. Rajesh
Kannan would like to thank the Department of Science and Technology, India,
for financial support through the projects MATRICS (MTR/2018/000986).

## References

  * [1] Andries E. Brouwer and Willem H. Haemers.  Spectra of graphs.  Universitext. Springer, New York, 2012.
  * [2] Steve Butler.  A note about cospectral graphs for the adjacency and normalized Laplacian matrices.  Linear Multilinear Algebra, 58(3-4):387–390, 2010.
  * [3] Fan R. K. Chung.  Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.
  * [4] Chris D. Godsil and Brendan D. McKay.  Products of graphs and their spectra.  In Combinatorial mathematics, IV (Proc. Fourth Australian Conf., Univ. Adelaide, Adelaide, 1975), pages 61–72. Lecture Notes in Math., Vol. 560, 1976.
  * [5] Chris D. Godsil and Brendan D. McKay.  Constructing cospectral graphs.  Aequationes Math., 25(2-3):257–268, 1982.
  * [6] Willem H. Haemers.  Are almost all graphs determined by their spectrum?  Not. S. Afr. Math. Soc., 47(1):42–45, 2016.
  * [7] Richard H. Hammack.  Proof of a conjecture concerning the direct product of bipartite graphs.  European J. Combin., 30(5):1114–1118, 2009.
  * [8] Pranava K. Jha, Sandi Klavžar, and Blaž Zmazek.  Isomorphic components of Kronecker product of bipartite graphs.  Discuss. Math. Graph Theory, 17(2):301–309, 1997.
  * [9] Yizhe Ji, Shicai Gong, and Wei Wang.  Constructing cospectral bipartite graphs.  Discrete Math., 343(10):112020, 7, 2020.
  * [10] M. Rajesh Kannan and Shivaramakrishna Pragada.  On the construction of cospectral graphs for the adjacency and the normalized Laplacian matrices.  Linear and Multilinear Algebra, 0(0):1–22, September 2020.
  * [11] Allen J. Schwenk.  Almost all trees are cospectral.  In New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), pages 275–307, 1973.
  * [12] Edwin R. van Dam and Willem H. Haemers.  Which graphs are determined by their spectrum?  volume 373, pages 241–272. 2003.  Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002).
  * [13] Edwin R. van Dam and Willem H. Haemers.  Developments on spectral characterizations of graphs.  Discrete Math., 309(3):576–586, 2009.
  * [14] Hitesh Wankhede.  Constructing cospectral graphs using partitioned tensor product.  MS Thesis. IISER Pune, 2021.
  * [15] Paul M. Weichsel.  The Kronecker product of graphs.  Proc. Amer. Math. Soc., 13:47–52, 1962.


# This is the title

INDEFINITE HALMOS, EGERVARY AND SZ.-NAGY DILATIONS
K. MAHESH KRISHNA
Post Doctoral Fellow

Statistics and Mathematics Unit

Indian Statistical Institute, Bangalore Centre

Karnataka 560 059, India

Email<EMAIL_ADDRESS>
Date:

Abstract: Let $\mathcal{M}$ be an indefinite inner product module over a
*-ring of characteristic 2. We show that every self-adjoint operator on
$\mathcal{M}$ admits Halmos, Egervary and Sz.-Nagy dilations.

Keywords: Dilation, Indefinite inner product space, Module.

Mathematics Subject Classification (2020): 47A20, 16D10, 46C20.

##  1\. Introduction

In 1950, Halmos [22] made a deep insight into structure theory of operators on
Hilbert space by exhibiting any contraction as a part of a unitary. In 1953,
Sz.-Nagy [39] showed that Halmos result can be extended to powers of
contractions using a unitary operator. In 1963, T. Ando [5] showed that there
is a version of Sz.-Nagy dilation for commuting contractions. Combined with
spectral theory and theory of (several) complex variables, today, dilation
theory of contractions is a rapidly evolving area of research and for a
comprehensive look, we refer [36, 41, 5, 32, 33, 35, 4, 1, 13, 42, 27, 6, 37,
21, 20, 19, 15, 34, 7, 9, 16, 10, 40, 31, 14, 12, 28, 43, 11]. Started in
1970’s, dilations of contractions acting on Lebesgue spaces and Banach spaces
followed Hilbert space developments [17, 2, 38, 30, 3, 24, 18].

In 2021, by identifying essential mechanisms of dilation theory, Bhat, De and
Rakshit [8] obtained surprising results in the set theory context and vector
spaces. In 2022, further study in the context of vector spaces was carried by
Krishna and Johnson [26]. We note that another vector space variant is also
studied by Han, Larson, Liu and Liu [23]. Recently Krishna introduced the
notion of magic contractions and derived Sz.-Nagy dilation for p-adic Hilbert
spaces and modules [25].

In this paper, we derive indefinite inner product module versions of Halmos
dilation (Theorem 2.2), Egervary N-dilation (Theorem 2.3), Sz.-Nagy dilation
(Theorem 2.4). Our article is highly motivated from the paper of Halmos [22],
Egervary [16], Schaffer [36], Sz.-Nagy [39], Bhat, De and Rakshit [8], Krishna
and Johnson [26] and Krishna [25].

##  2\. Indefinite Halmos, Egervary and Sz.-Nagy Dilations

We are going to use the following notions. A ring $\mathcal{R}$ with an
automorphism $*$ which is either identity or of order 2 is called as an
*-ring. Throughout the paper we assume that characteristic of ring is 2.

######  Definition 2.1.

[29] Let $\mathcal{V}$ be a module over $\mathcal{R}$. We say that
$\mathcal{V}$ is an indefinite inner product module (we write IIPM) if there
is a map (called as indefinite inner product)
$\langle\cdot,\cdot\rangle:\mathcal{V}\times\mathcal{V}\to\mathcal{R}$
satisfying following.

  1. (i)

If $x\in\mathcal{V}$ is such that $\langle x,y\rangle=0$ for all
$y\in\mathcal{V}$, then $x=0$.

  2. (ii)

$\langle x,y\rangle=\langle y,x\rangle^{*}$ for all $x,y\in\mathcal{V}$.

  3. (iii)

$\langle\alpha x+y,z\rangle=a\langle x,z\rangle+\langle y,z\rangle$ for all
$a\in\mathcal{R}$, for all $x,y,z\in\mathcal{V}$.

Let $\mathcal{V}$ be a IIPM and $T:\mathcal{V}\to\mathcal{V}$ be a morphism.
We say that $T$ is adjointable if there is a morphism, denoted by
$T^{*}:\mathcal{V}\to\mathcal{V}$ such that $\langle Tx,y\rangle=\langle
x,T^{*}y\rangle$, $\forall x,y\in\mathcal{V}$. Note that (i) in Definition 2.1
says that adjoint, if exists, is unique. An adjointable morphism $U$ is said
to be a unitary if $UU^{*}=U^{*}U=I_{\mathcal{V}}$, the identity operator on
$\mathcal{V}$. An adjointable morphism $P$ is said to be projection if
$P^{2}=P^{*}=P$. An adjointable morphism $T$ is said to be an isometry if
$T^{*}T=I_{\mathcal{V}}$. An adjointable morphism $T$ is said to be self-
adjoint if $T^{*}=T$. We denote the identity operator on $\mathcal{V}$ by
$I_{\mathcal{V}}$.

Our first result is the indefinite Halmos dilation.

######  Theorem 2.2.

(Indefinite Halmos dilation) Let $\mathcal{V}$ be a IIPM over a *-ring of
characteristic 2 and $T:\mathcal{V}\to\mathcal{V}$ be a self-adjoint morphism.
Then the morphism

$\displaystyle U\coloneqq\begin{pmatrix}T&I_{\mathcal{V}}+T\\\
I_{\mathcal{V}}+T&T\\\ \end{pmatrix}$

is unitary on $\mathcal{V}\oplus\mathcal{V}$. In other words,

$\displaystyle T=P_{\mathcal{V}}U|_{\mathcal{V}},\quad
T^{*}=P_{\mathcal{V}}U^{*}|_{\mathcal{V}},$

where $P_{\mathcal{V}}:\mathcal{V}\oplus\mathcal{V}\ni(x,y)\mapsto
x\in\mathcal{V}$.

###### Proof.

A direct calculation says that

$\displaystyle V\coloneqq\begin{pmatrix}T&I_{\mathcal{V}}+T\\\
I_{\mathcal{V}}+T&T\\\ \end{pmatrix}$

is the inverse and adjoint of $U$. ∎

Our second result is the indefinite Egervary N-dilation.

######  Theorem 2.3.

(Indefinite Egervary N-dilation) Let $\mathcal{V}$ be a IIPM over a *-ring of
characteristic 2 and $T:\mathcal{V}\to\mathcal{V}$ be a self-adjoint morphism.
Let $N$ be a natural number. Then the morphism

$\displaystyle U\coloneqq\begin{pmatrix}T&0&0&\cdots&0&0&I_{\mathcal{V}}+T\\\
I_{\mathcal{V}}+T&0&0&\cdots&0&0&T\\\ 0&I_{\mathcal{V}}&0&\cdots&0&0&0\\\
0&0&I_{\mathcal{V}}&\cdots&0&0&0\\\
\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots\\\ 0&0&0&\cdots&0&0&0\\\
0&0&0&\cdots&I_{\mathcal{V}}&0&0\\\ 0&0&0&\cdots&0&I_{\mathcal{V}}&0\\\
\end{pmatrix}_{(N+1)\times(N+1)}$

is unitary on $\oplus_{k=1}^{N+1}\mathcal{V}$ and

(1) $\displaystyle T^{k}=P_{\mathcal{V}}U^{k}|_{\mathcal{V}},\quad\forall
k=1,\dots,N,\quad(T^{*})^{k}=P_{\mathcal{V}}(U^{*})^{k}|_{\mathcal{V}},\quad\forall
k=1,\dots,N,$

where
$P_{\mathcal{V}}:\oplus_{k=1}^{N+1}\mathcal{V}\ni(x_{k})_{k=1}^{N+1}\mapsto
x_{1}\in\mathcal{V}$.

###### Proof.

A direct calculation of power of $U$ gives Equation (1). To complete the
proof, now we need show that $U$ is unitary. Define

$\displaystyle V\coloneqq\begin{pmatrix}T&I_{\mathcal{V}}+T&0&\cdots&0&0&0\\\
0&0&I_{\mathcal{V}}&\cdots&0&0&0\\\ 0&0&0&\cdots&0&0&0\\\
0&0&0&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&0&I_{\mathcal{V}}&0\\\ 0&0&0&\cdots&0&0&I_{\mathcal{V}}\\\
I_{\mathcal{V}}+T&T&0&\cdots&0&0&0\\\ \end{pmatrix}_{(N+1)\times(N+1)}.$

Then $UV=VU=I_{\oplus_{k=1}^{N+1}\mathcal{V}}$ and $U^{*}=V$. ∎

Note that the Equation (1) holds only upto $N$ and not for $N+1$ and higher
natural numbers. In the following theorem, given a IIPM $\mathcal{V}$,
$\oplus_{n=-\infty}^{\infty}\mathcal{V}$ is the IIPM defined by

$\displaystyle\oplus_{n=-\infty}^{\infty}\mathcal{V}\coloneqq\\{\\{x_{n}\\}_{n=-\infty}^{\infty},x_{n}\in\mathcal{V},\forall
n\in\mathbb{Z},x_{n}\neq 0\text{ only for finitely many
}n^{\prime}\text{s}\\}$

equipped with inner product

$\displaystyle\langle\\{x_{n}\\}_{n=-\infty}^{\infty},\\{y_{n}\\}_{n=-\infty}^{\infty}\rangle\coloneqq\sum_{n=-\infty}^{\infty}\langle
x_{n},y_{n}\rangle,\quad\forall\\{x_{n}\\}_{n=-\infty}^{\infty},\\{y_{n}\\}_{n=-\infty}^{\infty}\in\oplus_{n=-\infty}^{\infty}\mathcal{V}.$

Our third result is the indefinite Sz.-Nagy dilation.

######  Theorem 2.4.

(Indefinite Sz.-Nagy dilation) Let $\mathcal{V}$ be a IIPM over a *-ring of
characteristic 2 and $T:\mathcal{V}\to\mathcal{V}$ be a self-adjoint morphism.
Let $U\coloneqq(u_{n,m})_{-\infty\leq n,m\leq\infty}$ be the morphism defined
on $\oplus_{n=-\infty}^{\infty}\mathcal{V}$ given by the infinite matrix
defined as follows:

$\displaystyle u_{0,0}\coloneqq T,\quad u_{0,1}\coloneqq
I_{\mathcal{V}}+T,\quad u_{-1,0}\coloneqq I_{\mathcal{V}}+T,\quad
u_{-1,1}\coloneqq T,$ $\displaystyle u_{n,n+1}\coloneqq
I_{\mathcal{V}},\quad\forall n\in\mathbb{Z},n\neq 0,1,\quad u_{n,m}\coloneqq
0\quad\text{ otherwise},$

i.e.,

$\displaystyle U=\begin{pmatrix}&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\cdots&I_{\mathcal{V}}&0&0&0&0&0&\cdots&\\\
\cdots&0&I_{\mathcal{V}}&0&0&0&0&\cdots&\\\
\cdots&0&0&I_{\mathcal{V}}+T&T&0&0&\cdots&\\\
\cdots&0&0&\boxed{T}&I_{\mathcal{V}}+T&0&0&\cdots&\\\
\cdots&0&0&0&0&I_{\mathcal{V}}&0&\cdots&\\\
\cdots&0&0&0&0&0&I_{\mathcal{V}}&\cdots&\\\
&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\end{pmatrix}_{\infty\times\infty}$

where $T$ is in the $(0,0)$ position (which is boxed), is unitary on
$\oplus_{n=-\infty}^{\infty}\mathcal{V}$ and

(2) $\displaystyle T^{n}=P_{\mathcal{V}}U^{n}|_{\mathcal{V}},\quad\forall
n\in\mathbb{N},\quad(T^{*})^{n}=P_{\mathcal{V}}(U^{*})^{n}|_{\mathcal{V}},\quad\forall
n\in\mathbb{N},$

where
$P_{\mathcal{V}}:\oplus_{n=-\infty}^{\infty}\mathcal{V}\ni(x_{n})_{n=-\infty}^{\infty}\mapsto
x_{0}\in\mathcal{V}$.

###### Proof.

We get Equation (2) by calculation of powers of $U$. The matrix
$V\coloneqq(v_{n,m})_{-\infty\leq n,m\leq\infty}$ defined by

$\displaystyle v_{0,0}\coloneqq T,\quad v_{0,-1}\coloneqq
I_{\mathcal{V}}+T,\quad v_{1,0}\coloneqq I_{\mathcal{V}}+T,\quad
v_{1,-1}\coloneqq T,$ $\displaystyle v_{n,n-1}\coloneqq
I_{\mathcal{V}},\quad\forall n\in\mathbb{Z},n\neq 0,1,\quad v_{n,m}\coloneqq
0\quad\text{ otherwise},$

i.e.,

$\displaystyle V=\begin{pmatrix}&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\cdots&I_{\mathcal{V}}&0&0&0&0&0&\cdots&\\\
\cdots&0&I_{\mathcal{V}}&0&0&0&0&\cdots&\\\
\cdots&0&0&I_{\mathcal{V}}+T&\boxed{T}&0&0&\cdots&\\\
\cdots&0&0&T&I_{\mathcal{V}}+T&0&0&\cdots&\\\
\cdots&0&0&0&0&I_{\mathcal{V}}&0&\cdots&\\\
\cdots&0&0&0&0&0&I_{\mathcal{V}}&\cdots&\\\
&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\end{pmatrix}_{\infty\times\infty}$

where $T$ is in the $(0.0)$ position (which is boxed), satisfies
$UV=VU=I_{\oplus_{n=-\infty}^{\infty}\mathcal{V}}$ and $U^{*}=V$. ∎

We note that explicit sequential form of $U$ is

$\displaystyle
U(x_{n})_{n=-\infty}^{\infty}=(\dots,x_{-2},x_{-1},(I_{\mathcal{V}}+T)x_{0}+Tx_{1},\boxed{Tx_{0}+(I_{\mathcal{V}}+T)x_{1}},x_{2},x_{2},\dots)$

where $Tx_{0}+(I_{\mathcal{V}}+T)x_{1}$ is in the $0$ position (which is
boxed) and $U^{*}$ is

$\displaystyle
U^{*}(x_{n})_{n=-\infty}^{\infty}=(\dots,x_{-3},x_{-2},\boxed{(I_{\mathcal{V}}+T)x_{-1}+Tx_{0}},Tx_{-1}+(I_{\mathcal{V}}+T)x_{0},x_{1},\dots),$

where $(I_{\mathcal{V}}+T)x_{-1}+Tx_{0}$ is in the $0$ position (which is
boxed). We next wish to derive indefinite isometric Sz.-Nagy dilation.

######  Theorem 2.5.

(Indefinite isometric Sz.-Nagy dilation) Let $\mathcal{V}$ be a IIPM over a
*-ring of characteristic 2 and $T:\mathcal{V}\to\mathcal{V}$ be a self-adjoint
morphism. Let $U\coloneqq(u_{n,m})_{0\leq n,m\leq\infty}$ be the morphism
defined on $\oplus_{n=0}^{\infty}\mathcal{V}$ given by the infinite matrix
defined as follows:

$\displaystyle u_{0,0}\coloneqq T,\quad u_{2,1}\coloneqq
I_{\mathcal{V}}+T,\quad u_{n+1,n}\coloneqq I_{\mathcal{V}},\quad\forall n\geq
2,\quad u_{n,m}\coloneqq 0\quad\text{ otherwise},$

i.e.,

$\displaystyle U=\begin{pmatrix}&\boxed{T}&0&0&0&0&0&\cdots&\\\
&I_{\mathcal{V}}+T&0&0&0&0&0&\cdots&\\\ &0&I_{\mathcal{V}}&0&0&0&0&\cdots&\\\
&0&0&I_{\mathcal{V}}&0&0&0&\cdots&\\\ &0&0&0&I_{\mathcal{V}}&0&0&\cdots&\\\
&0&0&0&0&I_{\mathcal{V}}&0&\cdots&\\\
&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\end{pmatrix}_{\infty\times\infty}$

where $T$ is in the $(0,0)$ position (which is boxed), is isometry on
$\oplus_{n=0}^{\infty}\mathcal{V}$ and

(3) $\displaystyle T^{n}=P_{\mathcal{V}}U^{n}|_{\mathcal{V}},\quad\forall
n\in\mathbb{N},\quad(T^{*})^{n}=P_{\mathcal{V}}(U^{*})^{n}|_{\mathcal{V}},\quad\forall
n\in\mathbb{N},$

where
$P_{\mathcal{V}}:\oplus_{n=0}^{\infty}\mathcal{V}\ni(x_{n})_{n=0}^{\infty}\mapsto
x_{0}\in\mathcal{V}$.

###### Proof.

It suffices to note the adjoint of $U$ is

$\displaystyle
U^{*}=\begin{pmatrix}&\boxed{T}&I_{\mathcal{V}}+T&0&0&0&0&\cdots&\\\
&0&0&I_{\mathcal{V}}&0&0&0&\cdots&\\\ &0&0&0&I_{\mathcal{V}}&0&0&\cdots&\\\
&0&0&0&0&I_{\mathcal{V}}&0&\cdots&\\\ &0&0&0&0&0&I_{\mathcal{V}}&\cdots&\\\
&0&0&0&0&0&0&\cdots&\\\ &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\
\end{pmatrix}_{\infty\times\infty}$

where $T$ is in the $(0,0)$ position (which is boxed). ∎

We now formulate following problems.

######  Problem 2.6.

  1. (i)

Whether there is an indefinite Ando dilation? If yes, whether one can dilate
commuting three, four, … commuting self-adjoint morphisms to commuting
unitaries?

  2. (ii)

Whether there is (a kind of) uniqueness of indefinite Halmos dilation?

  3. (iii)

Whether there is a indefinite intertwining-lifting theorem (commutant lifting
theorem)?

## References

  * [1] Jim Agler and John E. McCarthy.  Pick interpolation and Hilbert function spaces, volume 44 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2002.
  * [2] M. A. Akcoglu and L. Sucheston.  Dilations of positive contractions on $L_{p}$ spaces.  Canad. Math. Bull., 20(3):285–292, 1977.
  * [3] Mustafa A. Akcoglu and P. Ekkehard Kopp.  Construction of dilations of positive $L_{p}$-contractions.  Math. Z., 155(2):119–127, 1977.
  * [4] C. Ambroziea and V. Muller.  Commutative dilation theory.  In Operator Theory, pages 1–29. Springer, 2015.
  * [5] T. Andô.  On a pair of commutative contractions.  Acta Sci. Math. (Szeged), 24:88–90, 1963.
  * [6] William Arveson.  Dilation theory yesterday and today.  In A glimpse at Hilbert space operators, volume 207 of Oper. Theory Adv. Appl., pages 99–123. Birkhäuser Verlag, Basel, 2010.
  * [7] Hari Bercovici.  Operator theory and arithmetic in $H^{\infty}$, volume 26 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 1988.
  * [8] B. V. Rajarama Bhat, Sandipan De, and Narayan Rakshit.  A caricature of dilation theory.  Adv. Oper. Theory, 6(4):Paper No. 63, 20, 2021.
  * [9] B. V. Rajarama Bhat and Mithun Mukherjee.  Two states.  Houston J. Math., 47(1):63–95, 2021.
  * [10] Tirthankar Bhattacharyya.  Dilation of contractive tuples: a survey.  In Surveys in analysis and operator theory (Canberra, 2001), volume 40 of Proc. Centre Math. Appl. Austral. Nat. Univ., pages 89–126. Austral. Nat. Univ., Canberra, 2002.
  * [11] Man-Duen Choi and Kenneth R. Davidson.  A $3\times 3$ dilation counterexample.  Bull. Lond. Math. Soc., 45(3):511–519, 2013.
  * [12] M. J. Crabb and A. M. Davie.  von Neumann’s inequality for Hilbert space operators.  Bull. London Math. Soc., 7:49–50, 1975.
  * [13] R. G. Douglas.  Structure theory for operators. I.  J. Reine Angew. Math., 232:180–193, 1968.
  * [14] S. W. Drury.  Remarks on von Neumann’s inequality.  In Banach spaces, harmonic analysis, and probability theory (Storrs, Conn., 1980/1981), volume 995 of Lecture Notes in Math., pages 14–32. Springer, Berlin, 1983.
  * [15] E. Durszt and B. Sz.-Nagy.  Remark to a paper: “Models for noncommuting operators” [J. Funct. Anal. 48 (1982), no. 1, 1–11] by A. E. Frazho.  J. Functional Analysis, 52(1):146–147, 1983.
  * [16] E. Egerváry.  On the contractive linear transformations of $n$-dimensional vector space.  Acta Sci. Math. (Szeged), 15:178–182, 1954.
  * [17] Stephan Fackler and Jochen Gluck.  A toolkit for constructing dilations on Banach spaces.  Proc. Lond. Math. Soc. (3), 118(2):416–440, 2019.
  * [18] Gero Fendler.  On dilations and transference for continuous one-parameter semigroups of positive contractions on ${L}^{p}$-spaces.  Ann. Univ. Sarav. Ser. Math., 9(1):iv+97, 1998.
  * [19] C. Foias, A. E. Frazho, I. Gohberg, and M. A. Kaashoek.  Metric constrained interpolation, commutant lifting and systems, volume 100 of Operator Theory: Advances and Applications.  Birkhäuser Verlag, Basel, 1998.
  * [20] Ciprian Foias and Arthur E. Frazho.  The commutant lifting approach to interpolation problems, volume 44 of Operator Theory: Advances and Applications.  Birkhäuser Verlag, Basel, 1990.
  * [21] Arthur E. Frazho.  Models for noncommuting operators.  J. Functional Analysis, 48(1):1–11, 1982.
  * [22] Paul R. Halmos.  Normal dilations and extensions of operators.  Summa Brasil. Math., 2:125–134, 1950.
  * [23] Deguang Han, David R. Larson, Bei Liu, and Rui Liu.  Structural properties of homomorphism dilation systems.  Chin. Ann. Math. Ser. B, 41(4):585–600, 2020.
  * [24] Martin Kern, Rainer Nagel, and Gunther Palm.  Dilations of positive operators: construction and ergodic theory.  Math. Z., 156(3):265–277, 1977.
  * [25] K. Mahesh Krishna.  p-adic magic contractions, p-adic von Neumann inequality and p-adic Sz.-Nagy dilation.  arXiv:2209.12012v1 [math.NT] 24 September, 2022.
  * [26] K. Mahesh Krishna and P. Sam Johnson.  Dilations of linear maps on vector spaces.  Oper. Matrices, 16(2):465–477, 2022.
  * [27] Eliahu Levy and Orr Moshe Shalit.  Dilation theory in finite dimensions: the possible, the impossible and the unknown.  Rocky Mountain J. Math., 44(1):203–221, 2014.
  * [28] John E. McCarthy and Orr Moshe Shalit.  Unitary $N$-dilations for tuples of commuting matrices.  Proc. Amer. Math. Soc., 141(2):563–571, 2013.
  * [29] John Milnor and Dale Husemoller.  Symmetric bilinear forms.  Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 73. Springer-Verlag, New York-Heidelberg, 1973.
  * [30] Rainer Nagel and Günther Palm.  Lattice dilations of positive contractions on $L^{p}$-spaces.  Canad. Math. Bull., 25(3):371–374, 1982.
  * [31] Stephen Parrott.  Unitary dilations for commuting contractions.  Pacific J. Math., 34:481–490, 1970.
  * [32] Vern Paulsen.  Completely bounded maps and operator algebras, volume 78 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2002.
  * [33] Gilles Pisier.  Similarity problems and completely bounded maps, volume 1618 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2001.
  * [34] Gelu Popescu.  Isometric dilations for infinite sequences of noncommuting operators.  Trans. Amer. Math. Soc., 316(2):523–536, 1989.
  * [35] Donald Sarason.  Generalized interpolation in $H^{\infty}$.  Trans. Amer. Math. Soc., 127:179–203, 1967.
  * [36] J. J. Schäffer.  On unitary dilations of contractions.  Proc. Amer. Math. Soc., 6:322, 1955.
  * [37] Orr Moshe Shalit.  Dilation theory: a guided tour.  In Operator theory, functional analysis and applications, volume 282 of Oper. Theory Adv. Appl., pages 551–623. Birkhäuser/Springer, Cham, 2021.
  * [38] Elena Stroescu.  Isometric dilations of contractions on Banach spaces.  Pacific J. Math., 47:257–262, 1973.
  * [39] Béla Sz.-Nagy.  Sur les contractions de l’espace de Hilbert.  Acta Sci. Math. (Szeged), 15:87–92, 1953.
  * [40] Béla Sz.-Nagy.  On Schäffer’s construction of unitary dilations.  Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3(4):343–346, 1960/61.
  * [41] Béla Sz.-Nagy and Ciprian Foiaş.  The “lifting theorem” for intertwining operators and some new applications.  Indiana Univ. Math. J., 20(10):901–904, 1971.
  * [42] Bela Sz.-Nagy, Ciprian Foias, Hari Bercovici, and Laszlo Kerchy.  Harmonic analysis of operators on Hilbert space.  Universitext. Springer, New York, second edition, 2010.
  * [43] N. Th. Varopoulos.  On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory.  J. Functional Analysis, 16:83–100, 1974.


11institutetext: IISER Bhopal,
11email<EMAIL_ADDRESS>
# Linearity and Local Correctness in Weighted Colourings of Random Graphs

Ghurumuruhan Ganesan

###### Abstract

In this paper, we consider a weighted generalization of the chromatic number
of a Binomial random graph $G.$ We equip each edge with a random weight and
then colour the vertices in such a way that the absolute colour difference
between any two adjacent vertices is at least as large as their edge weight.
We show that with high probability, the weighted colouring number grows
linearly with the maximum vertex degree if the edge weights have sufficiently
large moments. Conversely, if the edge weight moments are unbounded then the
weighted chromatic number is much larger than the maximum vertex degree, with
high probability. We also obtain a sharp threshold result for locally correct
weighted colourings for balanced subgraphs of $G.$

Key words: Weighted colouring; random graphs; edge weight moments, locally
correct colourings, sharp threshold.

AMS 2020 Subject Classification: Primary: 60C05.

##  1 Introduction

The chromatic number $\chi(G)$ of a graph $G$ is the smallest number of
colours needed for a proper colouring of $G$ and many upper and lower bounds
for $\chi(G)$ exist in terms of various graph parameters like maximum vertex
degree, independence number, clique number etc. (see Chapter $5,$ (West
(2000)). For random graphs, concentration and estimates for the actual value
of the chromatic number in terms of the edge probability $p$ has been well-
studied (see for example Bollobás (2001)).

In this paper, we study weighted colouring in random graphs whose edge
probabilities are not necessarily homogenous. Generalizing radio labelling of
graphs (Chartrand et al. (2001), Korze et al. (2021)) which we call as
weighted colouring number, we use the probabilistic method to estimate the
weighted colouring number when the edge weights themselves are random. Such
situations arise frequently in applications and we show that if the weights
have sufficiently large moments, then the “cost” incurred due to the
unboundedness of weights is small.

We also consider Ramsey type properties of weighted colourings in the sense of
locally correct colourings. The study of Ramsey property of random graphs is
important from theoretical and application perspectives. Luczak et al. (1992)
initiated the study by determining the threshold for the edge probability
exponent that results in the presence of a monochromatic copy of a given graph
for both vertex and edge colouring. Since then many variants and extensions
have been studied. For example, Rödl et al. (2017) extend the results of
Luczak et al. (1992) and determine a double exponential upper bound for the
$2-$colour Folkmann numbers. Concurrently Dudek and Pralat (2017) studied
monochromatic long paths in $3-$colourings of random graphs and obtain optimal
bounds on the length exponent. Recently Liebenau et al. (2022) established
threshold properties for asymmetric Ramsey properties of $G$ where every
colouring contains either a $1-$coloured copy of $F$ or a $2-$coloured copy of
$H,$ where the pair $(F,H)$ constitutes a clique and a cycle.

In this paper, we consider weighted random graphs and obtain sharp threshold
for the occurrence of properly coloured copies of balanced subgraphs. We
demonstrate a “sharp threshold” for the number of colours needed for such
properly coloured copies.

The paper is organized as follows: In Section 2, we study weighted colourings
and obtain estimates for the weighted chromatic number of random graphs when
the edge weights have bounded moments. In Section 3, we consider locally
correct weighted colourings where we fix the number of colours and seek
properly coloured subgraphs of the overall random graph.

##  2 Weighted Colourings

Let $K_{n}$ be the complete graph on $n$ vertices and let $X_{h},h\in K_{n}$
be independent and identically distributed (i.i.d.) Bernoulli random variables
indexed by the edge set of $K_{n}$ and satisfying

$\mathbb{P}(X_{f}=1)=p=1-\mathbb{P}(X_{f}=0)$ (2.1)

where $0\leq p\leq 1.$ Equip the ${n\choose 2}$ edges of $K_{n}$ with i.i.d.
weights $\\{w(h)\\}_{h\in K_{n}}$ (that are also independent of
$\\{X_{h}\\}$), satisfying $w(h)\geq 1$ a.s. and let $\mathbb{P}$ denote the
probability measure associated with $\\{X(h)\\}$ and $\\{w(h)\\}.$

Let $G$ be the random subgraph of $K_{n}$ formed by the set of all edges
satisfying $X_{f}=1.$ For an integer $k\geq 1,$ a proper $k-$colouring of $G$
is a map $g:V\rightarrow\\{1,2,\ldots,k\\}$ such that $g(u)\neq g(v)$ for all
edges $(u,v)\in E.$ The chromatic number $\chi(G)$ is the smallest integer $k$
such that $G$ admits a proper $k-$colouring.

Let $f:V\rightarrow\\{1,2,\ldots\\}$ be any map from the vertex set of $G$ to
the set of positive integers. We say that $f$ is a proper weighted colouring
of $G$ if for each edge $h=(u,v)\in E$ with endvertices $u$ and $v$ we have

$|f(u)-f(v)|\geq w(u,v).$ (2.2)

We define the weighted colouring number of $G$ as

$\chi_{w}=\chi_{w}(G):=\inf_{f}\max_{1\leq u\leq n}f(u),$ (2.3)

where the infimum is over all proper weighted colourings of $G.$ Roughly
speaking $\chi_{w}(G)$ could be thought of as a measure of the effect of
weights on a proper colouring of $G.$ Indeed if $w(u,v)=1$ for all edges, then
the weighted colouring number $\chi_{w}(G)=\chi(G),$ the chromatic number.

If $p\geq\frac{M\log{n}}{n}$ for some constant $M>0,$ then it is well-known
(see for example Theorem $2,$ Ganesan (2020)) that for every constant
$\epsilon>0$ there are constants $M_{0},D_{1},D_{2}>0$ such that if $M>M_{0},$
then

$\mathbb{P}\left(\frac{D_{1}np}{\log{n}}\leq\chi(G)\leq\Delta(G)+1\leq
np(1+\epsilon)\right)\geq 1-\frac{1}{n^{D_{2}}},$ (2.4)

where constants do not depend on $n,$ throughout and $\Delta(G)$ is the
maximum vertex degree in $G.$ By definition, the weighted colouring number
$\chi_{w}(G)\geq\chi(G)$ and we have the following result regarding the
linearity for $\chi_{w}(G).$

###### Theorem 2.1

We have:
$(a)$ Suppose $p\geq\frac{1}{n^{\beta}}$ and $\mathbb{E}w^{2s+c}(h)\leq C$ for
some constants
$0<\beta<1,C,c>0$ and integer constant $s\geq 2.$ For every
$\beta<1-\frac{1}{s+1/2-1/2s}$ and $\epsilon>0$ there is a constant $D>0$ such
that

$\mathbb{P}\left(\chi_{w}(G)\leq 2\mu np(1+\epsilon)\right)\geq
1-\frac{1}{n^{D}}$ (2.5)

where $\mu:=\mathbb{E}w(h)$ is the expected edge weight.
$(b)$ Suppose $p=\frac{1}{n^{\beta}}$ and $\mathbb{P}(w(h)\geq
x)\geq\frac{A}{x^{2s}}$ for some constants $0<\beta<1,A>0$ and $s>1.$ For
every $\beta>1-\frac{1}{2s-1},$ there are constants $\theta_{1},\theta_{2}>0$
such that

$\mathbb{P}\left(\chi_{w}(G)\geq n^{\theta_{1}}\cdot np\right)\geq
1-\exp\left(-n^{\theta_{2}}\right).$ (2.6)

Part $(a)$ of Theorem 2.1 says that if the edge weights have bounded
$(2s)^{th}$ moments and the edge probability exponent is small enough (or
equivalently if $G$ is sufficiently dense), then the weighted chromatic number
grows linearly with the maximum vertex degree. In part $(b),$ we obtain a
partial converse of part $(a):$ if the $(2s)^{th}$ moment is infinite and the
graph $G$ is sparse enough, then $\chi_{w}(G)$ is “much” larger than the
maximum degree in the sense of (2.6).

We prove Theorem 2.1$(a)$ using a greedy colouring strategy analogous to the
maximum degree bound for unweighted chromatic number and prove part $(b)$ by
estimating the maximum weight of an edge in $G.$ Throughout, we use the
following standard deviation estimate regarding sums of independent Bernoulli
random variables. Let $Z_{i},1\leq i\leq t$ be independent Bernoulli random
variables satisfying

$\mathbb{P}(Z_{i}=1)=p_{i}=1-\mathbb{P}(Z_{i}=0).$

If $W_{t}=\sum_{i=1}^{t}Z_{i}$ and $\mu_{t}=\mathbb{E}W_{t},$ then for any
$0<\epsilon<\frac{1}{2}$ we have that

$\mathbb{P}\left(\left|W_{t}-\mu_{t}\right|\geq\epsilon\mu_{t}\right)\leq
2\exp\left(-\frac{\epsilon^{2}}{4}\mu_{t}\right).$ (2.7)

For a proof of (2.7), we refer to Corollary $A.1.14,$ pp. $312,$ Alon and
Spencer (2008).

_Proof of Theorem 2.1_: We prove $(a)$ first and begin with a deterministic
estimate that obtains a bound for the weighted chromatic number in terms of
the locally averaged weights. Specifically, we show that

$\chi_{w}(G)\leq 1+\max_{v\in G}\sum_{u\sim v}(2w(u,v)-1)$ (2.8)

where $u\sim v$ denotes that $u$ and $v$ are adjacent in $G.$ This is a
generalization of the maximum degree bound $\chi(G)\leq\Delta+1,$ where
$\Delta$ is the maximum vertex degree in $G.$ In fact if $w(u,v)=1$ for all
edges, then the right side of (2.8) reduces to $\Delta+1.$ As in the proof of
the maximum degree bound, we use a greedy colouring procedure to obtain (2.8).

Let $L+1:=1+\max_{v}\sum_{u\sim v}(2w(u,v)-1),$ the right hand side of (2.8).
We iteratively colour the vertices of $H$ from the set $\\{1,2,\ldots,L+1\\}.$
Pick a vertex $u_{1}$ and assign the colour $l(u_{1})=1.$ For the $i^{th}$
iteration, $i\geq 2,$ we pick an uncoloured vertex $u_{i}$ and let
$l(v_{1}),\ldots,l(v_{t})$ be the colours of its coloured neighbours. Let
$I(v_{j})$ be the set of all integers $l$ satisfying $|l-l(v_{j})|\leq
w(u_{i},v_{j})-1.$ There are $2w(u_{i},v_{j})-1$ integers in $I(v_{j})$ and so
the number of integers in $\bigcup_{1\leq j\leq t}I(v_{j})$ is at most $L.$ We
therefore assign a colour
$l(u_{i})\in\\{1,2,\ldots,L+1\\}\setminus\bigcup_{1\leq j\leq t}I(v_{j})$ to
the vertex $u_{i}.$ Continuing this process we obtain a proper weighted
colouring of $G$ and this proves (2.8).

We use (2.8) to prove (2.5) as follows. For $1\leq i\leq n$ let $N_{i}$ be the
number of neighbours of the vertex $i$ in the graph $G.$ The expected number
of neighbours for vertex $i$ is at least $(n-1)p.$Therefore using the
concentration estimate (2.7) with $\epsilon>0,$ we have that

$\mathbb{P}\left(np(1-\epsilon)\leq N_{i}\leq np(1+\epsilon)\right)\geq
1-e^{-Dnp},$ (2.9)

for some positive constant $D=D(\epsilon).$ Letting

$E_{nei}:=\bigcap_{1\leq i\leq n}\left\\{np(1-\epsilon)\leq N_{i}\leq
np(1+\epsilon)\right\\},$

we have by the union bound that

$\mathbb{P}(E_{nei})\geq 1-ne^{-Dnp}.$ (2.10)

Let $\omega\in E_{nei}$ be a realization of $G$ and let $\mathbb{P}_{\omega}$
be the conditional probability measure given $\omega.$ To find an upper bound
for $\chi_{w}(\omega),$ we use the locally averaged bound (2.8). For $1\leq
i\leq n$ let $J_{i}:=\sum_{v\sim i}w(i,v)=\sum_{v=1}^{N_{i}}Z_{v}$ be the sum
of the weights of edges containing $i$ as an endvertex, where $N_{i}$ is the
degree of vertex $i$ in $\omega.$ The expected value
$\mathbb{E}_{\omega}(J_{i})=N_{i}\mu$ and so by the Markov inequality, we have
for constant $\epsilon>0$ that

$\displaystyle\mathbb{P}_{\omega}\left(\left|J_{i}-\mathbb{E}_{\omega}J_{i}\right|\geq\epsilon\mathbb{E}_{\omega}J_{i}\right)$
$\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}_{\omega}\left(J_{i}-\mathbb{E}_{\omega}J_{i}\right)^{2s}}{(\epsilon\mathbb{E}_{\omega}J_{i})^{2s}}$
(2.11) $\displaystyle\leq$
$\displaystyle\frac{D_{1}}{N_{i}^{2s}}\mathbb{E}_{\omega}\left(J_{i}-\mathbb{E}_{\omega}J_{i}\right)^{2s}$

for some constant $D_{1}>0.$

Expanding
$(J_{i}-\mathbb{E}_{\omega}J_{i})^{2s}=\left(\sum_{v=1}^{N_{i}}(Z_{v}-\mathbb{E}_{\omega}Z_{v})\right)^{2s},$
we see that any term of the form
$\prod_{j}(Z_{i_{j}}-\mathbb{E}_{\omega}Z_{i_{j}})^{b_{j}}$ has expectation
zero, unless each $b_{j}$ is even. This implies that the total number of terms
with non-zero expectation is

$\sum_{l=1}^{s}{N_{i}\choose l}\leq s{N_{i}\choose s}\leq sN_{i}^{s}$

by the monotonicity of the binomial coefficient for $N_{i}\geq 2s.$ Thus

$\mathbb{E}_{\omega}\left(\sum_{v=1}^{N_{i}}(Z_{v}-\mathbb{E}_{\omega}Z_{v})\right)^{2s}\leq
D_{2}N_{i}^{s}$

for some constant $D_{2}>0$ and plugging this into (2.11), we get that

$\mathbb{P}_{\omega}\left(\left|J_{i}-\mathbb{E}_{\omega}J_{i}\right|\geq\epsilon\mathbb{E}_{\omega}J_{i}\right)\leq\frac{D_{3}}{N_{i}^{s}}$

for some constant $D_{3}>0.$ Recalling that
$\mathbb{E}_{\omega}(J_{i})=N_{i}\mu$ and $np(1-\epsilon)\leq N_{i}\leq
np(1+\epsilon)$ since $\omega\in E_{nei},$ we get

$\mathbb{P}_{\omega}\left(J_{i}\geq\mu(1+\epsilon)^{2}np\right)\leq\frac{D_{3}}{N_{i}^{s}}\leq\frac{D_{4}}{(np)^{s}}$
(2.12)

for some constant $D_{4}>0.$

Define vertex $v$ to be _bad_ if $J_{v}>\mu np(1+\epsilon)^{2}$ and let
$G_{good}\subset G$ be the graph induced by set of all vertices that are _not_
bad. Arguing as in the first paragraph of the proof, we obtain a proper
colouring of $G_{good}$ using at most $L:=2\mu np(1+\epsilon)^{2}+1$ colours.
Next, if $v_{1},\ldots,v_{t}$ is the set of all bad vertices and $M_{u}$ is
the maximum weight of an edge in $G$ containing $u$ as an endvertex, then we
assign colour $L+2\sum_{i=1}^{j}M_{v_{i}}$ to vertex $v_{j}.$ The overall
resulting colouring is proper and uses at most $L+2\sum_{i=1}^{t}M_{v_{i}}$
colours and so $\chi_{w}$ is bounded above by

$\displaystyle\zeta_{w}$ $\displaystyle:=$ $\displaystyle 2\mu
np(1+\epsilon)^{2}+1+2\sum_{i=1}^{t}M_{v_{i}}$ (2.13) $\displaystyle=$
$\displaystyle 2\mu np(1+\epsilon)^{2}+1+2M_{tot},$

where $M_{tot}:=\sum_{v}M_{v}1{1}\left(v\text{ is bad}\right).$

We estimate $M_{v}1{1}(v\text{ is bad})$ as follows. By the moment condition
in the Theorem statement and the Markov inequality, we have for $x\geq 1$ that

$\displaystyle\mathbb{P}_{\omega}(M_{v}>x)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\omega}\left(\bigcup_{u\sim v}\\{w(u,v)>x\\}\right)$
(2.14) $\displaystyle\leq$ $\displaystyle\sum_{u\sim
v}\mathbb{P}_{\omega}(w(u,v)>x)$ $\displaystyle\leq$
$\displaystyle\frac{C_{1}N_{v}}{x^{2s+c}}$ $\displaystyle\leq$
$\displaystyle\frac{2C_{1}np}{x^{2s+c}}$

for some constant $C_{1}>0,$ where we recall that $N_{v}$ is the number of
neighbours of $v$ in $G$ and the final relation in (2.14) is true since
$\omega\in E_{nei}.$ Thus

$\displaystyle\mathbb{E}M_{v}^{2s}$ $\displaystyle=$ $\displaystyle\int
x^{2s-1}\mathbb{P}(M_{v}>x)dx$ $\displaystyle\leq$ $\displaystyle
2C_{1}np\int_{1}^{\infty}\frac{1}{x^{1+c}}dx$ $\displaystyle\leq$
$\displaystyle C_{2}np$

for some constant $C_{2}>0.$ By the Cauchy-Schwartz inequality and (2.12), we
therefore have that

$\displaystyle\mathbb{E}M_{v}1{1}(v\text{ is bad})$ $\displaystyle\leq$
$\displaystyle\left(\mathbb{E}M_{v}^{2s}\right)^{\frac{1}{2s}}\cdot\left(\mathbb{P}(v\text{
is bad })\right)^{1-\frac{1}{2s}}$ (2.15) $\displaystyle\leq$
$\displaystyle(C_{2}np)^{\frac{1}{2s}}\cdot\left(\frac{D_{5}}{(np)^{s}}\right)^{1-\frac{1}{2s}}$
$\displaystyle=$ $\displaystyle\frac{C_{3}}{(np)^{r}}$

where $r:=s-\frac{1}{2}-\frac{1}{2s}$ and $C_{3}>0$ is a constant.

Summing over $v$ in (2.15) and recalling that
$M_{tot}=\sum_{v}M_{v}1{1}(v\text{ is bad}),$ we get that

$\mathbb{E}M_{tot}\leq\frac{C_{3}n}{(np)^{r}}$

and so by Markov inequality we have for $\epsilon>0$ that

$\mathbb{P}\left(M_{tot}\geq\frac{n^{1+\epsilon}}{(np)^{r}}\right)\leq\frac{C_{4}}{n^{\epsilon}}$

for some constant $C_{4}>0.$ Plugging this into (2.13), we get that

$\mathbb{P}\left(\chi_{w}\leq 2\mu
np(1+\epsilon)^{2}+1+\frac{n^{1+\epsilon}}{(np)^{r}}\right)\geq
1-\frac{C_{4}}{n^{\epsilon}}.$

If we ensure that

$\frac{n^{1+\epsilon}}{(np)^{r}}\leq\epsilon np$

or equivalently that

$p\geq\left(\frac{1}{\epsilon}\right)^{\frac{1}{r+1}}\cdot\frac{1}{n^{1-\frac{\epsilon+1}{r+1}}}$
(2.16)

then we get (2.5). But by choice $\beta<1-\frac{1}{r+1}$ strictly and so
choosing $\epsilon>0$ small enough, we see that (2.16) holds and this
completes the proof of part $(a)$ of the Theorem.

To prove part $(b),$ we suppose that the event $E_{nei}$ defined above occurs,
so that the number of edges in $G$ is at least
$\frac{n^{2}p}{4}\geq\frac{1}{4}n^{2-\beta}$ and each edge has degree at most
$2np=n^{1-\beta}.$ The probability that an edge $h$ has weight less than
$n^{\epsilon}$ is at most $1-\frac{A}{n^{2s\epsilon}}$ and so the probability
that the maximum edge weight is at most $n^{\epsilon}$ is bounded above by

$\left(1-\frac{A}{n^{2s\epsilon}}\right)^{\frac{1}{4}n^{2-\beta}}\leq\exp\left(-\frac{A}{4}n^{2-\beta-2s\epsilon}\right)\longrightarrow
0$

if $\epsilon<\frac{2-\beta}{2s}$ strictly. The weight colouring number is at
least as large as the maximum edge weight and so choosing
$1-\beta<\epsilon<\frac{2-\beta}{2s}$ (this is possible by choice of $\beta$),
we obtain (2.6). This completes the proof of the Theorem.

##  3 Locally Correct Colourings

In this section, we consider a dual problem where the number of colours is
fixed and we seek properly coloured subgraphs of random graphs. As before, let
$G$ be the random graph as in (2.1) and let $\\{w(h)\\}_{h\in K_{n}}$ be
independent and identically distributed edge weights that are also independent
of $G.$

Let $\Gamma$ be a labelled deterministic graph on $v_{0}$ vertices and
containing $e_{0}$ edges and let $V(\Gamma)$ and $E(\Gamma)$ respectively
denote the vertex and edge sets of $\Gamma.$ We say that $\Gamma$ is
_balanced_ if for any subgraph $H\subset\Gamma$ we have that
$\frac{e(H)}{v(H)}\leq\frac{e_{0}}{v_{0}}$ where $e(H)=\\#E(H)$ and
$v(H)=\\#V(H)$ respectively denote the number of edges and vertices in $H.$
Throughout $\\#A$ denotes the cardinality of $A$ and we assume henceforth that
$\Gamma$ is a balanced graph.

We say that a subgraph $T\subset G$ containing $v_{0}$ vertices and $e_{0}$
edges is a _copy_ of $\Gamma$ if $T$ is isomorphic to $\Gamma:$ i.e. there
exists a bijection $g:V(T)\rightarrow V(\Gamma)$ such that $(u,v)\in E(T)$ if
and only if $(g(u),g(v))\in E(\Gamma).$ For constant $M>0,$ we say that a
subgraph $T\subset G$ is $M-$_good_ or simply good if

$w(u,v)\leq|\theta(u)-\theta(v)|\leq M$ (3.1)

for each edge $(u,v)\in E(T).$ Say that the colouring $\theta$ is _good_ if
there is at least one good copy of $\Gamma$ in $G.$

Letting $N_{tot}$ and $N_{good}=N_{good}(M)$ respectively denote the total
number of colourings and the number of good colourings of $G,$ the following
result obtains a “sharp threshold” for the occurrence of good colourings. As
before, constants do not depend on $n.$

###### Theorem 3.1

Let $\Gamma$ be a balanced graph containing $v_{0}$ vertices and $e_{0}$ edges
and suppose $r=n^{\theta}\text{ and }p=\frac{1}{n^{\beta}}$ for some constants
$0<\theta<1$ and $\frac{1}{e_{0}}<\beta<\frac{v_{0}}{e_{0}}$ so that
$0<\theta_{th}:=\frac{v_{0}-e_{0}\beta}{v_{0}-1}<1$ strictly. There exists
$M_{0}>0$ large such that for all $M>M_{0},$ the following hold:
$(a)$ If $\theta<\theta_{th},$ then

$\mathbb{P}\left(N_{good}\geq
N_{tot}\left(1-\frac{1}{n^{C_{1}}}\right)\right)\geq 1-\frac{1}{n^{C_{2}}}$

for some constants $C_{1},C_{2}>0.$
$(b)$ If $\theta>\theta_{th},$ then

$\mathbb{P}\left(N_{good}\leq\frac{N_{tot}}{n^{D_{1}}}\right)\geq
1-\frac{1}{n^{D_{2}}}$

for some constants $D_{1},D_{2}>0.$

In words, we see that if $\theta<\theta_{th},$ then nearly all colourings are
good with high probability and if $\theta>\theta_{th}$ then nearly all
colourings are bad with high probability. Thus $\theta_{th}$ could be
interpreted as the threshold value of $\theta$ for the occurrence of good
colourings.

_Proof of Theorem 3.1_: We prove both parts in the Theorem using method of
moments and begin with some preliminary computations. Throughout we set
$\zeta:=\theta(v_{0}-1)-(v_{0}-e_{0}\beta).$

We begin with the proof of $(a).$ Let $K\geq 1$ be a large enough integer so
that $z_{K}:=\mathbb{P}(w(h)\leq K)>0$ and let $G_{K}\subset G$ be the random
subgraph of $G$ obtained by preserving each edge $h$ such that $X_{h}=1$ and
the weight $w(h)\leq K$ (see discussion following (2.1)). Each edge of $K_{n}$
is present in $G_{K}$ with probability $z_{K}\cdot p.$

If $N_{\Gamma}(G)$ is the number of copies of $\Gamma$ in $G,$ then

$D_{1}n^{v_{0}}p^{e_{0}}\leq\mathbb{E}N_{\Gamma}(G_{K})\leq\mathbb{E}N_{\Gamma}(G)\leq
D_{2}n^{v_{0}}p^{e_{0}}$ (3.2)

for some constants $D_{1},D_{2}>0.$ If

$\displaystyle E_{\Gamma}$ $\displaystyle:=$
$\displaystyle\\{|N_{\Gamma}(G)-\mathbb{E}N_{\Gamma}(G)|\leq\epsilon
N_{\Gamma}(G)\\}$ (3.3)
$\displaystyle\;\;\;\bigcap\\{|N_{\Gamma}(G_{K})-\mathbb{E}N_{\Gamma}(G_{K})|\leq\epsilon
N_{\Gamma}(G_{K})\\}$

with $0<\epsilon<1$ constant, then from the Chebychev inequality and the
variance estimate for $N_{\Gamma}(G)$ in Lemma $3.5$ of Janson et al. (2000),
we know that

$\mathbb{P}\left(E^{c}_{\Gamma}\right)\leq\frac{C}{\min_{H\subset\Gamma}n^{v_{H}}p^{e_{H}}}$

for some constant $C>0,$ where the minimum is over all subgraphs of $H$
containing at least one edge and $v_{H}$ and $e_{H}$ respectively denote the
number of vertices and edges in $H,$ respectively. Using the fact that
$\Gamma$ is balanced, we see that $e_{H}\leq\frac{v_{H}e_{0}}{v_{0}}$ and so

$\min_{H}n^{v_{H}}p^{e_{H}}\geq\min_{2\leq i\leq
v_{0}}n^{i}p^{ie_{0}/v_{0}}=\min_{2\leq i\leq
v_{0}}(n^{v_{0}}p^{e_{0}})^{i/v_{0}}=(n^{v_{0}}p^{e_{0}})^{2/v_{0}}=:n^{\nu},$

where $\nu>0$ is positive since $\beta<\frac{v_{0}}{e_{0}}.$ Thus

$\mathbb{P}\left(E^{c}_{\Gamma}\right)\leq\frac{C}{n^{\nu}}.$ (3.4)

Next, let $X_{i},1\leq i\leq n$ be independent and identically distributed
(i.i.d.) random variables uniformly chosen from $\\{1,2,\ldots,r\\}$ that are
also independent of $G$ and the edge weights $\\{w(h)\\}.$ Assign colour
$X_{i}$ to the vertex $i$ and let $\mathbb{P}_{X}$ denote the distribution of
$(X_{1},\ldots,X_{n}).$

For a copy $T$ of $\Gamma,$ let $A_{T}$ be the event that the vertex colours
$X_{u},u\in T$ form an arithmetic progression with common difference $K+1.$
Also let $B_{T}$ be the event that $T$ is a subgraph of $G_{K}.$ If $A_{T}\cap
B_{T}$ occurs, then $T$ is an $M-$good copy of $\Gamma$ with $M=v_{0}(K+1)$
and so

$Y_{\Gamma}:=\sum_{T}1{1}(A_{T})1{1}(B_{T})$

is a lower bound on the number of good copies of $\Gamma,$ where $1{1}(.)$
refers to the indicator function and the summation is over all copies of
$\Gamma$ in the _complete graph_ $K_{n}.$

We now use the second moment method show that $Y_{\Gamma}$ is concentrated
around its mean with high $\mathbb{P}_{X}-$probability for nearly all
realizations of the random subgraph $G.$ Indeed,

$\mathbb{E}_{X}Y^{2}_{\Gamma}=\sum_{T}\mathbb{P}_{X}(A_{T})1{1}(B_{T})+\sum_{T_{1}\neq
T_{2}}\mathbb{P}_{X}(A_{T_{1}}\cap A_{T_{2}})1{1}\left(B_{T_{1}}\cap
B_{T_{2}}\right).$

Taking expectations with respect to $G$ and the edge weights, we then get that

$\displaystyle\mathbb{E}\mathbb{E}_{X}Y^{2}_{\Gamma}$ $\displaystyle=$
$\displaystyle\sum_{T}\mathbb{P}_{X}(A_{T})\mathbb{P}(B_{T})+\sum_{T_{1}\neq
T_{2}}\mathbb{P}_{X}(A_{T_{1}}\cap A_{T_{2}})\mathbb{P}\left(B_{T_{1}}\cap
B_{T_{2}}\right)$ (3.5) $\displaystyle=$
$\displaystyle\sum_{T_{1}}\mathbb{P}_{X}(A_{T_{1}})\mathbb{P}(B_{T_{1}})\left(1+\Delta\right),$

where

$\Delta:=\sum_{T_{1}\neq T_{2}}\mathbb{P}_{X}(A_{T_{2}}\mid
A_{T_{1}})\mathbb{P}\left(B_{T_{2}}\mid B_{T_{1}}\right).$

Let $T$ be any copy of $\Gamma$ and let $u$ be any vertex of $T.$ Conditioning
on the colour $X_{u},$ we see that $\mathbb{P}(A_{T}\mid X_{u})$ lies between
$\frac{C_{1}}{r^{v_{0}-1}}$ and $\frac{C_{2}}{r^{v_{0}-1}}$ for some positive
constants $C_{1},C_{2}$ and so taking averages we get

$\frac{C_{1}}{r^{v_{0}-1}}\leq\mathbb{P}_{X}(A_{T})\leq\frac{C_{2}}{r^{v_{0}-1}}.$
(3.6)

If $T_{1}$ and $T_{2}$ are distinct copies of $\Gamma$ that do not share any
vertex, then

$\mathbb{P}_{X}(A_{T_{2}}\mid A_{T_{1}})=\mathbb{P}_{X}(A_{T_{2}})\text{ and
}\mathbb{P}\left(B_{T_{2}}\mid
B_{T_{1}}\right)=\mathbb{P}\left(B_{T_{2}}\right).$ (3.7)

On the other hand if $T_{1}$ and $T_{2}$ share exactly $1\leq i\leq v_{0}-1$
common vertices, then the total number of vertices in $T_{1}\cup T_{2}$ is
$2(v_{0}-i)+i=2v_{0}-i$ and arguing as in (3.6), we have that

$\frac{C_{3}}{r^{2v_{0}-i-1}}\leq\mathbb{P}_{X}(A_{T_{1}}\cap
A_{T_{2}})\leq\frac{C_{4}}{r^{2v_{0}-i-1}}$ (3.8)

for some constants $C_{3},C_{4}>0.$ Combining with (3.6) we get

$\frac{C_{5}}{r^{v_{0}-i}}\leq\mathbb{P}_{X}(A_{T_{2}}\mid
A_{T_{1}})\leq\frac{C_{6}}{r^{v_{0}-i}}$ (3.9)

for some constants $C_{5},C_{6}>0.$

Next, the graph $\Gamma$ is balanced and so there are at most
$\frac{ie_{0}}{v_{0}}$ edges containing both end vertices within $T_{1}\cap
T_{2}.$ Consequently

$\mathbb{P}(B_{T_{2}}\mid B_{T_{1}})\leq(pz_{K})^{e_{0}-\frac{ie_{0}}{v_{0}}}$

where we recall that $z_{K}=\mathbb{P}(w(h)\leq K)$ is the (constant)
probability that edge weight is at most $K.$ Since there at most $n^{v_{0}-i}$
choices for the vertices in $T_{2}\setminus T_{1},$ we get from the above
discussion that

$\Delta\leq\sum_{T_{2}}\mathbb{P}_{X}(A_{T_{2}})\mathbb{P}(B_{T_{2}})+D_{1}\sum_{1\leq
i\leq v_{0}-1}\frac{n^{v_{0}-i}}{r^{v_{0}-i}}p^{e_{0}-\frac{ie_{0}}{v_{0}}}$

for some constant $D_{1}>0.$ Plugging this into (3.5), we get that

$\mathbb{E}\mathbb{E}_{X}Y^{2}_{\Gamma}\leq\alpha+\alpha^{2}+D_{1}\alpha\sum_{1\leq
i\leq v_{0}-1}\frac{n^{v_{0}-i}}{r^{v_{0}-i}}p^{e_{0}-\frac{ie_{0}}{v_{0}}},$
(3.10)

where

$\alpha:=\sum_{T}\mathbb{P}_{X}(A_{T})\mathbb{P}(B_{T})=\mathbb{E}\mathbb{E}_{X}Y_{\Gamma}.$
(3.11)

By Jensen’s inequality we have that
$\alpha^{2}=(\mathbb{E}\mathbb{E}_{X}Y_{\Gamma})^{2}\leq\mathbb{E}(\mathbb{E}_{X}Y_{\Gamma})^{2}$
and so from (3.10) we get that

$\mathbb{E}var_{X}(Y_{\Gamma})\leq\alpha\left(1+D_{1}\sum_{1\leq i\leq
v_{0}-1}\frac{n^{v_{0}-i}}{r^{v_{0}-i}}p^{e_{0}-\frac{ie_{0}}{v_{0}}}\right).$
(3.12)

Using the lower bounds in (3.6) and (3.2), we get that

$\displaystyle\alpha$ $\displaystyle\geq$
$\displaystyle\sum_{T}\mathbb{P}_{X}(A_{T})\mathbb{P}(T\in G_{K})$ (3.13)
$\displaystyle\geq$
$\displaystyle\frac{D_{2}z_{K}^{e_{0}}}{r^{v_{0}-1}}\mathbb{E}N_{\Gamma}(G_{K})$
$\displaystyle\geq$ $\displaystyle\frac{D_{3}n^{v_{0}}p^{e_{0}}}{r^{v_{0}-1}}$
$\displaystyle=$ $\displaystyle D_{3}n^{|\zeta|},$

for some constants $D_{2},D_{3}>0,$ since
$\theta<\frac{v_{0}-e_{0}\beta}{v_{0}-1}$ strictly. Similarly using the upper
bounds in (3.6) and (3.2), we get

$\alpha\leq\sum_{T}\mathbb{P}_{X}(A_{T})\mathbb{P}(T\in G)\leq
D_{4}n^{|\zeta|}$ (3.14)

for some constant $D_{4}>0.$

Next, for $1\leq i\leq v_{0}-1$ we have that

$\frac{n^{v_{0}-i}}{r^{v_{0}-i}}p^{e_{0}-\frac{ie_{0}}{v_{0}}}=\left(\frac{n^{v_{0}}p^{e_{0}}}{r^{v_{0}}}\right)^{1-\frac{i}{v_{0}}}\leq
D_{5}\left(\frac{\alpha}{r}\right)^{1-i/v_{0}}\leq
D_{5}\alpha^{1-1/v_{0}}=D_{5}\frac{\alpha}{n^{2\delta}}$

for some positive constants $D_{5},\delta$ not depending on the choice of $i.$
Plugging this into (3.12) we get that
$\mathbb{E}var_{X}(Y_{\Gamma})\leq\frac{D_{6}\alpha^{2}}{n^{2\delta}}$ for
some constant $D_{6}>0$ and so letting
$E_{var}:=\left\\{var_{X}(Y_{\Gamma})\leq\frac{D_{6}\alpha^{2}}{n^{\delta}}\right\\}$
we get from the Markov inequality that

$\mathbb{P}\left(E^{c}_{var}\right)\leq\frac{1}{n^{\delta}}.$ (3.15)

Suppose $E_{var}\cap E_{\Gamma}$ occurs where $E_{\Gamma}$ is as defined prior
to (3.4). For constant $0<\epsilon<1,$ we then get from the Chebychev
inequality that

$\mathbb{P}_{X}\left(|Y_{\Gamma}-\mathbb{E}_{X}Y_{\Gamma}|\geq\epsilon\mathbb{E}_{X}Y_{\Gamma}\right)\leq\frac{var_{X}(Y_{\Gamma})}{\epsilon^{2}(\mathbb{E}_{X}Y_{\Gamma})^{2}}\leq\frac{D_{7}\alpha^{2}}{n^{\delta}(\mathbb{E}_{X}Y_{\Gamma})^{2}}$
(3.16)

for some constant $D_{7}>0.$ From (3.11) and (3.6) we have

$\displaystyle\mathbb{E}_{X}Y_{\Gamma}$ $\displaystyle=$
$\displaystyle\sum_{T}\mathbb{P}_{X}(A_{T})1{1}(T\in G_{K})$ (3.17)
$\displaystyle\geq$ $\displaystyle D_{8}\frac{N_{\Gamma}(G_{K})}{r^{v_{0}-1}}$
$\displaystyle\geq$ $\displaystyle
D_{8}\frac{(1-\epsilon)\mathbb{E}N_{\Gamma}(G_{K})}{r^{v_{0}-1}}$
$\displaystyle\geq$ $\displaystyle D_{9}n^{|\zeta|}$

for some constants $D_{8},D_{9}>0,$ where the first relation in (3.17) is true
from the lower bound in (3.6), the second inequality in (3.17) follows from
the fact that $E_{\Gamma}$ occurs and the final estimate in (3.17) is obtained
by an analogous argument as in (3.13). Substituting (3.17) and the upper bound
for $\alpha$ in (3.14) into (3.16) we get that
$\mathbb{P}_{X}\left(Y_{\Gamma}=0\right)\leq\frac{D_{0}}{n^{\delta}}$ for some
constant $D_{0}>0.$ The estimates (3.15) and (3.4) then complete the proof of
part $(a)$ of the Theorem.

For part $(b),$ we proceed in a similar manner as above with minor
modifications. Let $J_{\Gamma}$ be the event as defined in (3.3) with $G_{K}$
replaced by $G,$ then as in (3.4), we have that

$\mathbb{P}\left(J^{c}_{\Gamma}\right)\leq\frac{C}{n^{\nu}}.$ (3.18)

As before, let $X_{i},1\leq i\leq n$ be i.i.d. random variables uniformly
chosen from $\\{1,2,\ldots,r\\}$ that are also independent of $G$ and the edge
weights $\\{w(h)\\}.$ Assign colour $X_{i}$ to the vertex $i$ and let
$\mathbb{P}_{X}$ denote the distribution of $(X_{1},\ldots,X_{n}).$

For a copy $T$ of $\Gamma$ let $S_{T}$ be the event that $|X_{u}-X_{v}|\leq M$
for any two vertices $u,v\in T$ and let $R_{T}$ be the event that $T\in G.$
The term $Z_{\Gamma}=\sum_{T}1{1}(S_{T})1{1}(R_{T})$ is then an upper bound on
the number of $M-$good copies of $\Gamma.$ Let $T$ be isomorphic to $\Gamma$
and let $u,v$ be vertices in $T.$ Given the colour $X_{u},$ we get that
$|X_{v}-X_{u}|\leq M$ with probability at least $\frac{1}{r}$ and at most
$\frac{2M}{r}$ and since there are $v_{0}-1$ choices for $v,$ we get that

$\frac{1}{r^{v_{0}-1}}\leq\mathbb{P}_{X}(S_{T})\leq\left(\frac{2M}{r}\right)^{v_{0}-1}.$
(3.19)

Therefore if the event $J_{\Gamma}$ occurs then

$\displaystyle\mathbb{E}_{X}Z_{\Gamma}$ $\displaystyle\leq$ $\displaystyle
N_{\Gamma}(G)\left(\frac{2M}{r}\right)^{v_{0}-1}$ (3.20) $\displaystyle\leq$
$\displaystyle\mathbb{E}N_{\Gamma}(G)(1+\epsilon)\left(\frac{2M}{r}\right)^{v_{0}-1}$
$\displaystyle\leq$ $\displaystyle
D_{2}(1+\epsilon)(2M)^{v_{0}-1}n^{v_{0}-e_{0}\beta-\theta(v_{0}-1)}$
$\displaystyle=$ $\displaystyle\frac{D_{3}}{n^{|\zeta|}}$

for some constant $D_{3}>0,$ where the first inequality in (3.20) is true by
the occurrence of the event $J_{\Gamma}$ and the final estimate in (3.20) is
true since $\theta>\theta_{th}$ strictly. By the Markov inequality, we
therefore have that $\mathbb{P}_{X}(Z_{\Gamma}\geq
1)\leq\frac{D_{4}}{n^{|\zeta|}}$ for some constant $D_{4}>0$ and so the
estimate (3.18) obtains part $(b)$ of the Theorem.

### Acknowledgement

I thank Professors Rahul Roy, Thomas Mountford and C. R. Subramanian for
crucial comments and also thank IMSc and IISER Bhopal for my fellowships.

## References

  * [1] N. Alon and J. Spencer. (2008).  The Probabilistic Method.  Wiley Interscience.
  * [2] B. Bollobás. (2001).  Random Graphs.  Cambridge University Press.
  * [3] G. Chartrand, D. Erwin, P. Zhang, F. Harary. (2001).  Radio labelings of graphs.  Bull. Inst. Combin. Appl., 33 pp. 77-85.
  * [4] A. Dudek and P. Pralat. (2017).  On Some Multicolor Ramsey Properties of Random Graphs.  SIAM Journal on Discrete Mathematics, 31, 2079–2092.
  * [5] G. Ganesan. (2020).  Cliques and Chromatic Number in Multiregime Random Graphs.  Sankhya, $doi:https://doi.org/10.1007/s13171-020-00205-4.$
  * [6] S. Janson, T. Luczak and A. Rucinski. (2000).  Random Graphs.  John Wiley.
  * [7] D. Korze, Z. Shao and A. Vesel. (2021).  New results on radio $k-$labelings of distance graphs.  Discrete Applied Mathematics, Available online, September 2021.
  * [8] A. Liebenau, L. Mattos, W. Mendonca, J. Skokan. (2022).  Asymmetric Ramsey Properties of Random Graphs for Cliques and Cycles.  Random Structures and Algorithms, July, https://doi.org/10.1002/rsa.21106.
  * [9] T. Luczak, A. Ruciński and B. Voigt. (1992).  Ramsey Properties of Random Graphs.  Journal of Combinatorial Theory Series B, 56, 55–68.
  * [10] V. Rödl, A. Ruciński, M. Schacht. (2017).  Ramsey Properties of Random Graphs and Folkmann numbers.  Discussiones Mathematicae Graph Theory, 27, 755–776.
  * [11] D. West. (2000).  Introduction to Graph Theory.  Prentice Hall.