# Linear maps preserving separability of pure states

Jinchuan Hou  Department of Mathematics
Taiyuan University of Technology
Taiyuan 030024, P. R. of China<EMAIL_ADDRESS>and  Xiaofei Qi
Department of Mathematics, Shanxi University, Taiyuan 030006, P. R. of China;
<EMAIL_ADDRESS>
###### Abstract.

Linear maps preserving pure states of a quantum system of any dimension are
characterized. This is then used to establish a structure theorem for linear
maps that preserve separable pure states in multipartite systems. As an
application, a characterization of separable pure state preserving affine maps
is obtained.

2010 Mathematics Subject Classification. 47B49; 47N50; 47A80

Key words and phrases. Linear maps, affine maps, quantum states, separability,
tensor products

This work is supported by National Natural Science Foundation of China
(11171249, 11101250) and Youth Foundation of Shanxi Province (2012021004).

##  1\. Introduction

A quantum state $\rho$ is a density operator acting on a complex Hilbert space
which is positive semidefinite and has trace 1. Furthermore, $\rho$ is a pure
state if $\rho^{2}=\rho$ (i.e., $\rho$ is a rank-1 projection); $\rho$ is a
mixed state if $\rho^{2}\not=\rho$. Denote by ${\mathcal{S}}(H)$ the set of
all states on a Hilbert space $H$. In quantum information theory we deal, in
general, with multipartite systems. The underlying space $H$ of a multipartite
composite quantum system is a tensor product of underlying spaces $H_{i}$ of
its subsystems, that is, $H=H_{1}\otimes H_{2}\otimes\cdots\otimes H_{n}$. In
the case $n=2$ the system is called a bipartite system. If $H$ and $K$ are
finite dimensional Hilbert spaces, $\rho\in{\mathcal{S}}(H\otimes K)$ is said
to be separable if $\rho$ can be written as

$None$ $\rho=\sum_{i=1}^{k}p_{i}\rho_{i}\otimes\sigma_{i},$

where $\rho_{i}$ and $\sigma_{i}$ are states on $H$ and $K$ respectively, and
$p_{i}$ are positive numbers with $\sum_{i=1}^{k}p_{i}=1$. Otherwise, $\rho$
is said to be inseparable or entangled (ref. [1, 6]). For the case that at
least one of $H$ and $K$ is of infinite dimension, by Werner [7], a state
$\rho$ acting on $H\otimes K$ is called separable if it can be approximated in
the trace norm by states of the form (0.1). Otherwise, $\rho$ is called an
entangled state. The full separability of multipartite states can be defined
similarly.

Entanglement is a basic physical resource to realize various quantum
information and quantum communication tasks [3, 4, 6]. So it is important to
determine whether or not a state in a composite system is separable, which is
also a very difficult task in this field. Thus, this makes it interesting to
find linear maps sending states to states, which will simplify a given state
so that it is easier to detect the entanglement in it. Clearly, such linear
maps should leave the separability of states invariant. So, this proposes the
question of studying linear preservers of separable states. This question was
attacked in [2] for the finite dimensional systems. Let ${\bf H}_{N}$ be the
real linear space of all $N\times N$ Hermitian matrices. It was shown in [2]
that, if a surjective linear map $\Phi:{\bf H}_{n_{1}n_{2}}\rightarrow{\bf
H}_{n_{1}n_{2}}$ preserves separable pure states in the bipartite system
${\mathbb{C}}^{n_{1}}\otimes{\mathbb{C}}^{n_{2}}$, then $\Phi$ sends product
states to product states, that is, $\Phi(A_{1}\otimes
A_{2})=\psi_{1}(A_{p_{1}})\otimes\psi_{2}(A_{p_{2}})$, where $(p_{1},p_{2})$
is a permutation of $(1,2)$, $n_{j}=n_{{p_{j}}}$ and
$\psi_{j}:M_{n_{j}}\rightarrow M_{n_{j}}$ is a linear map of the form
$X\mapsto U_{j}XU_{j}^{*}$ or $X\mapsto U_{j}X^{\rm t}U_{j}^{*}$ for a unitary
matrix $U_{j}\in M_{n_{j}}$. Here $X^{\rm t}$ denotes the transposed matrix of
$X$. A similar result holds for finite dimensional multipartite systems.

The purpose of the present paper is to characterize general linear maps that
preserve separable pure states for both finite and infinite dimensional
systems. We remark that the results for finite dimensional systems are
somewhat different from that for infinite dimensional systems because the
linear maps on infinite dimensional spaces may not be continuous.

Let ${\mathcal{T}}(H)$ be the Banach space of trace-class operators on a
complex Hilbert space $H$ endowed with the trace-norm $\|\cdot\|_{\rm Tr}$.
Denote by ${\mathcal{T}}_{\rm sa}(H)$ and ${\mathcal{F}}_{\rm sa}(H)$ the
subspace of self-adjoint operators and finite-rank self-adjoint operators in
${\mathcal{T}}(H)$, respectively. Denote by ${\mathcal{P}ur}(H)$ the set of
pure states (i.e., rank-one projections) on $H$. We first consider in Section
2 the question of characterizing linear maps preserving pure states since this
is basic for the study of our main question. Let $H$ and $K$ be Hilbert spaces
of any dimension. It is shown that a linear map $\Phi:{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ satisfies
$\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$ if and only if $\Phi$
either has the form $A\mapsto{\rm Tr}(A)R+\phi(A)$ for all
$A\in{\mathcal{T}}_{\rm sa}(H)$; or $\dim H\leq\dim K$ and $\Phi$ has the form
$A\mapsto UAU^{*}+\phi(A)$ for all $A\in{\mathcal{T}}_{\rm sa}(H)$, where
$\phi:{\mathcal{T}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ is a
linear map vanishing on each finite-rank operator, $R\in{\mathcal{P}ur}(K)$
and $U:H\rightarrow K$ is a linear or conjugate linear isometry (Theorem 2.2).
Particularly, if $\Phi$ preserves pure states in both directions, then $\Phi$
has the second form with $U$ unitary or conjugate unitary. The main result of
this section generalizes a result in [2] for finite dimensional case.

In Section 3 we discuss the question of characterizing linear maps preserving
separable pure states of bipartite systems. Let ${\mathcal{S}}_{\rm
sep}(H\otimes K)$ stand for the convex set of all separable states on
$H\otimes K$. Denote by ${\mathcal{T}}_{\rm sep}(H\otimes K)$ the linear
manifold generated by ${\mathcal{S}}_{\rm sep}(H\otimes K)$ and
${\mathcal{F}}_{\rm sep}(H\otimes K)={\mathcal{T}}_{\rm sep}(H\otimes
K)\cap{\mathcal{F}}_{\rm sa}(H\otimes K)$. It is obvious that
${\mathcal{T}}_{\rm sep}(H\otimes K)\subseteq{\mathcal{T}}_{\rm sa}(H\otimes
K)$. Our main result gives a characterization of linear maps from
${\mathcal{T}}_{\rm sa}(H\otimes K)$ into itself which preserve separable pure
states (not necessarily in both directions). It turns out such maps have one
of nine forms on ${\mathcal{F}}_{\rm sep}(H\otimes K)$ (see Theorem 3.2).
However, for most situations they have a standard form ((6) or (7) in Theorem
3.2). As an application, we get a characterization of affine maps between
convex sets of states which preserve separable pure states in both directions.
Such a map is either of the form $\Phi(\rho)=(U_{1}\otimes
U_{2})\Lambda(\rho)(U_{1}\otimes U_{2})^{*}$ for all
$\rho\in{\mathcal{S}}_{\rm sep}(H\otimes K)$ or of the form
$\Phi(\rho)=(U_{1}\otimes U_{2})\Lambda(\theta(\rho))(U_{1}\otimes U_{2})^{*}$
for all $\rho\in{\mathcal{S}}_{\rm sep}(H\otimes K)$, where $U_{1}$ and
$U_{2}$ are unitary operators on $H$ and $K$, respectively, $\Lambda$ is one
of the identity map, the transpose, the partial transpose with respect to any
fixed product orthonormal basis of $H\otimes K$, and
$\theta:{\mathcal{T}}(H\otimes K)\rightarrow{\mathcal{T}}(K\otimes H)$ is the
swap determined by $\theta(A\otimes B)=B\otimes A$.

In Section 4, a brief discussion of the question for multipartite systems is
given. Some results similar to those in bipartite systems in Section 3 are
presented.

##  2\. Linear maps preserving pure states

The main purpose of this section is to characterize linear preservers of pure
states for infinite dimensional systems, which are also needed to characterize
separable pure state preservers in the next section.

The following proposition comes from [2], which can be viewed as a
characterization of linear preservers of pure states for finite dimensional
systems.

Let ${\bf H}_{m}$ be the real linear space of all $m\times m$ Hermitian
matrices and let ${\mathcal{P}}_{m}$ be the set of all rank-1 $m\times m$
projection matrices.

Proposition 2.1. Suppose that $\phi:{\bf H}_{m}\rightarrow{\bf H}_{n}$ is
linear and satisfies $\phi({\mathcal{P}}_{m})\subseteq{\mathcal{P}}_{n}$. Then
one of the following holds:

(i) There is $Q\in{\mathcal{P}}_{n}$ such that $\phi(A)={\rm Tr}(A)Q$ for all
$A\in{\bf H}_{m}$.

(ii) $m\leq n$ and there is a matrix $U\in M_{n\times m}$ with $U^{*}U=I_{m}$
such that $\phi(A)=UAU^{*}$ for all $A\in{\bf H}_{m}$, or $\phi(A)=UA^{\rm
t}U^{*}$ for all $A\in{\bf H}_{m}$.

By using a result due to [5], we can generalize Proposition 2.1 to the
infinite dimensional case. Recall that a linear map $V:H\rightarrow K$ is an
isometry if $\|Vx\|=\|x\|$ for all $x\in H$, or equivalently, $V^{*}V=I_{H}$,
the identity operator on $H$. A conjugate linear isometry is defined
similarly.

The following is the main result of this section.

Theorem 2.2. Let $H$ and $K$ be Hilbert spaces of any dimension. Suppose that
$\Phi:{\mathcal{T}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ is a real
linear map. Then $\Phi$ satisfies
$\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$ if and only if there
exists a linear map $\phi:{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ vanishing on each finite-rank
operator and one of the following holds:

(i) There is some $R\in{\mathcal{P}ur}(K)$ such that $\Phi(A)={\rm
Tr}(A)R+\phi(A)$ for all $A\in{\mathcal{T}}_{\rm sa}(H)$.

(ii) $\dim H\leq\dim K$ and there is a linear or conjugate linear isometry
$U:H\rightarrow K$ such that $\Phi(A)=UAU^{*}+\phi(A)$ for all
$A\in{\mathcal{T}}_{\rm sa}(H)$.

Proof. Only the “only if” part should be checked.

Suppose that $\Phi$ preserves pure states. By Proposition 2.1, we may assume
that $\dim H=\infty$. Define a map $\Psi:{\mathcal{T}}_{\rm sa}(H\oplus
K)\rightarrow{\mathcal{T}}_{\rm sa}(H\oplus K)$ given by

$\Psi(S)=\Psi(\begin{bmatrix}A&C\\\
C^{*}&B\end{bmatrix})=\begin{bmatrix}0&0\\\ 0&\Phi(A)\end{bmatrix}$

for all

$S=\begin{bmatrix}A&C\\\ C^{*}&B\end{bmatrix}\in{\mathcal{T}}_{\rm sa}(H\oplus
K)\ {\rm with}\ A\in{\mathcal{T}}_{\rm sa}(H).$

It is obvious that $\Psi$ is linear and $\Psi(A\oplus 0)=0\oplus\Phi(A)$ for
all $A\in{\mathcal{T}}_{\rm sa}(H)$. Moreover, $\Psi$ is rank one decreasing,
that is, ${\rm rank}(\Psi(S))\leq 1$ whenever ${\rm rank}(S)=1$, since
$\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$. It follows that
$\Psi({\mathcal{F}}_{\rm sa}(H\oplus K))\subseteq{\mathcal{F}}_{\rm
sa}(H\oplus K)$, where ${\mathcal{F}}_{\rm sa}(H)$ stands for the set of all
finite-rank self-adjoint operators on $H$. Hence, by [5, Theorem 2.10], we get
that one of the following is true:

(1) $\Psi(S)=f(S)Q$ for all $S\in{\mathcal{F}}_{\rm sa}(H\oplus K)$, where
$f:{\mathcal{F}}_{\rm sa}(H\oplus K)\rightarrow{\mathbb{R}}$ is a linear map
and $Q$ is a rank one projection;

(2) $\Psi(x\otimes x)=\lambda Tx\otimes Tx$ for all $x\in H\oplus K$, where
$\lambda$ is a nonzero real number and $T:H\oplus K\rightarrow H\oplus K$ is a
linear or conjugate linear operator.

If (1) holds, then there exists some $R\in{\mathcal{P}ur}(K)$ such that
$Q=0\oplus R$ and $\Phi(A)=g(A)R$ for all $A\in{\mathcal{F}}_{\rm sa}(H)$,
where $g(A)=f(A\oplus 0)$. Since
$\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$, we have $g(P)=1$ for
all $P\in{\mathcal{P}ur}(H)$. Now, for any $A\in{\mathcal{F}}_{\rm sa}(H)$,
write $A=\sum_{i=1}^{n}\lambda_{i}P_{i}$, which is the spectral decomposition
of $A$. It follows from the linearity of $\Phi$ that
$g(A)=g(\sum_{i=1}^{n}\lambda_{i}P_{i})=\sum_{i=1}^{n}\lambda_{i}g(P_{i})=\sum_{i=1}^{n}\lambda_{i}={\rm
Tr}(A)$, that is, (i) holds for all finite-rank operators. Next let us show
that the statement (i) of Theorem 2.2 holds for all $A\in{\mathcal{T}}_{\rm
sa}(H)$. Note that $\Phi$ is bounded on the normed space ${\mathcal{F}}_{\rm
sa}(H)$ endowed with the trace-norm. In fact, $\|\Phi|_{{\mathcal{F}}_{\rm
sa}(H)}\|\leq\|R\|$. Let $\widehat{\Phi}:{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ be the bounded linear map defined
by $\widehat{\Phi}(A)={\rm Tr}(A)R$ and let $\phi=\Phi-\widehat{\Phi}$. Then,
$\phi(F)=0$ for each $F\in{\mathcal{F}}_{\rm sa}(H)$ and $\Phi(A)={\rm
Tr}(A)R+\phi(A)$ for all $A$, as desired.

Now assume that (2) holds. Note that $\Psi(A\oplus 0)=0\oplus\Phi(A)$. Then
$\Phi$ has the form $\Phi(x\otimes x)=\lambda Ux\otimes Ux$ for all $x\in H$,
where $U$ is the part of $T$ restricted to $H$. Next we prove that $U$ is
bounded. In fact, since $\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$,
we have

$None$ $\lambda\langle Ux,Ux\rangle=\lambda\|Ux\|^{2}=1$

for all unit vectors $x\in H$, which implies $\lambda>0$. Without loss of
generality, we may assume that $\lambda=1$. Since $U$ is linear or conjugate
linear, by Eq.(2.1), we get $\|Ux\|=\|x\|$ for all $x\in H$. It follows that
$U$ is bounded and $U^{*}U=I_{H}$, that is, $U$ is an isometry or conjugate
isometry. Then $\Phi(x\otimes x)=U(x\otimes x)U^{*}$, and consequently,
$\Phi(A)=UAU^{*}$ for all $A\in{\mathcal{F}}_{\rm sa}(H)$. Let
$\phi:{\mathcal{T}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(H)$ be the
linear map defined by $\phi(A)=\Phi(A)-UAU^{*}$ for every $A$. Then
$\Phi(A)=UAU^{*}+\phi(A)$ for all $A\in{\mathcal{T}}_{\rm sa}(H)$, that is,
(ii) of Theorem 2.2 holds.

The proof of the theorem is complete. $\Box$

Remark 2.3. If the linear map $\phi:{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(H)$ is not zero, then both $\Phi$ and
$\phi$ are not continuous because ${\mathcal{F}}_{\rm sa}(H)$ is dense in
${\mathcal{T}}_{\rm sa}(H)$. Such linear maps exist. For example, take any
nonzero linear map $\widehat{\phi}:{\mathcal{T}}_{\rm
sa}(H)/{\mathcal{F}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$, and let
$\phi$ be defined by $\phi(A)=\widehat{{\phi}}(\pi(A))$ for any
$A\in{\mathcal{T}}_{\rm sa}(H)$, where $\pi:{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(H)/{\mathcal{F}}_{\rm sa}(H)$ is the
quotient map.

The following corollary is immediate from Theorem 2.2.

Corollary 2.4. Let $H$ and $K$ be Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{T}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(K)$ is a
bounded real linear map. Then $\Phi$ satisfies
$\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$ if and only if one of
the following holds:

(i) There is some $R\in{\mathcal{P}ur}(K)$ such that $\Phi(A)={\rm Tr}(A)R$
for all $A\in{\mathcal{T}}_{\rm sa}(H)$.

(ii) There is a linear or conjugate linear isometry $U:H\rightarrow K$ with
$U^{*}U=I_{H}$ such that $\Phi(A)=UAU^{*}$ for all $A\in{\mathcal{T}}_{\rm
sa}(H)$.

Note that a bijective affine map from ${\mathcal{S}}(H)$ onto
${\mathcal{S}}(K)$ preserves pure states in both directions. So the following
corollary is a generalization of Kadison’s characterization of affine
isomorphisms on ${\mathcal{S}}(H)$, which says that a bijective affine map has
the form $\rho\mapsto U\rho U^{*}$, where $U$ is a unitary or conjugate
unitary operator (See, for instance, [1, Theorem 8.1]).

Corollary 2.5. Let $H$ and $K$ be Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{S}}(H)\rightarrow{\mathcal{S}}(K)$ is an affine map. Then
$\Phi$ satisfies $\Phi({\mathcal{P}ur}(H))\subseteq{\mathcal{P}ur}(K)$ if and
only if one of the following holds:

(i) There is some $R\in{\mathcal{P}ur}(K)$ such that $\Phi(\rho)=R$ for all
$\rho\in{\mathcal{S}}(H)$.

(ii) There is a linear or conjugate linear isometry $U:H\rightarrow K$ such
that $\Phi(\rho)=U\rho U^{*}$ for all $\rho\in{\mathcal{S}}(H)$.

Proof. We need only show that if
$\Phi:{\mathcal{S}}(H)\rightarrow{\mathcal{S}}(K)$ is affine and preserves
pure states, then $\Phi$ has the form (i) or the form (ii) stated in the
corollary.

To do this, note that the affinity of $\Phi$ allow us to extend it to a linear
map (see Ref. [2] for details), still denoted by $\Phi$, from
${\mathcal{T}}_{\rm sa}(H)$ into ${\mathcal{T}}_{\rm sa}(K)$. Every
$A\in{\mathcal{T}}_{\rm sa}(H)$ has a representation $A=A^{+}-A^{-}$ with
$A^{\pm}\geq 0$ and $A^{+}A^{-}=0$. Thus $\|A\|_{\rm Tr}=\|A^{+}\|_{\rm
Tr}+\|A^{-}\|_{\rm Tr}$. As $\|\Phi(\rho)\|_{\rm Tr}=\|\rho\|_{\rm Tr}$ for
all states $\rho$, we see that $\|\Phi(A)\|_{\rm Tr}\leq\|\Phi(A^{+})\|_{\rm
Tr}+\|\Phi(A^{-})\|_{\rm Tr}=\|A^{+}\|_{\rm Tr}+\|A^{-}\|_{\rm Tr}=\|A\|_{\rm
Tr}$. Hence $\Phi$ is bounded and, by Corollary 2.4, $\Phi$ has the desired
form. $\Box$

##  3\. linear maps preserving separable pure states: bipartite systems

Now we are ready to give a characterization of linear maps preserving
separable pure states for bipartite quantum systems.

Write ${\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)=\\{P\otimes
Q:P\in{\mathcal{P}ur}(H),\ Q\in{\mathcal{P}ur}(K)\\}$.

Lemma 3.1. Let $H$ and $K$ be any Hilbert spaces. Then the set of separable
states ${\mathcal{S}}_{\rm sep}(H\otimes K)$ is a convex set, whose extreme
points is ${\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$.

Proof. Obvious. $\Box$

Denote by ${\mathcal{T}}_{\rm sep}(H\otimes K)$ the real linear space
generated by ${\mathcal{S}}_{\rm sep}(H\otimes K)$, the set of all separable
states on $H\otimes K$; ${\mathcal{F}}_{\rm sep}(H\otimes K)$ the subspace of
all finite-rank operators in ${\mathcal{T}}_{\rm sep}(H\otimes K)$. We denote
by ${\rm Tr}_{i}$ the partial trace of the $i$th subsystem, that is, ${\rm
Tr}_{1}(\rho)={\rm Tr}_{H}(\rho)=({\rm Tr}\otimes I_{K})(\rho)$ and ${\rm
Tr}_{2}(\rho)={\rm Tr}_{K}(\rho)=(I_{H}\otimes{\rm Tr})(\rho)$. Clearly, ${\rm
Tr}_{i}$ is linear.

The following is the main result of this paper.

Theorem 3.2. Let $H$ and $K$ be two Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{T}}_{\rm sa}(H\otimes K)\rightarrow{\mathcal{T}}_{\rm
sa}(H\otimes K)$ is a linear map. Then
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))\subseteq{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
if and only if one of the following holds:

(1) There exists $R_{1}\otimes
R_{2}\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$ such that

$\Phi(F)={\rm Tr}(F)R_{1}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(2) There exist $R_{2}\in{\mathcal{P}ur}(K)$ and a linear or conjugate linear
isometry $U_{1}:H\rightarrow H$ such that

$\Phi(F)=U_{1}[{\rm Tr}_{2}(F)]U_{1}^{*}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(3) There exist $R_{1}\in{\mathcal{P}ur}(H)$ and a linear or conjugate linear
isometry $U_{2}:K\rightarrow K$ such that

$\Phi(F)=R_{1}\otimes U_{2}[{\rm Tr}_{1}(F)]U_{2}^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(4) $\dim H\geq\dim K$, there exist $R_{2}\in{\mathcal{P}ur}(K)$ and a linear
or conjugate linear isometry $U_{1}:K\rightarrow H$ such that

$\Phi(F)=U_{1}[{\rm Tr}_{1}(F)]U_{1}^{*}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(5) $\dim H\leq\dim K$, there exist $R_{1}\in{\mathcal{P}ur}(H)$ and a linear
or conjugate linear isometry $U_{2}:H\rightarrow K$ such that

$\Phi(F)=R_{1}\otimes U_{2}[{\rm Tr}_{2}(F)]U_{2}^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(6) There exist linear or conjugate linear isometries $U_{1}:H\rightarrow H$
and $U_{2}:K\rightarrow K$ such that

$\Phi(F)=(U_{1}\otimes U_{2})F(U_{1}\otimes U_{2})^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(7) $\dim H=\dim K$, there exist linear or conjugate linear isometries
$U_{1}:K\rightarrow H$ and $U_{2}:H\rightarrow K$ such that

$\Phi(F)=(U_{1}\otimes U_{2})\theta(F)(U_{1}\otimes U_{2})^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$, where
$\theta:{\mathcal{T}}(H\otimes K)\rightarrow{\mathcal{T}}(K\otimes H)$ is the
swap determined by $\theta(A\otimes B)=B\otimes A$.

(8) $\dim K\leq\dim H$, there exist $R_{2}\in{\mathcal{P}ur}(K)$ and a linear
map $\phi_{1}:{\mathcal{F}}_{\rm sep}(H\otimes K)\rightarrow{\mathcal{F}}_{\rm
sa}(H)$ such that, for each $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$, $\phi_{1}(P\otimes
Q)=U_{P}QU_{P}^{*}=V_{Q}PV_{Q}^{*}$ for some linear or conjugate linear
isometries $U_{P}:K\rightarrow H$, $V_{Q}:H\rightarrow H$, and

$\Phi(F)=\phi_{1}(F)\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

(9) $\dim H\leq\dim K$, there exist $R_{1}\in{\mathcal{P}ur}(H)$ and a linear
map $\phi_{2}:{\mathcal{F}}_{\rm sep}(H\otimes K)\rightarrow{\mathcal{F}}_{\rm
sa}(K)$ such that, for each $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$, $\phi_{2}(P\otimes
Q)=U_{P}QU_{P}^{*}=V_{Q}PV_{Q}^{*}$ for some linear or conjugate linear
isometries $U_{P}:K\rightarrow K$, $V_{Q}:H\rightarrow K$, and

$\Phi(F)=R_{1}\otimes\phi_{2}(F)$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.

We remark that, in cases (6)-(9) of Theorem 3.2, it is possible to have one of
the isometries be linear and the other isometry be conjugate-linear.

Proof of Theorem 3.2. It is clear that if any one of (1)-(9) holds, then
$\Phi$ preserves separable pure states. So we only need to check the converse.

Assume that
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))\subseteq{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$.

Define two maps $\phi_{1}:({\mathcal{T}}_{\rm sa}(H),{\mathcal{T}}_{\rm
sa}(K))\rightarrow{\mathcal{T}}_{\rm sa}(H)$ and $\phi_{2}:({\mathcal{T}}_{\rm
sa}(H),{\mathcal{T}}_{\rm sa}(K))\rightarrow{\mathcal{T}}_{\rm sa}(K)$ by

$None$ $\phi_{1}(A,B)={\rm Tr}_{2}(\Phi(A\otimes B))\quad{\rm
and}\quad\phi_{2}(A,B)={\rm Tr}_{1}(\Phi(A\otimes B)).$

Fix a $Q\in{\mathcal{P}ur}(K)$. Then $\phi_{1}(\cdot,Q):{\mathcal{T}}_{\rm
sa}(H)\rightarrow{\mathcal{T}}_{\rm sa}(H)$ and
$\phi_{2}(\cdot,Q):{\mathcal{T}}_{\rm sa}(H)\rightarrow{\mathcal{T}}_{\rm
sa}(K)$ are both linear. By the assumption, we have

$\Phi(P\otimes Q)={\rm Tr}_{2}(\Phi(P\otimes Q))\otimes{\rm
Tr}_{1}(\Phi(P\otimes Q))=\phi_{1}(P,Q)\otimes\phi_{2}(P,Q)$

for all $P\in{\mathcal{P}ur}(H)$ and all $Q\in{\mathcal{P}ur}(K)$. It follows
that

$\phi_{1}({\mathcal{P}ur}(H),Q)\subseteq{\mathcal{P}ur}(H)\quad{\rm
and}\quad\phi_{2}({\mathcal{P}ur}(H),Q)\subseteq{\mathcal{P}ur}(K).$

Thus, applying Theorem 2.2 to $\phi_{1}(\cdot,Q)$ and $\phi_{2}(\cdot,Q)$,
respectively, we get that, either

(i) there is a pure state $R_{iQ}$ such that $\phi_{i}(A,Q)={\rm Tr}(A)R_{iQ}$
for all $A\in{\mathcal{F}}_{\rm sa}(H)$, $i=1,2$, or

(ii) there is a linear or conjugate linear operator $U_{iQ}$ with
$U_{iQ}^{*}U_{iQ}=I_{H}$ such that $\phi_{i}(A,Q)=U_{iQ}AU_{iQ}^{*}$ for all
$A\in{\mathcal{F}}_{\rm sa}(H)$, $i=1,2$.

Similarly, for any fixed $P\in{\mathcal{P}ur}(H)$, considering the maps
$\phi_{1}(P,\cdot):{\mathcal{T}}_{\rm sa}(K)\rightarrow{\mathcal{T}}_{\rm
sa}(H)$ and $\phi_{2}(P,\cdot):{\mathcal{T}}_{\rm
sa}(K)\rightarrow{\mathcal{T}}_{\rm sa}(K)$, we have that, either

(i′) there is a pure state $R_{iP}$ such that $\phi_{i}(P,B)={\rm
Tr}(B)R_{iP}$ for all $B\in{\mathcal{F}}_{\rm sa}(K)$, $i=1,2$, or

(ii′) there is a linear or conjugate linear operator $U_{iP}$ with
$U_{iP}^{*}U_{iP}=I_{K}$ such that $\phi_{i}(P,B)=U_{iP}BU_{iP}^{*}$ for all
$B\in{\mathcal{F}}_{\rm sa}(K)$, $i=1,2$.

Observe that, for $i=1,2$, $\phi_{i}(\cdot,Q)$s and $\phi_{i}(P,\cdot)$s are
continuous on ${\mathcal{F}}_{\rm sa}(H)$ for all $Q\in{\mathcal{P}ur}(K)$ and
on ${\mathcal{F}}_{\rm sa}(K)$ for all $P\in{\mathcal{P}ur}(H)$, respectively.

Now, we consider the map $\phi_{1}(\cdot,Q)$.

Claim 1. Either $\phi_{1}(\cdot,Q)$ has the form (i) for all
$Q\in{\mathcal{P}ur}(K)$ or $\phi_{1}(\cdot,Q)$ has the form (ii) for all
$Q\in{\mathcal{P}ur}(K)$.

Fix $A_{0}=e_{1}\otimes e_{1}-e_{2}\otimes e_{2}\in{\mathcal{F}}_{\rm sa}(H)$
and define a function $F:{\mathcal{P}ur}(K)\rightarrow{\mathbb{R}}$ by
$F(Q)=\|\phi_{1}(A_{0},Q)\|_{\rm Tr}$ for all $Q\in{\mathcal{P}ur}(K)$. Note
that $F(Q)=\|{\rm Tr}(A_{0})R_{1Q}\|_{\rm Tr}=0$ if $\phi_{1}$ has the form
(i) and $F(Q)=\|U_{iQ}A_{0}U_{iQ}^{*}\|_{\rm Tr}=\|A_{0}\|_{\rm Tr}={2}$ if
$\phi_{1}$ has the form (ii).

Take any two distinct $Q_{1},Q_{2}\in{\mathcal{P}ur}(K)$. Then there exist two
linearly independent unit vectors $x,y\in K$ such that $Q_{1}=x\otimes x$ and
$Q_{2}=y\otimes y$. For any $t\in[0,1]$, define

$Q(t)=\frac{1}{\|x+t(y-x)\|^{2}}(x+t(y-x))\otimes(x+t(y-x))\in{\mathcal{P}ur}(K).$

Clearly, $Q(0)=Q_{1}$ and $Q(1)=Q_{2}$. Note that, for each $t\in[0,1]$,
$\phi_{1}(\cdot,Q(t))$ has the form (i) or (ii). Let ${\mathcal{L}}={\rm
span}\\{A_{0}\otimes Q(t):t\in[0,1]\\}$. It is clear that ${\mathcal{L}}$ is a
finite dimensional subspace of ${\mathcal{T}}_{\rm sep}(H\otimes K)$ and hence
$\Phi|_{{\mathcal{L}}}$ is continuous. It follows that
$\phi_{1}(\cdot,Q)|_{{\mathcal{L}}}$ is continuous and hence $t\mapsto
F(Q(t))$ is a continuous map. As $F(Q(t))$ can take only two possible distinct
values, it must be a constant. So Claim 1 holds.

Similarly, we have

Claim 1′. Either $\phi_{2}(\cdot,Q)$ has the form (i) for all
$Q\in{\mathcal{P}ur}(K)$ or $\phi_{2}(\cdot,Q)$ has the form (ii) for all
$Q\in{\mathcal{P}ur}(K)$.

Claim 2. One of the following holds:

(a) For all $Q\in{\mathcal{P}ur}(K)$, both $\phi_{1}(\cdot,Q)$ and
$\phi_{2}(\cdot,Q)$ have the form (i).

(b) For all $Q\in{\mathcal{P}ur}(K)$, $\phi_{1}(\cdot,Q)$ has the form (i) and
$\phi_{2}(\cdot,Q)$ has the form (ii).

(c) For all $Q\in{\mathcal{P}ur}(K)$, $\phi_{1}(\cdot,Q)$ has the form (ii)
and $\phi_{2}(\cdot,Q)$ has the form (i).

We need only to check that, for all $Q\in{\mathcal{P}ur}(K)$,
$\phi_{1}(\cdot,Q)$ and $\phi_{2}(\cdot,Q)$ can not have the form (ii)
simultaneously. Suppose there exists some $Q_{0}\in{\mathcal{P}ur}(K)$ such
that both $\phi_{1}(\cdot,Q_{0})$ and $\phi_{2}(\cdot,Q_{0})$ are of the form
(ii). So there exist isometric or conjugate isometric operators
$U_{1Q_{0}}:H\rightarrow H$ and $U_{2Q_{0}}:H\rightarrow K$ such that
$\phi_{i}(A,Q_{0})=U_{iQ_{0}}AU_{iQ_{0}}^{*}$ for all $A\in{\mathcal{F}}_{\rm
sa}(H)$, $i=1,2$. Thus, we must have $\dim H\leq\dim K$ and

$None$ $\Phi(P\otimes
Q_{0})=\phi_{1}(P,Q_{0})\otimes\phi_{2}(P,Q_{0})=U_{1Q_{0}}PU_{1Q_{0}}^{*}\otimes
U_{2Q_{0}}PU_{2Q_{0}}^{*}=U(P\otimes P)U^{*}$

for all $P\in{\mathcal{P}ur}(H)$, where $U=U_{1Q_{0}}\otimes
U_{2Q_{0}}:H\otimes H\rightarrow H\otimes K$. Particularly, take
$P_{1}=e_{1}\otimes e_{1}$, $P_{2}=e_{2}\otimes e_{2}$,
$P_{3}=\frac{1}{2}(e_{1}\otimes e_{1}+e_{1}\otimes e_{2}+e_{2}\otimes
e_{1}+e_{2}\otimes e_{2})$ and $P_{4}=\frac{1}{2}(e_{1}\otimes
e_{1}-e_{1}\otimes e_{2}-e_{2}\otimes e_{1}+e_{2}\otimes e_{2})$. Then
$P_{1}+P_{2}=P_{3}+P_{4}$ and so $P_{1}\otimes Q_{0}+P_{2}\otimes
Q_{0}=P_{3}\otimes Q_{0}+P_{4}\otimes Q_{0}$. However, by a simple
calculation, $P_{1}\otimes P_{1}+P_{2}\otimes P_{2}\not=P_{3}\otimes
P_{3}+P_{4}\otimes P_{4}$. Note that

$\Phi(P_{1}\otimes Q_{0}+P_{2}\otimes Q_{0})=U(P_{1}\otimes P_{1}+P_{2}\otimes
P_{2})U^{*}$

and

$\Phi(P_{3}\otimes Q_{0}+P_{4}\otimes Q_{0})=U(P_{3}\otimes P_{3}+P_{4}\otimes
P_{4})U^{*}.$

It follows that $\Phi(P_{1}\otimes Q_{0}+P_{2}\otimes
Q_{0})\not=\Phi(P_{3}\otimes Q_{0}+P_{4}\otimes Q_{0})$, a contradiction. So
the claim is true.

Similarly, one can check that

Claim 3. One of the following holds:

(a′) For all $P\in{\mathcal{P}ur}(H)$, both $\phi_{1}(P,\cdot)$ and
$\phi_{2}(P,\cdot)$ have the form (i′).

(b′) For all $P\in{\mathcal{P}ur}(H)$, $\phi_{1}(P,\cdot)$ has the form (i′)
and $\phi_{2}(P,\cdot)$ has the form (ii′).

(c′) For all $P\in{\mathcal{P}ur}(H)$, $\phi_{1}(P,\cdot)$ has the form (ii′)
and $\phi_{2}(P,\cdot)$ has the form (i′).

Claim 4. If (a) and (a′) hold, then there exists $R_{1}\otimes
R_{2}\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$ such that

$\Phi(F)={\rm Tr}(F)R_{1}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. Hence $\Phi$ has the form
(1).

Suppose that (a) and (a′) hold, that is, for all $Q\in{\mathcal{P}ur}(K)$, we
have $\phi_{i}(A,Q)={\rm Tr}(A)R_{iQ}$, and, for all $P\in{\mathcal{P}ur}(H)$,
we have $\phi_{i}(P,B)={\rm Tr}(B)R_{iP}$. Fix $P_{0}\in{\mathcal{P}ur}(H)$
and $Q_{0}\in{\mathcal{P}ur}(K)$. Then we get

$\phi_{i}(P,Q)=\phi_{i}(P,Q_{0})=\phi_{i}(P_{0},Q_{0})=R_{i}.$

Therefore, $\Phi(P\otimes Q)=R_{1}\otimes R_{2}$ for all $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$. By the linearity of $\Phi$,
one sees that Claim 4 is true.

Claim 5. If (a) and (b′) hold, then $\Phi$ has the form (3).

In this case, for any $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$, we have

$\Phi(P\otimes Q)=R_{1Q}\otimes R_{2Q}=R_{1P}\otimes U_{2P}QU_{2P}^{*},$

which implies that $R_{1Q}=R_{1P}$ is independent of $P,Q$ and
$U_{2P}QU_{2P}^{*}=R_{2Q}$ is independent of $P$. So there exist
$R_{1}\in{\mathcal{P}ur}(H)$ and a linear or conjugate linear isometry $U_{2}$
such that $\Phi(P\otimes Q)=R_{1}\otimes U_{2}QU_{2}^{*}=R_{1}\otimes
U_{2}[{\rm Tr}_{1}(P\otimes Q)]U_{2}^{*}$ for all separable pure states
$P\otimes Q$. Now by the linearity of $\Phi$, the claim is true.

Similarly, one can show the following Claims 6-8.

Claim 6. If (a) and (c′) hold, then (4) holds, that is, there exist
$R_{2}\in{\mathcal{P}ur}(K)$ and a linear or conjugate linear isometry
$U_{1}:K\rightarrow H$ such that

$\Phi(F)=U_{1}[{\rm Tr}_{1}(F)]U_{1}^{*}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. In this case we must have
$\dim H\geq\dim K$.

Claim 7. If (b) and (a′) hold, then $\Phi$ has the form (5), that is, there
exist $R_{1}\in{\mathcal{P}ur}(H)$ and a linear or conjugate linear isometry
$U_{2}:H\rightarrow K$ such that

$\Phi(F)=R_{1}\otimes U_{2}[{\rm Tr}_{2}(F)]U_{2}^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. In this case $\dim
H\leq\dim K$.

Claim 8. If (c) and (a′) hold, then there exist $R_{2}\in{\mathcal{P}ur}(K)$
and a linear or conjugate linear isometry $U_{1}:H\rightarrow H$ such that

$\Phi(F)=U_{1}[{\rm Tr}_{2}(F)]U_{1}^{*}\otimes R_{2}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. Hence $\Phi$ takes the form
(2).

Claim 9. If (b) and (c′) hold, then $\Phi$ has the form (7).

Now suppose that (b) and (c′) hold. Then

$\phi_{2}(\cdot,Q_{0})=U_{2Q_{0}}(\cdot)U_{2Q_{0}}^{*}\quad{\rm
and}\quad\phi_{1}(P_{0},\cdot)=U_{1P_{0}}(\cdot)U_{1P_{0}}^{*}$

with $U_{2Q_{0}}^{*}U_{2Q_{0}}=I_{H}$ and $U_{1P_{0}}^{*}U_{1P_{0}}=I_{K}$.
Moreover,

$\phi_{1}(P_{0},Q)={\rm Tr}(P_{0})R_{1Q}={\rm Tr}(P)R_{1Q}=\phi_{1}(P,Q)$

and

$\phi_{2}(P,Q_{0})={\rm Tr}(Q_{0})R_{2P}={\rm Tr}(Q)R_{2P}=\phi_{2}(P,Q).$

Thus, we obtain

$\Phi(P\otimes
Q)=\phi_{1}(P,Q)\otimes\phi_{2}(P,Q)=\phi_{1}(P_{0},Q)\otimes\phi_{2}(P,Q_{0})=U_{1P_{0}}QU_{1P_{0}}^{*}\otimes
U_{2Q_{0}}PU_{2Q_{0}}^{*}$

for all $P\in{\mathcal{P}ur}(H)$ and $Q\in{\mathcal{P}ur}(K)$. Let
$U_{1}=U_{1P_{0}}$ and $U_{2}=U_{2Q_{0}}$. Then $\Phi(P\otimes
Q)=(U_{1}\otimes U_{2})(Q\otimes P)(U_{1}\otimes U_{2})^{*}=(U_{1}\otimes
U_{2})\theta(P\otimes Q)(U_{1}\otimes U_{2})^{*}$ for all separable pure
states $P\otimes Q$. Obviously, $\dim H=\dim K$ in this case. It follows from
the linearity of $\Phi$ that the claim is true.

Similarly, we have

Claim 10. If (c) and (b′) hold, then there exist linear or conjugate linear
isometries $U_{1}:H\rightarrow H$ and $U_{2}:K\rightarrow K$ such that

$\Phi(F)=(U_{1}\otimes U_{2})F(U_{1}\otimes U_{2})^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. Hence in this case we have
(6).

Claim 11. If (b) and (b′) hold, then $\Phi$ has the form (9).

Assume (b) and (b′) hold synchronously. Then for any $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$, we have $\Phi(P\otimes
Q)=R_{1Q}\otimes U_{2Q}PU_{2Q}^{*}=R_{1P}\otimes U_{2P}QU_{2P}^{*}$. It
follows that there exists $R_{1}\in{\mathcal{P}ur}(H)$ such that
$R_{1Q}=R_{1P}=R_{1}$ and $U_{2Q}PU_{2Q}^{*}=U_{2P}QU_{2P}^{*}$ for all $P,Q$.
Thus there exists a linear map $\phi_{2}:{\mathcal{F}}_{\rm sep}(H\otimes
K)\rightarrow{\mathcal{F}}_{\rm sa}(K)$ such that, for each $P\otimes
Q\in{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$, $\phi_{2}(P\otimes
Q)=U_{P}QU_{P}^{*}=V_{Q}PV_{Q}^{*}$ for some linear or conjugate linear
isometries $U_{P}:K\rightarrow K$, $V_{Q}:H\rightarrow K$, and

$\Phi(F)=R_{1}\otimes\phi_{2}(F)$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$. In this case $\dim
H\leq\dim K$. So the claim is true.

Similarly,

Claim 12. If (c) and (c′) hold, then $\Phi$ takes the form (8).

The proof of the theorem is complete. $\Box$

The cases (8) and (9) of Theorem 3.2 seem not as natural as the other forms.
We do not know whether or not they may really occur. It raises another
interesting question of characterizing the real linear maps from
${\mathcal{F}}_{\rm sep}(H\otimes K)$ into ${\mathcal{F}}_{\rm sa}(H)$ that
send separable pure states to pure states.

Corollary 3.3. Let $H$ and $K$ be two Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{T}}_{\rm sa}(H\otimes K)\rightarrow{\mathcal{T}}_{\rm
sa}(H\otimes K)$ is a linear map satisfying
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))\subseteq{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
and $\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))$ contains two elements
$P^{\prime}_{i}\otimes Q^{\prime}_{i}$, $i=1,2$, with
$\\{P_{1}^{\prime},P_{2}^{\prime}\\}$ and
$\\{Q_{1}^{\prime},Q_{2}^{\prime}\\}$ linearly independent sets. Then $\Phi$
has the form (6) or (7) in Theorem 3.2.

In the case of finite dimension, we get a generalization of the main result
obtained in [2]; there the condition
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))={\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
is assumed.

Corollary 3.4. Let $H$ and $K$ be two finite-dimensional Hilbert spaces.
Suppose that $\Phi:{\mathcal{T}}_{\rm sa}(H\otimes
K)\rightarrow{\mathcal{T}}_{\rm sa}(H\otimes K)$ is a linear map. Then
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))\subseteq{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
if and only if one of the statements (1)-(9) holds for all
$A\in{\mathcal{T}}_{\rm sep}(H\otimes K)$.

Let $\\{e_{i}\\}_{i=1}^{\dim H}$ and $\\{u_{j}\\}_{j=1}^{\dim K}$ be
orthonormal bases of $H$ and $K$ respectively. With respect to the product
basis $\\{e_{i}\otimes u_{j}\\}_{i,j}$ of $H\otimes K$, the linear map ${\bf
T}\otimes{\rm id}:{\mathcal{T}}(H\otimes K)\rightarrow{\mathcal{T}}(H\otimes
K)$ determined by $A\otimes B\mapsto A^{T}\otimes B$ is called the partial
transpose of the first system. The partial transpose of the second system
${\rm id}\otimes{\bf T}$ is defined similarly. In terms of partial
transposition, one can restate Theorem 3.2 to avoid the term “conjugate
linear”. In fact, if $U$ is a conjugate isometry, then there exists an
isometry $V$ such that $UAU^{*}=VA^{\rm t}V^{*}$ for all $A$.

In the finite dimensional case, for a linear map $\Phi$, surjectivity and
separable pure state preserving is equivalent to preserving separable pure
states in both directions, and in turn, is equivalent to
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))={\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$.
But for the infinite dimensional case, bijectivity and separable pure state
preserving might not imply that $\Phi$ preserves separable pure states in both
directions.

The next result is a characterization of linear maps preserving separable pure
states in both directions. We state it avoiding the term “conjugate linear”.

Corollary 3.5. Let $H$ and $K$ be two Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{T}}_{\rm sa}(H\otimes K)\rightarrow{\mathcal{T}}_{\rm
sa}(H\otimes K)$ is a linear map. Then the following conditions are
equivalent.

(1) $\Phi$ preserves separable pure states in both directions.

(2)
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))={\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$.

(3) Either

(i) There exist unitary operators $U_{1}\in{\mathcal{B}}(H)$ and
$U_{2}\in{\mathcal{B}}(K)$ such that

$\Phi(F)=(U_{1}\otimes U_{2})\Lambda(F)(U_{1}\otimes U_{2})^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$; or

(ii) $\dim H=\dim K$, there exist unitary operators
$U_{1}\in{\mathcal{B}}(K,H)$ and $U_{2}\in{\mathcal{B}}(H,K)$ such that

$\Phi(F)=(U_{1}\otimes U_{2})\Lambda(\theta(F))(U_{1}\otimes U_{2})^{*}$

for all $F\in{\mathcal{F}}_{\rm sep}(H\otimes K)$.
Here $\Lambda$ is one of the identity map, the transpose, a partial transpose
with respect to any fixed product orthonormal basis of $H\otimes K$, and
$\theta:{\mathcal{T}}(H\otimes K)\rightarrow{\mathcal{T}}(K\otimes H)$ is the
swap determined by $\theta(A\otimes B)=B\otimes A$.

Proof. (3)$\Rightarrow$(1)$\Rightarrow$(2) are obvious. For
(2)$\Rightarrow$(3), by Corollary 3.3, we see that
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))={\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
implies that the statement (6) or (7) in Theorem 3.2 holds. Moreover, the
linear or conjugate linear isometries involved are all surjective and hence
unitary or conjugate unitary. $\Box$

Remark 3.6. Note that, by the proof of Theorem 3.2, the assumption of
$\Phi:{\mathcal{T}}_{\rm sa}(H\otimes K)\rightarrow{\mathcal{T}}_{\rm
sa}(H\otimes K)$ may be replaced by the assumption of $\Phi:{\mathcal{T}}_{\rm
sep}(H\otimes K)\rightarrow{\mathcal{T}}_{\rm sep}(H\otimes K)$, and the
results of Theorem 3.2, Corollaries 3.3-3.5 remain true. This remark is useful
in some applications.

As an application of Theorem 3.2, let us consider the separable pure state
preserving maps between states of bipartite systems.

Theorem 3.7. Let $H$ and $K$ be two Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{S}}(H\otimes K)\rightarrow{\mathcal{S}}(H\otimes K)$ is
an affine map. Then the following statements are equivalent.

(1)
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))\subseteq{\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$
.

(2) The conditions (1)-(9) in Theorem 3.2 hold for all
$\rho\in{\mathcal{S}}_{\rm sep}(H\otimes K)$.

Proof. (2)$\Rightarrow$(1) is obvious.

(1)$\Rightarrow$(2). As $\Phi$ is affine, it can be extended to a real linear
map from ${\mathcal{T}}_{\rm sa}(H\otimes K)$ into ${\mathcal{T}}_{\rm
sa}(H\otimes K)$ which still sends separable pure states to separable pure
states. Furthermore, the fact $\Phi({\mathcal{S}}(H\otimes
K))\subseteq{\mathcal{S}}(H\otimes K)$ implies that $\Phi$ is continuous, and
then, applying Theorem 3.2, one sees that (2) holds. $\Box$

Corollary 3.8. Let $H$ and $K$ be two Hilbert spaces of any dimension. Suppose
that $\Phi:{\mathcal{S}}(H\otimes K)\rightarrow{\mathcal{S}}(H\otimes K)$ is
an affine map. Then the following statements are equivalent.

(1) $\Phi$ preserves separable states in both directions.

(2) $\Phi$ preserves separable pure states in both directions.

(3) Either

(i) There exist unitary operators $U_{1}\in{\mathcal{B}}(H)$ and
$U_{2}\in{\mathcal{B}}(K)$ such that

$\Phi(\rho)=(U_{1}\otimes U_{2})\Lambda(\rho)(U_{1}\otimes U_{2})^{*}$

for all $\rho\in{\mathcal{S}}_{\rm sep}(H\otimes K)$; or

(ii) $\dim H=\dim K$, there exist unitary operators
$U_{1}\in{\mathcal{B}}(K,H)$ and $U_{2}\in{\mathcal{B}}(H,K)$ such that

$\Phi(\rho)=(U_{1}\otimes U_{2})\Lambda(\theta(\rho))(U_{1}\otimes U_{2})^{*}$

for all $\rho\in{\mathcal{S}}_{\rm sep}(H\otimes K)$.
Here $\Lambda$ is one of the identity map, the transpose, a partial transpose
with respect to any fixed product orthonormal basis of $H\otimes K$, and
$\theta:{\mathcal{T}}(H\otimes K)\rightarrow{\mathcal{T}}(K\otimes H)$ is the
swap determined by $\theta(A\otimes B)=B\otimes A$.

Proof. (3)$\Rightarrow$(1) is obvious.

(1)$\Rightarrow$(2): $\Phi$ preserves separable states in both directions
implies that $\Phi|_{{\mathcal{S}}_{\rm sep}(H\otimes K)}:{\mathcal{S}}_{\rm
sep}(H\otimes K)\rightarrow{\mathcal{S}}_{\rm sep}(H\otimes K)$ is a bijective
affine map. Note that an affine isomorphism between two convex sets preserves
extreme points in both directions. Hence $\Phi$ preserves separable pure
states in both directions and (2) is true.

(2)$\Rightarrow$(3): Assume that (2) holds; then
$\Phi({\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K))={\mathcal{P}ur}(H)\otimes{\mathcal{P}ur}(K)$.
By Theorem 3.7 and Corollary 3.5, we see that either (i) or (ii) holds for
$\Phi$ and all separable states $\rho$, that is, (3) is true. $\Box$

##  4\. linear maps preserving separable pure states: multipartite systems

Results similar to that in Section 3 for bipartite cases are valid for
multipartite cases also, but with more complicated expressions. The techniques
of the proofs are almost identical to those used in the preceding part of the
paper and in [2]. In this section we only list those results which have
relatively simple expressions and which may have more applications. The
meanings of the notations used here are also similar to that in Section 2. For
example, ${\mathcal{S}}_{\rm sep}(H_{1}\otimes H_{2}\otimes\cdots\otimes
H_{n})$ denotes the closed convex hull of all fully separable states in
${\mathcal{S}}(H_{1}\otimes H_{2}\cdots\otimes H_{n})$.

The following result corresponds to Corollary 3.3.

Theorem 4.1. Let $H_{1},H_{2},\ldots,H_{n}$ be complex Hilbert spaces of any
dimensions and let $\Phi:{\mathcal{T}}_{\rm sa}(H_{1}\otimes
H_{2}\otimes\cdots\otimes H_{n})\rightarrow{\mathcal{T}}_{\rm sa}(H_{1}\otimes
H_{2}\otimes\cdots\otimes H_{n})$ be a linear map. Then
$\Phi({\mathcal{P}ur}(H_{1})\otimes\cdots\otimes{\mathcal{P}ur}(H_{n}))\subseteq{\mathcal{P}ur}(H_{1})\otimes\cdots\otimes{\mathcal{P}ur}(H_{n})$
and there are $P_{1}^{\prime}\otimes\cdots\otimes
P_{n}^{\prime}\in\Phi({\mathcal{P}ur}(H_{1})\otimes\cdots\otimes{\mathcal{P}ur}(H_{n}))$
and $Q_{1}^{\prime}\otimes\cdots\otimes
Q_{n}^{\prime}\in\Phi({\mathcal{P}ur}(H_{1})\otimes\cdots\otimes{\mathcal{P}ur}(H_{n}))$
with $\\{P_{i}^{\prime},Q_{i}^{\prime}\\}$ linearly independent for each
$i=1,2,\ldots,n$, if and only if there is a permutation
$\pi:(1,\ldots,n)\mapsto(p_{1},\ldots,p_{n})$ of $(1,\ldots,n)$ and linear or
conjugate linear isometries $U_{j}:H_{p_{j}}\rightarrow H_{j}$,
$j=1,\ldots,n$, such that

$None$ $\Phi(F)=(U_{1}\otimes\cdots\otimes
U_{n})\theta_{\pi}(F)(U_{1}^{*}\otimes\cdots\otimes U_{n}^{*})$

holds for all $F\in{\mathcal{F}}_{\rm sep}(H_{1}\otimes\cdots\otimes H_{n})$.
Here $\theta_{\pi}:{\mathcal{T}}_{\rm sa}(H_{1}\otimes
H_{2}\otimes\cdots\otimes H_{n})\rightarrow{\mathcal{T}}_{\rm
sa}(H_{p_{1}}\otimes H_{p_{2}}\otimes\cdots\otimes H_{p_{n}})$ is a linear map
determined by $\theta_{\pi}(A_{1}\otimes A_{2}\otimes\cdots\otimes
A_{n})=A_{p_{1}}\otimes A_{p_{2}}\otimes\cdots\otimes A_{p_{n}}$, and each
$U_{j}$ can be independently linear or conjugate-linear.

It is clear that, if $\Phi$ has the form Eq.(4.1), then $\dim
H_{p_{j}}\leq\dim H_{j}$. So, if $\dim H_{p_{j}}>\dim H_{j}$ for some $j$,
then $\Phi$ cannot take the form (4.1) for the permutation
$\pi:(1,\ldots,n)\mapsto(p_{1},\ldots,p_{n})$. Actually, $\dim H_{j}$ is
constant for all indices $j$ in a cycle of the permutation $\pi$.

The following is a special case corresponding to Theorem 3.7.

Theorem 4.2. A linear map $\Phi:{\mathcal{T}}_{\rm sa}(H_{1}\otimes
H_{2}\otimes\cdots\otimes H_{n})\rightarrow{\mathcal{T}}_{\rm sa}(H_{1}\otimes
H_{2}\otimes\cdots\otimes H_{n})$ satisfies the conditions of Theorem 4.1 and
the condition $\Phi({\mathcal{S}}(H_{1}\otimes\cdots\otimes
H_{n}))\subseteq{\mathcal{S}}(H_{1}\otimes\cdots\otimes H_{n})$ if and only if
Eq.(4.1) holds for all $\rho\in{\mathcal{T}}_{\rm
sep}(H_{1}\otimes\cdots\otimes H_{n})$.

Particularly,

Theorem 4.3. Let $H_{1},H_{2},\ldots,H_{n}$ be complex Hilbert spaces of any
dimensions and let $\Phi:{\mathcal{S}}(H_{1}\otimes H_{2}\otimes\cdots\otimes
H_{n})\rightarrow{\mathcal{S}}(H_{1}\otimes H_{2}\otimes\cdots\otimes H_{n})$
be an affine map. Then the following statements are equivalent.

(1) $\Phi$ preserves fully separable states in both directions.

(2) $\Phi$ preserves separable pure states in both directions.

(3) There is a permutation $\pi:(1,\ldots,n)\mapsto(p_{1},\ldots,p_{n})$ of
$(1,\ldots,n)$ and unitary or conjugate unitary operators
$U_{j}:H_{p_{j}}\rightarrow H_{j}$, $j=1,\ldots,n$, such that

$None$ $\Phi(\rho)=(U_{1}\otimes\cdots\otimes
U_{n})\theta_{\pi}(\rho)(U_{1}^{*}\otimes\cdots\otimes U_{n}^{*})$

holds for all $\rho\in{\mathcal{S}}_{\rm sep}(H_{1}\otimes\cdots\otimes
H_{n})$. Here, each $U_{j}$ can be independently linear or conjugate-linear.

Obviously, if $\Phi$ is of the form (4.2), then $\dim H_{p_{j}}=\dim H_{j}$.

Theorems 4.1-4.3 may be restated in terms of linear isometric (unitary)
operators and partial transpositions as in Corollaries 3.5 and 3.8, but with
more complicated expressions.

Acknowledgement. The authors wish to give their thanks to the referees. They
read the original manuscript carefully, made up some gaps and gave many
helpful suggestions to improve the paper.

## References

  * [1] I. Bengtsson, K. Zyczkowski, Geometry of Quantum States, An introduction to quantum entangument, Cambridge University Press, Cambridge, 2006.
  * [2] S. Friedland, C. K. Li, T. Y. Poon, N. S. Sze, The automorphism group of separable states in quantum information theory, J. Math. Phys., 52 (2011), 042203.
  * [3] M. Horodecki, P. Horodecki, R. Horodecki, Separability of mixed states: necessary and sufficient conditions, Phys. Lett. A, 223 (1996), 1.
  * [4] R. Horodecki, P. Horodecki, M. Horodecki, K. Horodecki, Quantum entanglement, Rev. Mod. Phys., 81 (2009), 865.
  * [5] M. H. Lim, Additive mappings between Hermitian matrix spaces preserving rank not exceeding one, Lin. Alg. Appl., 408 (2005), 259-267.
  * [6] M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2000.
  * [7] R. F. Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model, Phys. Rev. A, 40 (1989), 4277.


# The Ramsey number of books

David Conlon Supported by a Royal Society University Research Fellowship and
ERC Starting Grant 676632.

###### Abstract

We show that in every two-colouring of the edges of the complete graph $K_{N}$
there is a monochromatic $K_{k}$ which can be extended in at least
$(1+o_{k}(1))2^{-k}N$ ways to a monochromatic $K_{k+1}$. This result is
asymptotically best possible, as may be seen by considering a random
colouring. Equivalently, defining the book $B_{n}^{(k)}$ to be the graph
consisting of $n$ copies of $K_{k+1}$ all sharing a common $K_{k}$, we show
that the Ramsey number $r(B_{n}^{(k)})=2^{k}n+o_{k}(n)$. In this form, our
result answers a question of Erdős, Faudree, Rousseau and Schelp and
establishes an asymptotic version of a conjecture of Thomason.

title = The Ramsey number of books, author = David Conlon, plaintextauthor =
David Conlon, plaintexttitle = The Ramsey number of books, runningtitle = The
Ramsey number of books, runningauthor = David Conlon, copyrightauthor = D.
Conlon, keywords = Ramsey numbers, regularity method, Ramsey multiplicity,
year=2019, number=3, received=9 August 2018, published=30 October 2019,
doi=10.19086/aic.10808,

[classification=text]

##  1 Introduction

The Ramsey number $r(H)$ of a graph $H$ is the smallest natural number $N$
such that every two-colouring of the edges of the complete graph $K_{N}$
contains a monochromatic copy of $H$. The problem of determining Ramsey
numbers is notoriously hard. For instance, when $H$ is a complete graph, work
of Erdős and Szekeres [8, 12] in the 1930s and 40s showed that
$\sqrt{2}^{t}\leq r(K_{t})\leq 4^{t}$, but the only improvements to these
bounds since that time [3, 24] have been to lower order terms.

We investigate the Ramsey numbers of books, a study which bears close relation
to the problem of determining $r(K_{t})$. The book $B_{n}^{(k)}$ is the graph
consisting of $n$ copies of $K_{k+1}$, all sharing a common $K_{k}$. Embracing
the metaphor, we refer to the common $K_{k}$ as the spine of the book and the
$n$ points completing each copy of $K_{k+1}$ as the pages or leaves.

The Ramsey problem for these books was first studied by Erdős, Faudree,
Rousseau and Schelp [10] and then by Thomason [25]. Both papers contain bounds
of the form

$2^{k}n+o_{k}(n)\leq r(B_{n}^{(k)})\leq 4^{k}n,$

where the lower bound follows from considering the random graph $G(n,1/2)$ and
the upper bound from a standard neighbourhood chasing argument. In their
paper, Erdős et al. asked whether one of these bounds might be asymptotically
correct and Thomason conjectured that the lower bound is. In fact, he made a
very precise conjecture about the value of $r(B_{n}^{(k)})$, namely, that

$r(B_{n}^{(k)})\leq 2^{k}(n+k-2)+2.$

For $k=2$, this conjecture is known to hold [23] and is tight for infinitely
many values of $n$. The main contribution of this paper is a proof of an
approximate version of Thomason’s conjecture, thus answering the question of
Erdős et al. (see also [21]).

###### Theorem 1

For every natural number $k$,

$r(B_{n}^{(k)})=2^{k}n+o_{k}(n).$

To see something of why this is interesting, suppose that we have a red/blue-
colouring of $K_{N}$ with no monochromatic copy of $K_{t}$. Then this
colouring contains no monochromatic book $B_{n}^{(k)}$ with $n$ equal to the
off-diagonal Ramsey number $r(K_{t-k},K_{t})$. Indeed, suppose that the book
is red. If the set induced by the pages contains a blue $K_{t}$, we have a
contradiction, so it must contain a red $K_{t-k}$. But together with the red
spine $K_{k}$, this forms a red $K_{t}$. Hence, by Theorem 1, if $t$, and
therefore $n$, is sufficiently large in terms of $k$, we have

$r(K_{t})\leq r(B_{n}^{(k)})\leq 2^{k+1}r(K_{t-k},K_{t})\leq
2^{k+1}\binom{2t-k}{t-k},$

where the last inequality follows from a classical estimate of Erdős and
Szekeres [12]. In particular, if the theorem applied for $t$ linear in $k$,
this would give an exponential improvement on the upper bound for diagonal
Ramsey numbers. Unfortunately, our Theorem 1 is very far from achieving this
goal, since in order to obtain an error term of the form $\epsilon n$ we
require $n$ to be at least a tower of twos whose height is a function of $k$
and $1/\epsilon$.

Another motivation for Theorem 1 is its relation to a well-known, but false,
conjecture of Erdős [9] (see also [2]) asserting that every two-colouring of
the edges of $K_{N}$ contains at least

$(1+o_{k}(1))2^{1-\binom{k}{2}}\binom{N}{k}$

monochromatic copies of $K_{k}$. That is, he conjectured that a random
colouring should asymptotically minimise the number of monochromatic copies of
$K_{k}$. While true for $k=3$ by a result of Goodman [16], this conjecture was
disproved for $k\geq 4$ by Thomason [26]. However, Theorem 1 is equivalent to
a local version of Erdős’ conjecture, saying that there is some monochromatic
copy of $K_{k-1}$ which is contained in asymptotically as many monochromatic
$K_{k}$ as in a random colouring. In some ways, this interpretation is more
appealing than the original formulation in terms of books. It also connects
our result with the study of Ramsey multiplicity, which has drawn considerable
attention in recent years (see, for instance, [4, 7, 13, 19, 20]).

##  2 Preliminaries

In this section, we collect several results that we will need for the proof of
Theorem 1.

###  2.1 Regularity and counting lemmas

One of the main ingredients in our proof is a simple corollary of Szemerédi’s
regularity lemma. To state this fundamental result, we first recall some
standard definitions. Given two vertex sets $U$ and $V$ in a graph, the
density $d(U,V)$ between them is given by $d(U,V)=e(U,V)/|U||V|$. A bipartite
graph between two vertex sets $U$ and $V$ is said to be $\epsilon$-regular if,
for all sets $U^{\prime}\subseteq U$, $V^{\prime}\subseteq V$ with
$|U^{\prime}|\geq\epsilon|U|$ and $|V^{\prime}|\geq\epsilon|V|$,
$|d(U^{\prime},V^{\prime})-d(U,V)|\leq\epsilon$. A partition
$V(G)=\cup_{i=1}^{m}V_{i}$ of the vertex set of a graph $G$ is said to be
equitable if $||V_{i}|-|V_{j}||\leq 1$ for all $i$ and $j$. The regularity
lemma is now as follows.

###### Lemma 1

For every $0<\epsilon<1$ and natural number $m_{0}$, there exists a natural
number $M$ such that every graph $G$ with at least $m_{0}$ vertices has an
equitable partition $V(G)=\cup_{i=1}^{m}V_{i}$ with $m_{0}\leq m\leq M$ parts
such that all but $\epsilon m^{2}$ pairs $(V_{i},V_{j})$ with $1\leq i\neq
j\leq m$ are $\epsilon$-regular.

We will also need the following lemma from [5]. We say that a subset $U$ of
the vertex set of a graph $G$ is $\epsilon$-regular if the pair $(U,U)$ is
$\epsilon$-regular.

###### Lemma 2

For every $0<\epsilon<1$, there exists a constant $\delta$ such that every
graph $G$ contains an $\epsilon$-regular vertex subset $U$ with
$|U|\geq\delta|V(G)|$.

The key lemma we will need is the following. We note a superficial similarity
to a lemma used in the proof of the induced removal lemma [1], though that
lemma requires the stronger condition that every pair $(W_{i},W_{j})$ be
regular.

###### Lemma 3

For every $0<\eta<1$ and natural number $m_{0}$, there exists a natural number
$M$ such that every graph $G$ with at least $m_{0}$ vertices has an equitable
partition $V(G)=\cup_{i=1}^{m}V_{i}$ with $m_{0}\leq m\leq M$ parts and
subsets $W_{i}\subseteq V_{i}$ such that $W_{i}$ is $\eta$-regular for all $i$
and, for all but $\eta m^{2}$ pairs $(i,j)$ with $1\leq i\neq j\leq m$,
$(V_{i},V_{j})$, $(W_{i},V_{j})$ and $(W_{i},W_{j})$ are $\eta$-regular with
$|d(W_{i},V_{j})-d(V_{i},V_{j})|\leq\eta$ and
$|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq\eta$.

######  Proof 2.2.

Apply the regularity lemma, Lemma 1, to $G$ with
$\epsilon=\eta\cdot\delta(\eta)$, with $\delta$ as in Lemma 2. This yields an
equitable partition $V(G)=\cup_{i=1}^{m}V_{i}$ where all but $\epsilon
m^{2}\leq\eta m^{2}$ pairs $(V_{i},V_{j})$ with $1\leq i\neq j\leq m$ are
$\epsilon$-regular. Within each piece $V_{i}$, now apply Lemma 2 to find a set
$W_{i}$ of order at least $\delta(\eta)$ which is $\eta$-regular. Note that if
$(V_{i},V_{j})$ is $\epsilon$-regular, then, since $|W_{i}|\geq\delta|V_{i}|$
and $\epsilon=\eta\cdot\delta(\eta)$, the pairs $(W_{i},V_{j})$ and
$(W_{i},W_{j})$ are $\eta$-regular with
$|d(W_{i},V_{j})-d(V_{i},V_{j})|\leq\epsilon\leq\eta$ and
$|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq\eta$.

In order to apply Lemma 3, we need a standard counting lemma (see, for
example, [22, Theorem 18]). We use the shorthand $x\pm\delta$ to indicate a
quantity that lies between $x-\delta$ and $x+\delta$.

######  Lemma 2.3.

For any $\delta>0$ and any natural number $k$, there is $\eta>0$ such that if
$U_{1},\dots,U_{k}$ are (not necessarily distinct) vertex sets with
$(U_{i},U_{i^{\prime}})$ $\eta$-regular of density $d_{i,i^{\prime}}$ for all
$1\leq i<i^{\prime}\leq k$, then there are

$\prod_{i<i^{\prime}}d_{i,i^{\prime}}\prod_{i=1}^{k}|U_{i}|\pm\delta\prod_{i=1}^{k}|U_{i}|$

copies of $K_{k}$ with vertex $i$ in $U_{i}$ for each $1\leq i\leq k$.

In practice, we will always use this lemma in the following form.

######  Lemma 2.4.

For any $\delta>0$ and any natural number $k$, there is $\eta>0$ such that if
$U_{1},\dots,U_{k}$, $U_{k+1},\dots,U_{k+\ell}$ are (not necessarily distinct)
vertex sets with $(U_{i},U_{i^{\prime}})$ $\eta$-regular of density
$d_{i,i^{\prime}}$ for all $1\leq i<i^{\prime}\leq k$ and $1\leq i\leq
k<i^{\prime}\leq k+\ell$ and $d_{i,i^{\prime}}\geq\delta$ for all $1\leq
i<i^{\prime}\leq k$, then there is a copy of $K_{k}$ with vertex $i$ in
$U_{i}$ for each $1\leq i\leq k$ which is contained in at least

$\sum_{j=1}^{\ell}\left(\prod_{i=1}^{k}d_{i,k+j}-\delta\right)|U_{k+j}|$

copies of $K_{k+1}$ with vertex $k+1$ in $\cup_{j=1}^{\ell}U_{k+j}$.

######  Proof 2.5.

By Lemma 2.3 applied with $\delta^{\prime}=\delta^{\binom{k}{2}+1}/2$ instead
of $\delta$, there exists $\eta_{0}=\eta(\delta^{\prime},k)$ such that the
number of copies of $K_{k}$ with vertex $i$ in $U_{i}$ for each $1\leq i\leq
k$ is at most

$\prod_{1\leq i<i^{\prime}\leq
k}d_{i,i^{\prime}}\prod_{i=1}^{k}|U_{i}|+\delta^{\prime}\prod_{i=1}^{k}|U_{i}|.$

Moreover, by repeated application of Lemma 2.3 with $k+1$ parts, there exists
$\eta_{1}=\eta(\delta^{\prime},k+1)$ such that the number of copies of
$K_{k+1}$ with vertex $i$ in $U_{i}$ for each $1\leq i\leq k$ and vertex $k+1$
in $\cup_{j=1}^{\ell}U_{k+j}$ is at least

$\sum_{j=1}^{\ell}\prod_{i=1}^{k}d_{i,k+j}|U_{k+j}|\prod_{1\leq
i<i^{\prime}\leq
k}d_{i,i^{\prime}}\prod_{i=1}^{k}|U_{i}|-\delta^{\prime}\sum_{j=1}^{\ell}|U_{k+j}|\prod_{i=1}^{k}|U_{i}|.$

Therefore, for $\eta=\min(\eta_{0},\eta_{1})$, there must be some $K_{k}$
which is in at least

$\displaystyle\frac{\sum_{j=1}^{\ell}\prod_{i=1}^{k}d_{i,k+j}|U_{k+j}|\prod_{1\leq
i<i^{\prime}\leq
k}d_{i,i^{\prime}}-\delta^{\prime}\sum_{j=1}^{\ell}|U_{k+j}|}{\prod_{1\leq
i<i^{\prime}\leq k}d_{i,i^{\prime}}+\delta^{\prime}}$
$\displaystyle\geq\frac{\sum_{j=1}^{\ell}\left(\prod_{i=1}^{k}d_{i,k+j}-\delta^{-\binom{k}{2}}\delta^{\prime}\right)|U_{k+j}|}{1+\delta^{-\binom{k}{2}}\delta^{\prime}}$
$\displaystyle\geq\sum_{j=1}^{\ell}\left(\prod_{i=1}^{k}d_{i,k+j}-\delta\right)|U_{k+j}|$

copies of $K_{k+1}$, as required.

###  2.2 A coloured extremal result

We will need a coloured version of the celebrated Erdős–Stone theorem [11].
Recall that a blow-up of a graph $H$ is a graph where each vertex of $H$ is
replaced by a vertex set and the bipartite graph between two such vertex sets
is complete whenever the corresponding vertices are joined by an edge.

######  Lemma 2.6.

For any natural numbers $k$ and $t$ and any $\delta>0$, there exists a natural
number $n_{0}$ such that if the edges of the complete graph on $n\geq n_{0}$
vertices are coloured in red and blue, then, provided the blue density is at
least $1-\frac{1}{k-1}+\delta$, there is a blue blow-up of $K_{k}$ with $t$
vertices in each part, where each part is itself a monochromatic clique.

######  Proof 2.7.

Since the blue density is at least $1-\frac{1}{k-1}+\delta$, the Erdős–Stone
theorem implies that for $n\geq n_{0}$ there is a blue blow-up of $K_{k}$ with
at least $r(K_{t})$ vertices in each part. Applying Ramsey’s theorem within
each part then gives the required monochromatic cliques.

In practice, we will use a slight variant of this lemma, where the underlying
graph is not necessarily complete.

######  Lemma 2.8.

For any natural numbers $k$ and $t$ and any $\delta>0$, there exists a natural
number $n_{1}$ and $\epsilon>0$ such that if the edges of a graph on $n\geq
n_{1}$ vertices with $(1-\epsilon)\binom{n}{2}$ edges are coloured in red and
blue, then, provided the blue density is at least $1-\frac{1}{k-1}+\delta$,
there is a blue blow-up of $K_{k}$ with $t$ vertices in each part, where each
part is itself a monochromatic clique.

######  Proof 2.9.

Suppose first that the $\epsilon\binom{n}{2}$ missing edges are coloured blue,
so that the underlying graph is complete. Then, by Lemma 2.6, every subset of
the graph of order $n_{0}$ contains the required blow-up of $K_{k}$ with
monochromatic parts of order $t$. But then, for $n$ sufficiently large in
terms of $n_{0}$, there must be at least

$\binom{n}{n_{0}}/\binom{n-kt}{n_{0}-kt}=\binom{n}{kt}/\binom{n_{0}}{kt}\geq\frac{n^{kt}}{2n_{0}^{kt}}$

such blow-ups of $K_{k}$. However, at most $\epsilon n^{2}\cdot
n^{kt-2}=\epsilon n^{kt}$ such copies contain an edge from the missing set.
Therefore, for $\epsilon<1/2n_{0}^{kt}$, we must have the required blue blow-
up of $K_{k}$ with at least $t$ vertices in each part, where each part is a
monochromatic clique.

###  2.3 Some technical lemmas

The proof requires a small degree of optimisation, almost all of which is
contained in the following two lemmas.

######  Lemma 2.10.

For each $i=1,\dots,k$, let $x_{i}$ be a real number between $0$ and $t$. Then

$\frac{1}{k}\sum_{i=1}^{k}(t-x_{i})^{k}+\prod_{i=1}^{k}x_{i}\geq 2(t/2)^{k}.$

######  Proof 2.11.

As the result is easily checked for $k=2$, $3$ and $4$, we can assume without
loss of generality that $k\geq 5$. Moreover, since $(t-t/k)^{k}>2(t/2)^{k}k$
for all $k\geq 5$, we may assume that none of the $x_{i}$ are less than $t/k$.

We claim that the minimum value of $\sum_{i}(t-x_{i})^{k}$ subject to the
constraint $\prod_{i}x_{i}=z$, and assuming $x_{i}\geq t/k$ for all $i$,
occurs when all the $x_{i}$ are equal to $z^{1/k}$. To see this, make the
substitution $x_{i}=e^{y_{i}}$. The problem then becomes to minimise
$\sum_{i=1}^{k}(t-e^{y_{i}})^{k}$ subject to the constraint
$\sum_{i=1}^{k}y_{i}=\log z$. But the function $(t-e^{y})^{k}$ is easily seen
to be a convex function of $y$ for $t/k\leq e^{y}\leq t$. Therefore, the
minimum occurs when all of the $e^{y_{i}}$ and, hence, all of the $x_{i}$ are
equal.

Substituting $x_{i}=z^{1/k}$ for all $i$, it simply remains to minimise
$f(z)=(t-z^{1/k})^{k}+z$ on the interval $[0,t^{k}]$. But
$f^{\prime}(z)=-(t-z^{1/k})^{k-1}z^{-(k-1)/k}+1$, which equals $0$ precisely
when $z=(t/2)^{k}$. Hence, the minimum value of $f(z)$ is $2(t/2)^{k}$, as
required.

######  Lemma 2.12.

Suppose that $k\leq\ell$ and, for each $i=1,\dots,\ell$, let $x_{i}$ be a real
number between $0$ and $1$. Then

$\sum_{1\leq
i_{1}<\dots<i_{k}\leq\ell}\prod_{j=1}^{k}x_{i_{j}}\geq\binom{\sum_{i}x_{i}}{k}.$

######  Proof 2.13.

Suppose that $\sum_{i}x_{i}=c$ and we wish to minimise the left-hand side of
the required inequality under this constraint. We claim that the minimum
occurs when all but one of the $x_{i}$ equal $0$ or $1$, that is, $\lfloor
c\rfloor$ of the $x_{i}$ are $1$, one is $\\{c\\}=c-\lfloor c\rfloor$ and the
rest are $0$.

Suppose instead that $x_{1}$ and $x_{2}$, say, are both different from $0$ and
$1$. Then $x_{1}x_{2}=x_{1}(c-\sum_{i=3}^{k}x_{i}-x_{1})$, which has the form
$-x_{1}^{2}+Bx_{1}$, where $B$ is a function of $x_{3},\dots,x_{k}$ and hence
constant if these variables are held constant. But such a polynomial is
minimised when $x_{1}$ is either as large or as small as possible within its
allowed range. Hence, if $x_{1}$ and $x_{2}=c-\sum_{i=3}^{k}x_{i}-x_{1}$ are
both different from $0$ and $1$, we may vary $x_{1}$, keeping all $x_{i}$ with
$3\leq i\leq k$ fixed, to make $x_{1}x_{2}$, and thus $\prod_{i=1}^{k}x_{i}$,
smaller. This contradiction proves the claim, so

$\sum_{1\leq
i_{1}<\dots<i_{k}\leq\ell}\prod_{j=1}^{k}x_{i_{j}}\geq\binom{\lfloor
c\rfloor}{k}+\\{c\\}\binom{\lfloor c\rfloor}{k-1}\geq\binom{c}{k}.$

To establish the final inequality, suppose that $X$ is a random subset of a
$(\lfloor c\rfloor+1)$-element set, where the first element is chosen with
probability $\\{c\\}$ and all other elements with probability $1$. The
expected number of subsets of size $k$ in this random set is then

$\binom{\lfloor c\rfloor}{k}+\\{c\\}\binom{\lfloor c\rfloor}{k-1}.$

But it is also equal to

$(1-\\{c\\})\binom{\lfloor c\rfloor}{k}+\\{c\\}\binom{\lfloor c\rfloor+1}{k},$

which by convexity of $\binom{x}{k}$ is at least $\binom{c}{k}$.

##  3 Proof of Theorem 1

Suppose that we have a red/blue-colouring of the edges of the complete graph
on $N=(2^{k}+\epsilon)n$ vertices. Assume that $\eta$ is taken sufficiently
small and $m_{0}$ sufficiently large in terms of $k$ and $\epsilon$ and apply
Lemma 3 with $\eta$ and $m_{0}$ to the red subgraph to obtain an equitable
partition $\cup_{i=1}^{m}V_{i}$ of the vertex set $[N]$ with $m\geq m_{0}$ and
subsets $W_{i}\subseteq V_{i}$ such that $W_{i}$ is $\eta$-regular for all $i$
and, for all but $\eta m^{2}$ pairs $(i,j)$ with $1\leq i\neq j\leq m$,
$(V_{i},V_{j})$, $(W_{i},V_{j})$ and $(W_{i},W_{j})$ are $\eta$-regular with
$|d(W_{i},V_{j})-d(V_{i},V_{j})|\leq\eta$ and
$|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq\eta$, where $d(U,V)$ measures the red
density between vertex sets $U$ and $V$. Because the colours are
complementary, the same conclusion holds for the blue subgraph. For
convenience of notation, we will assume below that all $V_{i}$ have precisely
the same order $N/m$.

We now form a coloured reduced graph with vertex set $v_{1},\dots,v_{m}$. To
each $v_{i}$, we assign a colour $c_{i}$, either red or blue, depending on
which colour has the higher density inside $W_{i}$, breaking ties arbitrarily.
By the pigeonhole principle, at least $m/2$ of the $c_{i}$ are the same
colour, say red. We now colour the edges of the reduced graph, leaving an edge
uncoloured if $(W_{i},V_{j})$, $(V_{i},V_{j})$ and $(W_{i},W_{j})$ are not all
$\eta$-regular with $|d(W_{i},V_{j})-d(V_{i},V_{j})|\leq\eta$ and
$|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq\eta$. Otherwise, we fix a constant
$\delta$ (which will be taken sufficiently small in terms of $k$ and
$\epsilon$) and colour the edge $v_{i}v_{j}$ red if the red density between
$V_{i}$ and $V_{j}$ is at least $1-\delta$ and blue if the blue density is at
least $\delta$, again breaking ties arbitrarily. Note that there are at most
$\eta m^{2}$ ordered pairs $(i,j)$ whose corresponding edge is uncoloured.
Therefore, by deleting at most $\sqrt{\eta}m$ vertices, we may assume that
each vertex is adjacent to at most $\sqrt{\eta}m$ uncoloured edges. In what
follows, when referring to the reduced graph, we will assume that these
vertices have been removed. Note that at least
$s=\lceil(1/2-\sqrt{\eta})m\rceil$ of the remaining vertices have colour red.

Suppose now that there is a red vertex $v_{a}$ in the reduced graph which has
degree at least $\ell:=2^{-k}m$ in red, with neighbours
$v_{b_{1}},\dots,v_{b_{\ell}}$. Since the density of red edges in $W_{a}$ is
at least $1/2$, we may apply Lemma 2.4 with $U_{1}=\dots=U_{k}=W_{a}$ and
$U_{k+j}=V_{b_{j}}$ for $j=1,\dots,\ell$ to conclude that, for $\eta$
sufficiently small in terms of $\delta$, there is a red $K_{k}$ which is
contained in at least

$\sum_{j=1}^{\ell}(d(W_{a},V_{b_{j}})^{k}-\delta)|V_{b_{j}}|\geq((1-\delta-\eta)^{k}-\delta)\ell\frac{N}{m}=((1-\delta-\eta)^{k}-\delta)2^{-k}N$

red $K_{k+1}$. Provided $\eta$ and $\delta$ are sufficiently small in terms of
$k$ and $\epsilon$, this quantity is at least $n$, so we obtain the required
book $B_{n}^{(k)}$. We may therefore assume that we are in the other case,
where every red vertex in the reduced graph has blue degree at least
$m-\ell-2\sqrt{\eta}m\geq(1-2^{-k}-2\sqrt{\eta})m$.

The degree of each red vertex is therefore at least $(1-2^{-k}-2\sqrt{\eta})m$
in blue. If we restrict to a set $S$ consisting of $s$ of the red vertices,
the blue degree of each vertex inside this set is at least
$s-(2^{-k}+2\sqrt{\eta})m\geq(1-2^{-(k-1)}-16\sqrt{\eta})s$. Since
$1-2^{-(k-1)}-16\sqrt{\eta}>1-(k-1)^{-1}+\beta$ for some $\beta>0$ depending
only on $k$ and the number of uncoloured edges is at most $\eta m^{2}\leq
8\eta s^{2}$, Lemma 2.8 implies that for $m$ sufficiently large and $\eta$
sufficiently small in terms of $k$ and $t$, where $t$ is a constant to be
fixed below, the reduced graph contains a blue blow-up of $K_{k}$ with at
least $t$ vertices in each part, where each part is itself a monochromatic
clique.

We now claim that none of these monochromatic cliques can be blue. Indeed,
suppose otherwise and $C$ is a blue clique of order $t$. If any of the
vertices in $C$, say $v_{a}$, is such that
$\sum_{j}d(W_{a},V_{j})\geq\frac{1}{2}m$, where the sum is taken over all $j$
such that $(W_{a},V_{j})$ is $\eta$-regular, then we have

$\sum_{j}d(W_{a},V_{j})^{k}\geq
m\left(\frac{\sum_{j}d(W_{a},V_{j})}{m}\right)^{k}\geq 2^{-k}m.$

Again, since the density of red edges in $W_{a}$ is at least $1/2$, we may
apply Lemma 2.4 with $U_{1}=\dots=U_{k}=W_{a}$ and $U_{k+j}$ equal in turn to
each of the $V_{j}$ for which $(W_{a},V_{j})$ is $\eta$-regular to conclude
that, for $\eta$ sufficiently small in terms of $\delta$, there is a red
$K_{k}$ which is contained in at least

$\sum_{j}(d(W_{a},V_{j})^{k}-\delta)|V_{j}|\geq(2^{-k}-\delta)N$

red $K_{k+1}$. Provided $\eta$ and $\delta$ are sufficiently small in terms of
$k$ and $\epsilon$, this quantity is at least $n$, so we again obtain the
required book $B_{n}^{(k)}$.

Therefore, writing $\overline{d}(U,V)$ for the blue density between sets $U$
and $V$, we must have
$\sum_{j}\overline{d}(W_{a},V_{j})\geq(\frac{1}{2}-2\sqrt{\eta})m$ for all
$v_{a}\in C$, where the sum is now over all $j$ such that $v_{j}$ is in the
reduced graph. Writing $\overline{d}_{C}(V_{j})=\sum_{v_{a}\in
C}\overline{d}(W_{a},V_{j})$, we see, by applying Lemma 2.12 and summing over
all $j$ such that $v_{j}$ is in the reduced graph, that

$\sum_{j}\sum_{(a_{1},\dots,a_{k})\in\binom{C}{k}}\prod_{i=1}^{k}\overline{d}(W_{a_{i}},V_{j})\geq\sum_{j}\binom{\overline{d}_{C}(V_{j})}{k}\geq
m\binom{\sum_{j}\overline{d}_{C}(V_{j})/m}{k}.$

Therefore, since
$\sum_{j}\overline{d}_{C}(V_{j})\geq\frac{1}{2}(1-4\sqrt{\eta})m|C|$, we have,
for $t=|C|\geq(1+\xi)k/(\xi-4\sqrt{\eta})$, that

$\sum_{j}\sum_{(a_{1},\dots,a_{k})\in\binom{C}{k}}\prod_{i=1}^{k}\overline{d}(W_{a_{i}},V_{j})\geq\binom{\frac{1}{2}(1-4\sqrt{\eta})|C|}{k}\geq\left(\frac{1}{2}(1-\xi)\right)^{k}\binom{|C|}{k}\geq
2^{-k}(1-k\xi)\binom{|C|}{k},$

where we used that
$\frac{1}{2}(1-4\sqrt{\eta})|C|-i\geq\frac{1}{2}(1-\xi)(|C|-i)$ for $0\leq
i\leq k$. Hence, there exists a choice of $a_{1},\dots,a_{k}$ such that

$\sum_{j}\prod_{i=1}^{k}\overline{d}(W_{a_{i}},V_{j})\geq 2^{-k}(1-k\xi)m.$

Since, in the reduced graph, each $v_{a_{i}}$ has at most $\sqrt{\eta}m$
neighbours $v_{j}$ such that $(W_{a_{i}},V_{j})$ is not $\eta$-regular, if we
now sum only over those $j$ such that $(W_{a_{i}},V_{j})$ is $\eta$-regular
for all $i$, we have that

$\sum_{j}\prod_{i=1}^{k}\overline{d}(W_{a_{i}},V_{j})\geq
2^{-k}(1-k\xi)m-k\sqrt{\eta}m.$

We now apply Lemma 2.4 with $U_{i}=W_{a_{i}}$ for each $1\leq i\leq k$ and
$U_{k+j}$ equal in turn to each $V_{j}$ with $(W_{a_{i}},V_{j})$
$\eta$-regular for all $1\leq i\leq k$ to conclude that, for $\eta$
sufficiently small in terms of $\delta$, there is a blue $K_{k}$ which is
contained in at least

$\sum_{j}(\prod_{i=1}^{k}\overline{d}(W_{a_{i}},V_{j})-\delta)|V_{j}|\geq(2^{-k}(1-k\xi)-k\sqrt{\eta}-\delta)N$

blue $K_{k+1}$. Provided $\eta$, $\delta$ and $\xi$ are sufficiently small
(and $t$ is sufficiently large) in terms of $k$ and $\epsilon$, this quantity
is again at least $n$.

This completes the proof of the claim. We may therefore assume that all of the
cliques are red and focus on the subgraph of the reduced graph consisting of
the $k$ red cliques $C_{1},\dots,C_{k}$, each of order $t$, where every edge
between $C_{i}$ and $C_{j}$ with $i\neq j$ is blue.

Now, for each vertex $v$ in the reduced graph, let $e_{i}(v)$ be the weighted
blue degree of $v$ in each $C_{i}$. That is, $e_{i}(v)=\sum_{w\in
C_{i}}\overline{d}(v,w)$. By Lemma 2.10,
$\frac{1}{k}\sum_{v}\sum_{i}(t-e_{i}(v))^{k}+\sum_{v}\prod_{i}e_{i}(v)\geq
2(t/2)^{k}m^{\prime}$, which implies that either
$\sum_{v}\sum_{i}(t-e_{i}(v))^{k}\geq(t/2)^{k}km^{\prime}$ or
$\sum_{v}\prod_{i}e_{i}(v)\geq(t/2)^{k}m^{\prime}$, where
$m^{\prime}=(1-\sqrt{\eta})m$. In the second case, we see that there must
exist a choice of vertices $v_{c_{1}},\dots,v_{c_{k}}$ with $v_{c_{i}}\in
C_{i}$ such that

$\sum_{j}\prod_{i=1}^{k}\overline{d}(W_{c_{i}},V_{j})\geq\frac{\sum_{j}\sum_{c_{1},\dots,c_{k}}\prod_{i}\overline{d}(W_{c_{i}},V_{j})}{t^{k}}=\frac{\sum_{j}\prod_{i}(\sum_{c_{i}\in
C_{i}}\overline{d}(W_{c_{i}},V_{j}))}{t^{k}}=\frac{\sum_{v}\prod_{i}e_{i}(v)}{t^{k}}\geq
2^{-k}m^{\prime}.$

Since there are at most $k\sqrt{\eta}m$ vertices $v_{j}$ such that
$(W_{c_{i}},V_{j})$ is not $\eta$-regular for all $1\leq i\leq k$, we may
apply Lemma 2.4 with $U_{i}=W_{c_{i}}$ for $i=1,\dots,k$ and $U_{k+j}$ equal
in turn to each $V_{j}$ such that $(W_{c_{i}},V_{j})$ is $\eta$-regular for
each $1\leq i\leq k$ to conclude that, for $\eta$ sufficiently small in terms
of $\delta$, there is a blue $K_{k}$ which is contained in at least

$\sum_{j}(\prod_{i=1}^{k}\overline{d}(W_{c_{i}},V_{j})-\delta)|V_{j}|\geq(2^{-k}(1-\sqrt{\eta})-k\sqrt{\eta}-\delta)N$

blue $K_{k+1}$, again giving the required book for $\eta$ and $\delta$
sufficiently small in terms of $k$ and $\epsilon$.

In the first case, there exists a $C_{r}$ such that
$\sum_{v}(t-e_{r}(v))^{k}\geq(t/2)^{k}m^{\prime}$. There must therefore exist
(not necessarily distinct) vertices $d_{1},\dots,d_{k}\in C_{r}$ such that

$\sum_{j}\prod_{i=1}^{k}d(W_{d_{i}},V_{j})\geq\frac{\sum_{j}\sum_{d_{1},\dots,d_{k}}\prod_{i}d(W_{d_{i}},V_{j})}{t^{k}}=\frac{\sum_{j}(\sum_{d\in
C_{r}}d(W_{d},V_{j}))^{k}}{t^{k}}=\frac{\sum_{v}(t-e_{r}(v))^{k}}{t^{k}}\geq
2^{-k}m^{\prime}.$

If we again remove the at most $k\sqrt{\eta}m$ vertices $v_{j}$ such that
$(W_{d_{i}},V_{j})$ is not $\eta$-regular for all $1\leq i\leq k$, we may
apply Lemma 2.4 with $U_{i}=W_{d_{i}}$ for $i=1,\dots,k$ and $U_{k+j}$ equal
in turn to each $V_{j}$ such that $(W_{d_{i}},V_{j})$ is $\eta$-regular for
each $1\leq i\leq k$ to conclude that, for $\eta$ sufficiently small in terms
of $\delta$, there is a red $K_{k}$ which is contained in at least

$\sum_{j}(\prod_{i=1}^{k}d(W_{d_{i}},V_{j})-\delta)|V_{j}|\geq(2^{-k}(1-\sqrt{\eta})-k\sqrt{\eta}-\delta)N$

red $K_{k+1}$, giving the required book in this final case provided $\eta$ and
$\delta$ are again small enough in terms of $k$ and $\epsilon$. This completes
the proof.

##  4 Concluding remarks

One obvious question is whether a multicolour analogue of Theorem 1 might
hold. This is certainly not the case when the number of colours is large. To
see this, we use the fact that there exist $q$-colourings of the complete
graph on vertex set $\\{1,2,\dots,2^{qk/4}\\}$ with no monochromatic $K_{k}$
(see, for example, [6, Section 2.1]). Fix such a colouring $\chi$. We consider
the $(q+1)$-coloured complete graph whose vertex set is split into
$t=2^{qk/4}$ vertex sets $V_{1},\dots,V_{t}$, each of order $n$, where every
edge between $V_{i}$ and $V_{j}$ receives the colour $\chi(i,j)$ and edges
internal to any $V_{i}$ all receive a $(q+1)$st colour. This colouring
contains no monochromatic $B_{n}^{(k)}$, so the $(q+1)$-colour Ramsey number
$r(B_{n}^{(k)};q+1)\geq 2^{qk/4}n$, far greater than the $(q+1)^{k}n$ bound
one might hope for. More generally, we have
$r(B_{n}^{(k)};q+1)\geq(r(k;q)-1)n$, so, if true, the problem of showing that
$r(B_{n}^{(k)};3)\leq 3^{k}n+o_{k}(n)$ is at least as hard as showing that
$r(k)\leq 3^{k+o(k)}$.

It is also tempting to generalise Theorem 1 to hypergraphs. To this end, we
define $B_{n}^{(k,s)}$ to be the $s$-uniform hypergraph consisting of $n$
copies of $K_{k+1}^{(s)}$, all sharing a common $K_{k}^{(s)}$. The natural
conjecture would then be that

$r(B_{n}^{(k,s)})=2^{\binom{k}{s-1}}n+o_{k,s}(n).$

However, this is false for $s\geq 4$. To see this, suppose that $s\geq 3$, $k$
is a multiple of $s$ and there is a $2$-colouring $\chi$ of the $s$-uniform
hypergraph on vertex set $\\{1,2,\dots,r-1\\}$ with no monochromatic
$K_{k/s}^{(s)}$. Consider the complete $s$-uniform hypergraph whose vertex set
is split into $r-1$ vertex sets $V_{1},\dots,V_{r-1}$, each of order $n$. To
colour this hypergraph, suppose that $\\{v_{1},\dots,v_{s}\\}$ is an edge and
$v_{j}\in V_{i_{j}}$ for all $1\leq j\leq s$. If the $i_{j}$ are all distinct,
we colour the edge by $\chi(i_{1},\dots,i_{s})$ and if the $i_{j}$ are all the
same, we colour the edge red. Otherwise, we colour the edge blue. Since the
colouring $\chi$ contains no monochromatic $K_{k/s}^{(s)}$, at least $s$
elements of the spine of any monochromatic $B_{n}^{(k,s)}$ are contained in
the same set $V_{i}$. But this implies that the book must be red and,
therefore, entirely contained within $V_{i}$, which is not large enough to
contain it, a contradiction. Since we may take $r$ to be $r(K_{k/s}^{(s)})$,
this implies that

$r(B_{n}^{(k,s)})\geq(r(K_{k/s}^{(s)})-1)n.$

The value of $r(K_{k}^{(s)})$ is known to be at least an $(s-2)$-fold
exponential in $k$ (see, for example, [6]), so this disproves the conjecture
for $s\geq 4$. The $s=3$ case remains unresolved, though a negative answer
would again follow from improved lower bounds for $r(K_{k}^{(3)})$.

As a final remark, we note that there is a strong analogy between Theorem 1
and Green’s popular progression theorem [17] (see also [18]). This says that
for every $\epsilon>0$ there exists $n_{0}$ such that if $n\geq n_{0}$ and $A$
is a subset of $\\{1,2,\dots,n\\}$ of size $\alpha n$, then there is $d\neq 0$
such that $A$ contains at least $(\alpha^{3}-\epsilon)n$ arithmetic
progressions of length $3$ with common difference $d$. That is, there are
asymptotically at least as many arithmetic progressions of length $3$ in $A$
with common difference $d$ as there would be in a random subset of
$\\{1,2,\dots,n\\}$ of the same size. A surprising recent result of Fox, Pham
and Zhao [14, 15] says that $n_{0}$ grows as a tower-type function of
$\epsilon$, showing that an application of the (arithmetic) regularity lemma
in Green’s proof is in some sense necessary. It would be very interesting if a
similar phenomenon held for our result, though this seems unlikely to the
author.

## Acknowledgments

This paper was partially written while I was visiting the California Institute
of Technology as a Moore Distinguished Scholar and I am extremely grateful for
their kind support. I am also much indebted to Jacob Fox, Lisa Sauermann and
Yuval Wigderson for pointing out a subtle error in the first version of this
paper. Finally, I would like to thank the anonymous reviewers for several
helpful remarks which improved the presentation.

## References

  * [1] N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451–476.
  * [2] S. A. Burr and V. Rosta, On the Ramsey multiplicity of graphs – problems and recent results, J. Graph Theory 4 (1980), 347–361.
  * [3] D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. 170 (2009), 941–960.
  * [4] D. Conlon, On the Ramsey multiplicity of complete graphs, Combinatorica 32 (2012), 171–186.
  * [5] D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), 1191–1256.
  * [6] D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, in _Surveys in Combinatorics 2015_ , 49–118, London Math. Soc. Lecture Note Ser., 424, Cambridge Univ. Press, Cambridge, 2015.
  * [7] J. Cummings, D. Král’, F. Pfender, K. Sperfeld, A. Treglown and M. Young, Monochromatic triangles in three-coloured graphs, J. Combin. Theory Ser. B 103 (2013), 489–503.
  * [8] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294.
  * [9] P. Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 7 (1962), 459–464.
  * [10] P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–161.
  * [11] P. Erdős and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
  * [12] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463–470.
  * [13] J. Fox, There exist graphs with super-exponential Ramsey multiplicity constant, J. Graph Theory 57 (2008), 89–98.
  * [14] J. Fox and H. T. Pham, Popular progression differences in vector spaces, preprint available at arXiv:1708.08482 [math.CO].
  * [15] J. Fox, H. T. Pham and Y. Zhao, Tower-type bounds for Roth’s theorem with popular differences, preprint.
  * [16] A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783.
  * [17] B. Green, A Szemerédi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), 340–376.
  * [18] B. Green and T. Tao, An arithmetic regularity lemma, an associated counting lemma, and applications, in An Irregular Mind (Szemerédi is 70), 261–334, Springer, 2010.
  * [19] H. Hatami, J. Hladký, D. Král’, S. Norine and A. Razborov, Non-three-colorable common graphs exist, Combin. Probab. Comput. 21 (2012), 734–742.
  * [20] C. Jagger, P. Šťovíček and A. Thomason, Multiplicities of subgraphs, Combinatorica 16 (1996), 123–141.
  * [21] V. Nikiforov, C. C. Rousseau and R. H. Schelp, Book Ramsey numbers and quasi-randomness, Combin. Probab. Comput. 14 (2005), 851–860.
  * [22] V. Rödl and M. Schacht, Regularity lemmas for graphs, in Fete of combinatorics and computer science, 287–325, Bolyai Soc. Math. Stud., 20, János Bolyai Math. Soc., Budapest, 2010.
  * [23] C. C. Rousseau and J. Sheehan, On Ramsey numbers of books, J. Graph Theory 2 (1978), 77–87.
  * [24] J. H. Spencer, Ramsey’s theorem — a new lower bound, J. Combin. Theory Ser. A 18 (1975), 108–115.
  * [25] A. Thomason, On finite Ramsey numbers, Eur. J. Combin. 3 (1982), 263–273.
  * [26] A. Thomason, A disproof of a conjecture of Erdős in Ramsey theory, J. London Math. Soc. 39 (1989), 246–255.

[dcon] David Conlon
Mathematical Institute
University of Oxford
david.conlonmathsoxacuk
https://people.maths.ox.ac.uk/conlond


* Dowdall  _et al._ [2019] R. J. Dowdall, C. T. H. Davies, R. R. Horgan, G. P. Lepage, C. J. Monahan, J. Shigemitsu, and M. Wingate, Neutral B-meson mixing from full lattice QCD at the physical point, Phys. Rev. D 100, 094508 (2019), arXiv:1907.01025 [hep-lat] .
  * Blake  _et al._ [2017] T. Blake, G. Lanfranchi, and D. M. Straub, Rare $B$ Decays as Tests of the Standard Model, Prog. Part. Nucl. Phys. 92, 50 (2017), arXiv:1606.00916 [hep-ph] .
  * Hatton  _et al._ [2020b] D. Hatton, C. T. H. Davies, B. Galloway, J. Koponen, G. P. Lepage, and A. T. Lytle (HPQCD), Charmonium properties from lattice $QCD$+QED : Hyperfine splitting, $J/\psi$ leptonic width, charm quark mass, and $a^{c}_{\mu}$, Phys. Rev. D 102, 054511 (2020b), arXiv:2005.01845 [hep-lat] .
  * Pivovarov [2002] A. A. Pivovarov, Running electromagnetic coupling constant: Low-energy normalization and the value at M(Z), Phys. Atom. Nucl. 65, 1319 (2002), arXiv:hep-ph/0011135 .
  * Chetyrkin and Steinhauser [1999] K. G. Chetyrkin and M. Steinhauser, Short distance mass of a heavy quark at order $\alpha_{s}^{3}$, Phys. Rev. Lett. 83, 4001 (1999), arXiv:hep-ph/9907509 .
  * Melnikov and Ritbergen [2000] K. Melnikov and T. v. Ritbergen, The Three loop relation between the MS-bar and the pole quark masses, Phys. Lett. B 482, 99 (2000), arXiv:hep-ph/9912391 .
  * Beneke and Braun [1994] M. Beneke and V. M. Braun, Heavy quark effective theory beyond perturbation theory: Renormalons, the pole mass and the residual mass term, Nucl. Phys. B 426, 301 (1994), arXiv:hep-ph/9402364 .
  * CKM [2018] CKMfitter, http://ckmfitter.in2p3.fr (2018).
  * CKM [2021] CKMfitter, http://ckmfitter.in2p3.fr (2021).
  * Beylich  _et al._ [2011] M. Beylich, G. Buchalla, and T. Feldmann, Theory of $B\to K^{(*)}\ell^{+}\ell^{-}$ decays at high $q^{2}$: OPE and quark-hadron duality, Eur. Phys. J. C 71, 1635 (2011), arXiv:1101.5118 [hep-ph] .
  * Davidson  _et al._ [2016] N. Davidson, T. Przedzinski, and Z. Was, PHOTOS interface in C++: Technical and Physics Documentation, Comput. Phys. Commun. 199, 86 (2016), arXiv:1011.0937 [hep-ph] .
  * Isidori  _et al._ [2020] G. Isidori, S. Nabeebaccus, and R. Zwicky, QED corrections in $\overline{B}\to\overline{K}{\mathrm{\ell}}^{+}{\mathrm{\ell}}^{-}$ at the double-differential level, JHEP 12, 104, arXiv:2009.00929 [hep-ph] .
  * Isidori  _et al._ [2022] G. Isidori, D. Lancierini, S. Nabeebaccus, and R. Zwicky, QED in $\bar{B}\to\bar{K}\ell^{+}\ell^{-}$ LFU ratios: Theory versus Experiment, a Monte Carlo Study, (2022), arXiv:2205.08635 [hep-ph] .
  * Bordone  _et al._ [2016] M. Bordone, G. Isidori, and A. Pattori, On the Standard Model predictions for $R_{K}$ and $R_{K^{*}}$, Eur. Phys. J. C 76, 440 (2016), arXiv:1605.07633 [hep-ph] .
  * Mishra and Mahajan [2021] D. Mishra and N. Mahajan, Impact of soft photons on $B\rightarrow K\ell^{+}\ell^{-}$, Phys. Rev. D 103, 056022 (2021), arXiv:2010.10853 [hep-ph] .
  * Gubernari  _et al._ [2022] N. Gubernari, M. Reboud, D. van Dyk, and J. Virto, Improved Theory Predictions and Global Analysis of Exclusive $\boldsymbol{b\to s\mu^{+}\mu^{-}}$ Processes, (2022), arXiv:2206.03797 [hep-ph] .
  * Ali  _et al._ [2000] A. Ali, P. Ball, L. T. Handoko, and G. Hiller, A Comparative study of the decays $B\to$ ($K$, $K^{*)}\ell^{+}\ell^{-}$ in standard model and supersymmetric theories, Phys. Rev. D 61, 074024 (2000), arXiv:hep-ph/9910221 .
  * Bečirević  _et al._ [2016] D. Bečirević, O. Sumensari, and R. Zukanovich Funchal, Lepton flavor violation in exclusive $b\rightarrow s$ decays, Eur. Phys. J. C 76, 134 (2016), arXiv:1602.00881 [hep-ph] .
  * Angelescu  _et al._ [2020] A. Angelescu, D. A. Faroughy, and O. Sumensari, Lepton Flavor Violation and Dilepton Tails at the LHC, Eur. Phys. J. C 80, 641 (2020), arXiv:2002.05684 [hep-ph] .
  * Lytle  _et al._ [2018] A. T. Lytle, C. T. H. Davies, D. Hatton, G. P. Lepage, and C. Sturm (HPQCD), Determination of quark masses from $\mathbf{n_{f}=4}$ lattice QCD and the RI-SMOM intermediate scheme, Phys. Rev. D 98, 014513 (2018), arXiv:1805.06225 [hep-lat] .
  * Hiller  _et al._ [2016] G. Hiller, D. Loose, and K. Schönwald, Leptoquark Flavor Patterns & B Decay Anomalies, JHEP 12, 027, arXiv:1609.08895 [hep-ph] .
  * Descotes-Genon  _et al._ [2020] S. Descotes-Genon, S. Fajfer, J. F. Kamenik, and M. Novoa-Brunet, Implications of $b\to s\mu\mu$ anomalies for future measurements of $B\to K^{(*)}\nu\bar{\nu}$ and $K\to\pi\nu\bar{\nu}$, Phys. Lett. B 809, 135769 (2020), arXiv:2005.03734 [hep-ph] .
  * Altmannshofer  _et al._ [2020] W. Altmannshofer, P. S. B. Dev, A. Soni, and Y. Sui, Addressing R${}_{D^{(*)}}$, R${}_{K^{(*)}}$, muon $g-2$ and ANITA anomalies in a minimal $R$-parity violating supersymmetric framework, Phys. Rev. D 102, 015031 (2020), arXiv:2002.12910 [hep-ph] .
  * Bhupal Dev  _et al._ [2022] P. S. Bhupal Dev, A. Soni, and F. Xu, Hints of natural supersymmetry in flavor anomalies?, Phys. Rev. D 106, 015014 (2022), arXiv:2106.15647 [hep-ph] .
  * Altmannshofer  _et al._ [2009] W. Altmannshofer, A. J. Buras, D. M. Straub, and M. Wick, New strategies for New Physics search in $B\to K^{*}\nu\bar{\nu}$, $B\to K\nu\bar{\nu}$ and $B\to X_{s}\nu\bar{\nu}$ decays, JHEP 04, 022, arXiv:0902.0160 [hep-ph] .
  * Brod  _et al._ [2011] J. Brod, M. Gorbahn, and E. Stamou, Two-Loop Electroweak Corrections for the $K\to\pi\nu\bar{\nu}$ Decays, Phys. Rev. D 83, 034030 (2011), arXiv:1009.0947 [hep-ph] .
  * Kamenik and Smith [2009] J. F. Kamenik and C. Smith, Tree-level contributions to the rare decays B+ —$>$ pi+ nu anti-nu, B+ —$>$ K+ nu anti-nu, and B+ —$>$ K*+ nu anti-nu in the Standard Model, Phys. Lett. B 680, 471 (2009), arXiv:0908.1174 [hep-ph] .
  * Bailey  _et al._ [2015] J. A. Bailey _et al._ (Fermilab Lattice, MILC), $|V_{ub}|$ from $B\to\pi\ell\nu$ decays and (2+1)-flavor lattice QCD, Phys. Rev. D92, 014024 (2015), arXiv:1503.07839 [hep-lat] .
  * Flynn  _et al._ [2015] J. M. Flynn, T. Izubuchi, T. Kawanai, C. Lehner, A. Soni, R. S. Van de Water, and O. Witzel, $B\to\pi\ell\nu$ and $B_{s}\to K\ell\nu$ form factors and $|V_{ub}|$ from 2+1-flavor lattice QCD with domain-wall light quarks and relativistic heavy quarks, Phys. Rev. D 91, 074510 (2015), arXiv:1501.05373 [hep-lat] .
  * Rosner  _et al._ [2015] J. L. Rosner, S. Stone, and R. S. Van de Water, Leptonic Decays of Charged Pseudoscalar Mesons - 2015, (2015), arXiv:1509.02220 [hep-ph] .
  * Moulson [2014] M. Moulson, Experimental determination of $V_{us}$ from kaon decays, in  _8th International Workshop on the CKM Unitarity Triangle_ (2014) arXiv:1411.5252 [hep-ex] .
  * Buras and Venturini [2021] A. J. Buras and E. Venturini, Searching for New Physics in Rare $K$ and $B$ Decays without $|V_{cb}|$ and $|V_{ub}|$ Uncertainties, (2021), arXiv:2109.11032 [hep-ph] .
  * Buras and Venturini [2022] A. J. Buras and E. Venturini, The Exclusive Vision of Rare $K$ and $B$ Decays and of the Quark Mixing in the Standard Model, (2022), arXiv:2203.11960 [hep-ph] .
  * Altmannshofer and Stangl [2021] W. Altmannshofer and P. Stangl, New physics in rare B decays after Moriond 2021, Eur. Phys. J. C 81, 952 (2021), arXiv:2103.13370 [hep-ph] .
  * LHC [2022] Test of lepton universality in $b\rightarrow s\ell^{+}\ell^{-}$ decays, (2022), arXiv:2212.09152 [hep-ex] .
  * Chakraborty  _et al._ [2015] B. Chakraborty, C. T. H. Davies, B. Galloway, P. Knecht, J. Koponen, G. C. Donald, R. J. Dowdall, G. P. Lepage, and C. McNeile, High-precision quark masses and QCD coupling from $n_{f}=4$ lattice QCD, Phys. Rev. D91, 054508 (2015), arXiv:1408.4169 [hep-lat] .
  * Beneke  _et al._ [2001] M. Beneke, T. Feldmann, and D. Seidel, Systematic approach to exclusive $B\to Vl^{+}l^{-}$, $V\gamma$ decays, Nucl. Phys. B 612, 25 (2001), arXiv:hep-ph/0106067 .
  * Greub  _et al._ [2008] C. Greub, V. Pilipp, and C. Schupbach, Analytic calculation of two-loop QCD corrections to $b\to sl^{+}l^{-}$ in the high $q^{2}$ region, JHEP 12, 040, arXiv:0810.4077 [hep-ph] .
  * Grinstein and Pirjol [2004] B. Grinstein and D. Pirjol, Exclusive rare $B\to K^{*}\ell^{+}\ell^{-}$ decays at low recoil: Controlling the long-distance effects, Phys. Rev. D 70, 114005 (2004), arXiv:hep-ph/0404250 .
  * Bobeth  _et al._ [2010] C. Bobeth, G. Hiller, and D. van Dyk, The Benefits of $\bar{B}->\bar{K}^{*}l^{+}l^{-}$ Decays at Low Recoil, JHEP 07, 098, arXiv:1006.5013 [hep-ph] .
  * Bobeth  _et al._ [2011] C. Bobeth, G. Hiller, and D. van Dyk, More Benefits of Semileptonic Rare B Decays at Low Recoil: CP Violation, JHEP 07, 067, arXiv:1105.0376 [hep-ph] .
  * Beneke and Feldmann [2001] M. Beneke and T. Feldmann, Symmetry breaking corrections to heavy to light B meson form-factors at large recoil, Nucl. Phys. B 592, 3 (2001), arXiv:hep-ph/0008255 .
  * Asatrian  _et al._ [2001] H. H. Asatrian, H. M. Asatrian, C. Greub, and M. Walker, Two loop virtual corrections to $B\to X_{s}l^{+}l^{-}$ in the standard model, Phys. Lett. B 507, 162 (2001), arXiv:hep-ph/0103087 .
  * Asatryan  _et al._ [2002] H. H. Asatryan, H. M. Asatrian, C. Greub, and M. Walker, Calculation of two loop virtual corrections to $b\to sl^{+}l^{-}$ in the standard model, Phys. Rev. D 65, 074004 (2002), arXiv:hep-ph/0109140 .
  * Asatrian  _et al._ [2004] H. M. Asatrian, K. Bieri, C. Greub, and M. Walker, Virtual corrections and bremsstrahlung corrections to b —$>$ d l+ l- in the standard model, Phys. Rev. D 69, 074007 (2004), arXiv:hep-ph/0312063 .
  * Seidel [2004] D. Seidel, Analytic two loop virtual corrections to b —$>$ d l+ l-, Phys. Rev. D 70, 094038 (2004), arXiv:hep-ph/0403185 .
  * Beneke  _et al._ [2005] M. Beneke, T. Feldmann, and D. Seidel, Exclusive radiative and electroweak $b\to d$ and $b\to s$ penguin decays at NLO, Eur. Phys. J. C 41, 173 (2005), arXiv:hep-ph/0412400 .
  * Braun  _et al._ [2006] V. M. Braun _et al._ , Moments of pseudoscalar meson distribution amplitudes from the lattice, Phys. Rev. D 74, 074501 (2006), arXiv:hep-lat/0606012 .
  * Lepage [2021] P. Lepage, gplepage/vegas: vegas version 4.0.3 (2021).