# Perfect quantum state transfer on the Johnson scheme

Bahman Ahmadi<EMAIL_ADDRESS>M. H. Shirdareh Haghighi
<EMAIL_ADDRESS>Ahmad Mokhtar<EMAIL_ADDRESS>Department of
Mathematics, Shiraz University, Shiraz, Iran

###### Abstract

For any graph $X$ with the adjacency matrix $A$, the transition matrix of the
continuous-time quantum walk at time $t$ is given by the matrix-valued
function $\mathcal{H}_{X}(t)=\mathrm{e}^{itA}$. We say that there is perfect
state transfer in $X$ from the vertex $u$ to the vertex $v$ at time $\tau$ if
$|\mathcal{H}_{X}(\tau)_{u,v}|=1$. It is an important problem to determine
whether perfect state transfers can happen on a given family of graphs. In
this paper we characterize all the graphs in the Johnson scheme which have
this property. Indeed, we show that the Kneser graph $K(2k,k)$ is the only
class in the scheme which admits perfect state transfers. We also show that,
under some conditions, some of the unions of the graphs in the Johnson scheme
admit perfect state transfer.

###### keywords:

perfect state transfer, association scheme, Johnson scheme

##  1 Introduction

Let $X$ be a simple graph. The transition matrix of the continuous-time
quantum walk at time $t$ on the graph $X$ is given by the matrix-valued
function $\mathcal{H}_{X}(t)=\mathrm{e}^{itA}$, where $A=A(X)$ is the
adjacency matrix of $X$. We say that there is perfect state transfer (or PST)
in $X$ from the vertex $u$ to the vertex $v$ at time $\tau$ if
$|\mathcal{H}_{X}(\tau)_{u,v}|=1$ or, equivalently, if
$\mathcal{H}_{X}(\tau)e_{u}=\lambda e_{v}$, for some $\lambda\in\mathbb{C}$,
where $e_{u}$ is the characteristic vector of the vertex $u$ in $V(X)$. (Note
that since $\mathcal{H}_{X}(\tau)$ is unitary, we must have $|\lambda|=1$.) If
the graph $X$ is clear from the context, we may drop the subscript $X$. We,
further, say that $X$ is periodic at a vertex $u$ if there is a positive time
$\tau$ such that $|\mathcal{H}(\tau)_{u,u}|=1$, and we say $X$ itself is
periodic if there is a positive time $\tau$ such that
$|\mathcal{H}(\tau)_{u,u}|=1$ for all vertices $u$. Note that if there is PST
from $u$ to $v$, then there is also PST from $v$ to $u$ (so we may just say
there is PST “between” $u$ and $v$), and that $X$ will be periodic at $u$ and
at $v$ (see [6]).

It is an important question to ask on which graphs PST can happen. As an easy
example we can show that PST occurs between the vertices of the the path
$P_{2}$ (see Corollary 2.5). We can, also, show directly (see [7]) that PST
happens between the end-points of the path $P_{3}$, as well; but this is not
the case for any other path. In other words, it has been shown in [2] that if
$n>3$, then there is no PST on the path $P_{n}$. On the other hand, in the
works such as [1, 2, 6, 9], the existence of PST in different graphs has been
shown. See [7] for a survey on the subject.

In [3] necessary and sufficient conditions have been proposed for graphs in
association schemes to have PST and using this result the authors have
examined some of the graphs in some association schemes. Since one of the most
important association schemes is the Johnson scheme $J(n,k)$, it is quite
natural to ask whether any of the classes of this scheme admits PST.

In this paper, we prove that except for the Kneser graph $K(2k,k)$, which is
one of the classes of the Johnson scheme for the case $n=2k$, no other class
has the capability to have PST. We, further, deduce that the union of all the
graphs in the scheme $J(2k,k)$, except the Kneser graph $K(2k,k)$, admits PST
as long as the number of vertices of the scheme is divisible by $4$.

In the next section, we will provide some brief background on the topic. Then
we will prove the main result in Section 3. In Section 4 we will study the
case of sums of the classes of the scheme $J(2k,k)$ and, finally, conclude the
paper with some further discussions in Section 5.

##  2 Background

In this section, we provide the reader with some necessary tools and facts on
the topic, which will be used in Section 3. For the notation and basic facts
of algebraic graph theory and association schemes the reader may refer to [8]
and [4]. All the association schemes are assumed to be symmetric. Let
$\mathcal{A}=\\{I=A_{0},A_{1},\ldots,A_{d}\\}$ (where $A_{i}$ are $v\times v$
matrices) be an association scheme with $d$ classes whose minimal idempotents
(i.e. projections to the eigenspaces) are
$\mathcal{E}=\\{E_{0},E_{1},\ldots,E_{d}\\}$. Since $\mathcal{E}$ is a basis
for the Bose-Mesner algebra of $\mathcal{A}$, there are coefficients
$p_{i}(j)$ such that

$A_{i}=\sum_{j=0}^{d}p_{i}(j)E_{j},\quad\text{for }\,i=0,\ldots,d.$

For any $i=0,\ldots,d$, the (real) numbers $p_{i}(j)$, $j=0,\ldots,d$, are the
eigenvalues of $A_{i}$ and the columns of $E_{j}$ are eigenvectors of $A_{i}$.
We can think of $A_{i}$ as the adjacency matrix of a regular graph $X_{i}$ on
$v$ vertices of valency $p_{i}(0)$. We will denote the valency of $X_{i}$ by
$v_{i}$. On the other hand, the idempotents $E_{i}$ can also be written as a
linear combination of the $A_{j}$’s; that is, there are coefficients
$q_{i}(j)$ such that

$E_{i}=\frac{1}{v}\sum_{j=0}^{d}q_{i}(j)A_{j},\quad\text{for }\,i=0,\ldots,d.$
(1)

The numbers $q_{i}(j)$ are called the dual eigenvalues of the scheme. We note
that $q_{j}(0)=\mathrm{tr}(E_{j})$ which is equal to the dimension of the
$j$-th eigenspace of the matrices of the scheme which will be denoted by
$m_{j}$. The following fundamental result will be used in Section 3 (see [4]).

######  Proposition 2.1.

Using the notation above, for any $i,j=0,\ldots,d$, we have
$q_{j}(i)/m_{j}=p_{i}(j)/v_{i}$.∎

Given an association scheme, the following result gives necessary conditions
for a graph belonging to the scheme to have PST [3].

######  Theorem 2.2.

Let $X$ be a graph that belongs to an association scheme with $d$ classes and
with adjacency matrix $A=A(X)$. If $X$ admits perfect state transfer at time
$\tau$, then there is a permutation matrix $T$ with no fixed points and of
order two such that $\mathcal{H}(\tau)=\lambda T$ for some
$\lambda\in\mathbb{C}$. Moreover, $T$ is a class of the scheme. ∎

The following result from [7], as well, provides a necessary condition for the
existence of PST on a vertex-transitive graph.

######  Theorem 2.3.

Let $X$ be a connected vertex-transitive graph. If $X$ admits perfect state
transfer at time $\tau$, then there is a permutation matrix $T$ with no fixed
points and of order two such that $\mathcal{H}(\tau)=\lambda T$ for some
$\lambda\in\mathbb{C}$.∎

Suppose in a class of an association scheme PST occurs and that
$E_{0},\ldots,E_{d}$ are the idempotents of the scheme. By Theorem 2.2, $T$
must be one of the classes of the scheme and since the eigenvalues of $T$ are
$\\{-1,+1\\}$, for any $j=0,\ldots,d$, we have $TE_{j}=\pm E_{j}$. As in [3],
we define a partition $(\mathcal{I}^{+}_{T},\mathcal{I}^{-}_{T})$ of
$\\{0,\ldots,d\\}$ as $j\in\mathcal{I}^{+}_{T}$ if $TE_{j}=E_{j}$ and
$j\in\mathcal{I}^{-}_{T}$ otherwise. We might drop the subscript $T$ if $T$ is
clear from the context. Furthermore, for any $x\in\mathbb{Z}$ we denote by
$\mathrm{ord}_{2}(x)$ the exponent of $2$ in the factorization of $x$ and by
convention we define $\mathrm{ord}_{2}(0)=+\infty$.

The following theorem, which is a part of [3, Theorem 4.3], provides other
necessary conditions for the existence of PST on a graph belonging to an
association scheme. According to [3, Lemma 4.2], if PST happens in a graph
belonging to an association scheme, then all the eigenvalues of the graph are
integers. Let $X$ be a graph in an association scheme on which PST occurs and
let $\lambda_{0}>\cdots>\lambda_{d}$ be the distinct integer eigenvalues of
$X$. Define

$\alpha_{X}=\mathrm{gcd}(\\{\lambda_{0}-\lambda_{j}\;|\;j\in\\{0,\ldots,d\\}\\}).$
(2)

We will drop the subscript $X$, if the graph $X$ is clear from the context.

######  Theorem 2.4.

With the notation above, if PST occurs on $X$, then we have
$\mathrm{ord}_{2}(\lambda_{0}-\lambda_{j})>\mathrm{ord}_{2}(\alpha)$ for
$j\in\mathcal{I}^{+}$ and
$\mathrm{ord}_{2}(\lambda_{0}-\lambda_{\ell})=\mathrm{ord}_{2}(\alpha)$ for
$\ell\in\mathcal{I}^{-}$. ∎

It is clear that for any such $T$, $0\in\mathcal{I}^{+}_{T}$, but identifying
the whole partition $(\mathcal{I}^{+},\mathcal{I}^{-})$ is not easy in
general. We next point out the following observation which follows easily from
the definition (see [7]).

######  Corollary 2.5.

There is PST between the vertices of the graph $K_{2}$ at time $\tau=\pi/2$.∎

From [7] we also recall the following result which provides a sufficient
condition for a graph to be periodic.

######  Theorem 2.6.

If all eigenvalues of a graph $X$ are integers, then $X$ is periodic. ∎

We conclude this section with a brief introduction to the Johnson scheme.
Throughout the paper we will assume that $n\geq 2k$. For any $i=0,1,\ldots,k$,
we define the graph $J(n,k,i)$ to be the graph whose vertex set is the set of
all $k$-subsets of $\\{1,\ldots,n\\}$ and in which two vertices $A$ and $B$
are adjacent if $|A\cap B|=i$ (in some texts the adjacency in $J(n,k,i)$ is
defined as when $|A\cap B|=k-i$, but this makes no difference in our
discussion). It can be shown that the set
$\mathcal{A}=\\{A_{0},A_{1},\ldots,A_{k}\\}$, where $A_{i}$ is
$A(J(n,k,k-i))$, the adjacency matrix of the graph $J(n,k,k-i)$, is an
association scheme (see for example [4]). This scheme is called the Johnson
scheme, denoted by $J(n,k)$, and the classes $J(n,k,i)$ are called the
generalized Johnson graphs. The special cases of $J(n,k,0)$ and $J(n,k,k-1)$
are called the Kneser graph (often denoted by $K(n,k)$), and the Johnson
graph, respectively. Note that the adjacency matrix of $J(n,k,k)$ is the
identity matrix; that is $A_{0}=I$. In the following lemma, we observe that
most of the generalized Johnson graphs are connected.

######  Lemma 2.7.

The graph $J(n,k,i)$ is connected if the non-negative integer $i$ satisfies
$2k-n<i<k$.

###### Proof.

Consider a vertex $A=\\{a_{1},\ldots,a_{k}\\}$ from the graph $X=J(n,k,i)$.
For any vertex $B=\\{b,a_{2},\ldots,a_{k}\\}$ which is obtained by changing
one of the elements of $A$, we claim that there is a path from $A$ to $B$.
According to the conditions on $n,k$ and $i$, the set
$\\{1,\ldots,n\\}\setminus\\{a_{1},\ldots,a_{k},b\\}$ contains at least $k-i$
elements such as $c_{1},\ldots,c_{k-i}$; so we have the following path in $X$:

$A\sim\\{c_{1},\ldots,c_{k-i},a_{k-i+1},\ldots,a_{k}\\}\sim\\{b,a_{2},\ldots,a_{k-i},a_{k-i+1},\ldots,a_{k}\\}=B,$

and the claim follows. If there is a path between two vertices $V$ and $W$, we
will write $V\longleftrightarrow W$. Now we show that, for each vertex
$C=\\{b_{1},\ldots,b_{k}\\}$, $A\longleftrightarrow C$. Indeed, if $A\cap
C=\varnothing$ the following path is in $X$:

$A\longleftrightarrow\\{b_{1},a_{2},\ldots,a_{k}\\}\longleftrightarrow\\{b_{1},b_{2},a_{3},\ldots,a_{k}\\}\longleftrightarrow\cdots\longleftrightarrow\\{b_{1},b_{2},\ldots,b_{k}\\}=C.$

On the other hand, if $|A\cap C|=m>0$, then without loss of generality we may
assume that $A\cap C=\\{b_{1},\ldots,b_{m}\\}=\\{a_{1},\ldots,a_{m}\\}$. Then,
since

$\\{a_{1},\ldots,a_{m},b_{m+1},a_{m+2},\ldots,a_{k}\\}=\\{b_{1},\ldots,b_{m},b_{m+1},a_{m+2},\ldots,a_{k}\\},$

the following path exists:

$\displaystyle A$
$\displaystyle\longleftrightarrow\\{b_{1},\ldots,b_{m},b_{m+1},a_{m+2},\ldots,a_{k}\\}$
$\displaystyle\longleftrightarrow\\{b_{1},\ldots,b_{m},b_{m+1},b_{m+2},a_{m+3},\ldots,a_{k}\\}\longleftrightarrow\cdots\longleftrightarrow\\{b_{1},\ldots,b_{k}\\}=C.$

Therefore the result follows. ∎

In particular, if $k\geq 2$ and $0<i<k$, then all the generalized Johnson
graphs $J(2k,k,i)$ are connected.

It is clear that the generalized Johnson graph $J(n,k,i)$ is a regular graph
with $v={n\choose k}$ vertices and valency $v_{i}={k\choose i}{n-k\choose
k-i}$. Furthermore, it has been shown (see [4, p. 220]) that the eigenvalues
of the graphs $J(n,k,i)$ are given by

$\lambda_{j}^{i}=\sum_{\ell=0}^{k-i}(-1)^{\ell}{j\choose\ell}{k-j\choose
k-i-\ell}{n-k-j\choose k-i-\ell},\quad\text{ for }j=0,\ldots,k,$ (3)

with some appropriate multiplicities. Note that the eigenvalues of the scheme
$\mathcal{A}$ are, then, given by $p_{i}(j)=\lambda_{j}^{k-i}$. Assuming that
$i$ is clear from the context, we will just write $\lambda_{j}$ instead of
$\lambda_{j}^{i}$. An immediate consequence of (3) is that all the eigenvalues
of the graph $J(n,k,i)$ are integers. Hence, according to Theorem 2.6, we
observe the following.

######  Corollary 2.8.

All graphs in the Johnson scheme are periodic. ∎

##  3 PST on the Johnson Scheme

In this section we will prove the main result of the paper; i.e. we address
the question of whether perfect state transfer can occur in any class of the
Johnson scheme. First, we provide a necessary condition for the existence of
PST in the Johnson scheme.

######  Proposition 3.1.

If a graph in the Johnson scheme $J(n,k)$ admits PST then we must have $n=2k$.

###### Proof.

If there is PST in $X$, according to Theorem 2.2, there is a graph $J(n,k,i)$
in the scheme such that $A(J(n,k,i))=T$ is a permutation matrix of order two;
hence $v={n\choose k}$ must be even and one of the graphs of the scheme must
be the union of $\frac{1}{2}{n\choose k}$ copies of $K_{2}$ edges, that is,
$J(n,k,i)\cong\frac{1}{2}{n\choose k}K_{2}$. This implies that the valency

${k\choose i}{n-k\choose k-i}$

equals $1$. Hence, ${k\choose i}=1={n-k\choose k-i}$. The first equality
implies $i=k$ or $i=0$, but if the former happens, the graph $J(n,k,i)$ will
be the empty graph which implies that $T$ is the identity matrix, a
contradiction. Thus we can only have $i=0$. Now the second equality implies
$n=2k$. ∎

######  Corollary 3.2.

The Kneser graph $K(n,k)$ admits PST if and only if $n=2k$.

###### Proof.

If $K(n,k)=J(n,k,0)$ has PST, then according to Proposition 3.1, $n=2k$. On
the other hand, since $K(2k,k)\cong\frac{1}{2}{2k\choose k}K_{2}$ and there is
PST on $K_{2}$ (Corollary 2.5), the result follows. ∎

In the rest of this section we will show that the Kneser graph $J(2k,k,0)$ is
the only graph in the Johnson scheme $J(2k,k)$ which has PST. In other words,
we prove the following theorem, which is the main result of the paper.

######  Theorem 3.3.

There is PST in the class $J(n,k,i)$ of the Johnson scheme $J(n,k)$ if and
only if $n=2k$ and $i=0$.

In order to prove Theorem 3.3, we need several preliminary lemmas. First note
that, using (3), we can list all the eigenvalues of $J(2k,k,i)$.

######  Lemma 3.4.

For any $i=0,\ldots,k$, the eigenvalues of $J(2k,k,i)$ are given by

$\lambda_{j}=\sum_{\ell=0}^{k-i}(-1)^{\ell}{j\choose\ell}{k-j\choose
i-j+\ell}^{2},\quad j=0,\ldots,k.\qed$

In some special cases, we can simplify the formula of the eigenvalues as
follows.

$\displaystyle\lambda_{0}={k\choose i}^{2},$ (4)
$\displaystyle\lambda_{1}={k\choose i}^{2}-2{k\choose i}{k-1\choose i},$ (5)
$\displaystyle\lambda_{k}=(-1)^{k-i}{k\choose i},$ (6)
$\displaystyle\lambda_{k-1}=(-1)^{k-i}\left[{k\choose i}-2{k-1\choose
i}\right],$ (7)
$\displaystyle\lambda_{i}=\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell}{k-i\choose\ell}^{2},$
(8)
$\displaystyle\lambda_{i+1}=\sum_{\ell=0}^{k-i}(-1)^{\ell}{i+1\choose\ell}{k-i-1\choose\ell-1}^{2}.$
(9)

In particular, in the scheme $\mathcal{A}$, we have $v_{i}={k\choose i}^{2}$.
Next, we identify the partition $(\mathcal{I}^{-},\mathcal{I}^{+})$ for the
generalized Johnson graph $J(2k,k,i)$.

######  Proposition 3.5.

For any $i=1,\ldots,k-1$ and any eigenvalue $\lambda_{j}$ of $J(2k,k,i)$, we
have $j\in\mathcal{I}^{+}$ if $j$ is even and $j\in\mathcal{I}^{-}$ if $j$ is
odd.

###### Proof.

Let $\\{E_{0},\ldots,E_{k}\\}$ be the idempotents of the scheme $\mathcal{A}$
and $T=A_{k}=A(J(2k,k,0))$ be the adjacency matrix of the Kneser graph
$J(2k,k,0)$. Let $i=1,\ldots,k-1$ be arbitrary. Recall that
$\lambda_{j}=p_{k-i}(j)$. We sort the vertices of the scheme in the
lexicographic order of the $k$-subsets of $\\{1,\ldots,2k\\}$, so that the
first vertex is $U=\\{1,\ldots,k\\}$ and the last (i.e. the $v$-th) vertex is
$\overline{U}$ so $T$ is anti-diagonal. As mentioned before Theorem 2.4, for
any $j=0,\ldots,k$, we have $TE_{j}=\pm E_{j}$. This means that for any $j$,
$(TE_{j})_{1,1}=\pm(E_{j})_{1,1}$. On the other hand, we have
$(TE_{j})_{1,1}=(E_{j})_{1,v}$. Thus $j\in\mathcal{I}^{+}$ if
$(E_{j})_{1,v}=(E_{j})_{1,1}$ and $j\in\mathcal{I}^{-}$ otherwise. Note that
$(E_{j})_{1,1}$ is positive (indeed the diagonal entries of these idempotent
are always positive). Now, using (1) and Proposition 2.1, we have

$E_{j}=\frac{1}{v}\sum_{\ell=0}^{k}q_{j}(\ell)A_{\ell}=\frac{m_{j}}{v}\sum_{\ell=0}^{k}\frac{p_{\ell}(j)}{v_{\ell}}A_{\ell}.$

Since $(A_{k})_{1,v}=1$, we deduce that

$(E_{j})_{1,v}=\frac{m_{j}}{v}\frac{p_{k}(j)}{v_{k}}(A_{k})_{1,v}=\frac{m_{j}}{v}p_{k}(j).$

But $p_{k}(j)$ are the eigenvalues of the Kneser graph and according to Lemma
3.4,

$p_{k}(j)=\lambda_{j}=(-1)^{j}.$

Therefore $(E_{j})_{1,v}$ is positive if and only if $j$ is even and the
result follows. ∎

We first consider the problem of existence of PST in the case where ${k\choose
i}$ is even.

######  Lemma 3.6.

For any $i=1,\ldots,k-1$, if ${k\choose i}$ is even, then there is no PST on
$J(2k,k,i)$.

###### Proof.

Using (5), we have $\lambda_{1}={k\choose i}^{2}-2{k\choose i}{k-1\choose i}$
and according to Proposition 3.5, $1\in\mathcal{I}^{-}$ and

$\lambda_{0}-\lambda_{1}={k\choose i}^{2}-{k\choose i}^{2}+2{k\choose
i}{k-1\choose i}=2{k\choose i}{k-1\choose i}.$ (10)

If $\mathrm{ord}_{2}(\alpha)=t$, then for any $j=1,\ldots,k$, we must have
$2^{t}|\lambda_{0}-\lambda_{j}$. In particular,
$2^{t}|\lambda_{0}-\lambda_{k}$ and $2^{t}|\lambda_{0}-\lambda_{k-1}$. Hence,
$2^{t}|\lambda_{k}-\lambda_{k-1}$. That is,
$t\leq\mathrm{ord}_{2}(\lambda_{k}-\lambda_{k-1})$. On the other hand, using
(6) and (7) we have

$\lambda_{k}-\lambda_{k-1}=2(-1)^{k-i}{k-1\choose i};$

and since ${k\choose i}$ is even, we have
$\mathrm{ord}_{2}(\lambda_{k}-\lambda_{k-1})<\mathrm{ord}_{2}(\lambda_{0}-\lambda_{1})$.
This means that
$\mathrm{ord}_{2}(\alpha)<\mathrm{ord}_{2}(\lambda_{0}-\lambda_{1})$.
According to Theorem 2.4, this shows that $J(2k,k,i)$ cannot have PST. ∎

To complete the proof, therefore, we should consider the case where ${k\choose
i}$ is odd. To this goal, we will need to make use of Lucas’s famous Theorem
(see, for example [5]).

######  Theorem 3.7.

Suppose $a$ and $b$ are non-negative integers and $p$ is a prime. Also let

$a=a_{r}p^{r}+a_{r-1}p^{r-1}+\cdots+a_{1}p+a_{0}\;\;\text{and}\;\;b=b_{r}p^{r}+b_{r-1}p^{r-1}+\cdots+b_{1}p+b_{0}$

be the base-$p$ representation of $a$ and $b$, respectively. Then

${a\choose b}\equiv\prod_{\ell=0}^{r}{a_{\ell}\choose
b_{\ell}}\;\;(\mathrm{mod}\,p).\qed$

For the case $p=2$, we get the following consequence of Theorem 3.7. We will
write $b\preccurlyeq a$ if every digit of binary (i.e. base-$2$)
representation of $b$ is less than or equal to the corresponding digit of $a$.

######  Theorem 3.8.

For any non-negative $a$ and $b$, ${a\choose b}$ is odd if and only if
$b\preccurlyeq a$.∎

The following is an easy consequence of Theorem 3.8.

######  Corollary 3.9.

If $a$ is even and $b$ is odd, then ${a\choose b}$ is even.

In what follows, we assume, always, that $i\in\\{1,2,\ldots,k-1\\}$.

######  Lemma 3.10.

If ${k\choose i}$ is odd, then, for any $\ell=1,\ldots,k-i$, either
${i\choose\ell}$ or ${k-i\choose\ell}$ is even.

###### Proof.

Suppose ${i\choose\ell}$ and ${k-i\choose\ell}$ are both odd. Then, according
to Theorem 3.8, we have $\ell\preccurlyeq i$ and $\ell\preccurlyeq k-i$. Since
$\ell\neq 0$, there is a digit $\ell_{j}$ of the binary representation of
$\ell$ such that $\ell_{j}=1$. Thus we must have $i_{j}=1$ and $(k-i)_{j}=1$.
On the other hand, since ${k\choose i}$ is odd, we have $i\preccurlyeq k$,
which implies that $i_{j}\leq k_{j}$, thus $k_{j}=1$. But then we have
$(k-i)_{j}=k_{j}-i_{j}=1-1=0$, which is a contradiction. Thus the result
follows. ∎

For the results bellow, recall the definition of $\alpha$ from (2).

######  Lemma 3.11.

If ${k\choose i}$ is odd, then $\mathrm{ord}_{2}(\alpha)\leq 1$.

###### Proof.

Using (9) and Pascal’s rule, we have

$\displaystyle\lambda_{i+1}$
$\displaystyle=\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell-1}^{2}+\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell-1}{k-i-1\choose\ell-1}^{2}.$

Since
${k-i\choose\ell}^{2}={k-i-1\choose\ell}^{2}+{k-i-1\choose\ell-1}^{2}+2{k-i-1\choose\ell}{k-i-1\choose\ell-1}$,
we deduce that

$\displaystyle\lambda_{i+1}=$
$\displaystyle\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell}{k-i\choose\ell}^{2}-\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}^{2}$
$\displaystyle-2\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}{k-i-1\choose\ell-1}$
$\displaystyle+\sum_{\ell=0}^{k-i}(-1)^{\ell}{i\choose\ell-1}{k-i-1\choose\ell-1}^{2}$
$\displaystyle=$
$\displaystyle\lambda_{i}-\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}^{2}+\sum_{\ell=1}^{k-i}(-1)^{\ell}{i\choose\ell-1}{k-i-1\choose\ell-1}^{2}$
$\displaystyle-2\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}{k-i-1\choose\ell-1}$
$\displaystyle=$
$\displaystyle\lambda_{i}-\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}^{2}-\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}^{2}$
$\displaystyle-2\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}{k-i-1\choose\ell-1}$
$\displaystyle=$
$\displaystyle\lambda_{i}-2\sum_{\ell=0}^{k-i-1}(-1)^{\ell}\left[{i\choose\ell}{k-i-1\choose\ell}^{2}+{i\choose\ell}{k-i-1\choose\ell}{k-i-1\choose\ell-1}\right]$
$\displaystyle=$
$\displaystyle\lambda_{i}-2\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i-1\choose\ell}\left[{k-i-1\choose\ell}+{k-i-1\choose\ell-1}\right]$
$\displaystyle=$
$\displaystyle\lambda_{i}-2\sum_{\ell=0}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i\choose\ell}{k-i-1\choose\ell}$
$\displaystyle=$
$\displaystyle\lambda_{i}-2-2\sum_{\ell=1}^{k-i-1}(-1)^{\ell}{i\choose\ell}{k-i\choose\ell}{k-i-1\choose\ell}\equiv\lambda_{i}-2-0\quad(\mathrm{mod}\,4).$

The last line follows from the fact that according to Lemma 3.10, all the
summands in the last summation are even. This shows that
$\lambda_{i}-\lambda_{i+1}\equiv-2\equiv 2$ (mod $4$). Now if
$\mathrm{ord}_{2}(\alpha)>1$, then $4|\lambda_{0}-\lambda_{i}$ and
$4|\lambda_{0}-\lambda_{i+1}$ and hence $4|\lambda_{i}-\lambda_{i+1}$, which
is a contradiction. Therefore $\mathrm{ord}_{2}(\alpha)\leq 1$. ∎

######  Lemma 3.12.

If ${k\choose i}$ is odd and ${k-1\choose i}$ is even, then $J(2k,k,i)$ cannot
have PST.

###### Proof.

According to (10), we have $\mathrm{ord}_{2}(\lambda_{0}-\lambda_{1})\geq 2$;
hence using Lemma 3.11, Theorem 2.4 and the fact that $1\in\mathcal{I}^{-}$,
the result follows. ∎

It remains to consider the case where ${k\choose i}$ and ${k-1\choose i}$ are
both odd. According to Corollary 3.9, these imply that $i$ is even. To show
the result in this case, we will make use of the following lemmas.

######  Lemma 3.13.

If ${k\choose i}$ is odd, then for any $\ell=0,1,\ldots,k-i$, the following
product is even:

${k-i\choose\ell}{i\choose k-i-\ell}{i-2\choose k-i-\ell-2}.$

###### Proof.

Let $s$ be the smallest index for which $i_{s}$, the $s$-th digit of $i$ in
the binary representation, is equal to $1$. As $i\preccurlyeq k$, we have
$k_{s}=1$; thus $(k-i)_{s}=0$. Suppose ${k-i\choose\ell}$ and ${i\choose
k-i-\ell}$ are both odd. Since $\ell\preccurlyeq k-i$, it follows that
$\ell_{s}=0$ and the binary representation of $k-i-\ell$ will be

$k-i-\ell=\cdots(k_{s+1}-i_{s+1}-\ell_{s+1})0(k_{s-1}-\ell_{s-1})\cdots(k_{0}-\ell_{0}).$

Now $k-i-\ell\preccurlyeq i$ implies, first, that

$k-i-\ell=\cdots(k_{s+1}-i_{s+1}-\ell_{s+1})0\cdots 0.$

It, further, implies that for every $t\geq s+1$, if $i_{t}=0$, then
$k_{t}-i_{t}-\ell_{t}=0$ and if $i_{t}=1$, then $k_{t}=1$ from which we deduce
that $k_{t}-i_{t}=\ell_{t}=0$ which, again, implies that
$k_{t}-i_{t}-\ell_{t}=0$. Thus $k-i-\ell=0$ and ${i-2\choose k-i-\ell-2}=0$;
therefore the result follows. ∎

To prove the next result, we will make use of the well-known Vandermode
Convolution identity: let $a,b$ and $c$ be non-negative integers. Then

$\sum_{\ell=0}^{a}{a\choose\ell}{b\choose c-\ell}={a+b\choose c}.$ (11)

######  Lemma 3.14.

If ${k\choose i}$ and ${k-1\choose i}$ are odd and $k$ is even, then the
summation

$S=\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i-2}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}$

is odd.

###### Proof.

Since $k-i$ is even, according to Corollary 3.9, we have $S\equiv S^{\prime}$
(mod $2$), where

$S^{\prime}=\sum_{\ell=0}^{k-i}{k-i\choose\ell}{i-2\choose k-i-\ell-2}^{2},$

where $\ell$ ranges over all the numbers (even and odd). On the other hand,
since for any integer $x$, we have $x\equiv x^{2}$ (mod $2$), we can write

$\displaystyle S^{\prime}$
$\displaystyle\equiv\sum_{\ell=0}^{k-i}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}\;(\mathrm{mod}\,2).$

Then using (11) we deduce that

$S^{\prime}\equiv{k-2\choose i}\;(\mathrm{mod}\,2).$

On the other hand, by the assumption that ${k-1\choose i}$ is odd and using
Corollary 3.9, we have

${k-2\choose i}={k-1\choose i}-{k-2\choose i-1}\equiv 1\;(\mathrm{mod}\,2).$

Therefore the result follows. ∎

######  Lemma 3.15.

If ${k\choose i}$ and ${k-1\choose i}$ are both odd and $k$ is even, then

$\lambda_{k-i+2}-\lambda_{k-i}\equiv 2\quad(\mathrm{mod}\;4).$

###### Proof.

Recall that the assumptions imply that $i$ is even. We start by writing

$\displaystyle\lambda_{k-i+2}-\lambda_{k-i}$
$\displaystyle=\sum_{\ell=0}^{k-i}(-1)^{\ell}\left[{k-i+2\choose\ell}{i-2\choose
k-i-\ell}^{2}-{k-i\choose\ell}{i\choose k-i-\ell}^{2}\right].$

It is obvious (noting Theorem 3.8) that the summands of this summation, for
any odd $\ell$, are divisible by $4$; thus we may write

$\displaystyle\lambda_{k-i+2}-\lambda_{k-i}$
$\displaystyle\equiv\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i}{k-i+2\choose\ell}{i-2\choose
k-i-\ell}^{2}-{k-i\choose\ell}{i\choose k-i-\ell}^{2}\;(\mathrm{mod}\,4),$

Using Pascal’s rule and Corollary 3.9, for any such $\ell$, we can write

$\displaystyle{k-i+2\choose\ell}{i-2\choose
k-i-\ell}^{2}\equiv{k-i\choose\ell}{i-2\choose
k-i-\ell}^{2}+{k-i\choose\ell-2}{i-2\choose k-i-\ell}^{2}$
$\displaystyle\equiv{k-i\choose\ell}{i\choose
k-i-\ell}^{2}+{k-i\choose\ell}{i-2\choose k-i-\ell-2}^{2}$
$\displaystyle-2{k-i\choose\ell}{i\choose k-i-\ell}{i-2\choose
k-i-\ell-2}+{k-i\choose\ell-2}{i-2\choose k-i-\ell}^{2}\;(\mathrm{mod}\,4).$

Therefore, using Lemma 3.13, we can write

$\displaystyle\lambda_{k-i+2}-\lambda_{k-i}\equiv\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}+{k-i\choose\ell-2}{i-2\choose k-i-\ell}^{2}$
$\displaystyle\equiv\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i-2}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}+\sum_{\begin{subarray}{c}\ell=2\\\
\ell:\text{even}\end{subarray}}^{k-i}{k-i\choose\ell-2}{i-2\choose
k-i-\ell}^{2}$ $\displaystyle\equiv\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i-2}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}+\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i-2}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}$ $\displaystyle\equiv 2\,\sum_{\begin{subarray}{c}\ell=0\\\
\ell:\text{even}\end{subarray}}^{k-i-2}{k-i\choose\ell}{i-2\choose
k-i-\ell-2}^{2}\;(\mathrm{mod}\,4),$

This, according to Lemma 3.14, completes the proof. ∎

Using a similar approach, one can prove the following result.

######  Lemma 3.16.

If ${k\choose i}$, ${k-1\choose i}$ and $k$ are odd, then

$\lambda_{k-i+1}-\lambda_{k-i-1}\equiv 2\quad(\mathrm{mod}\;4).\qed$

Now we are ready to prove the result in the remaining case.

######  Lemma 3.17.

If ${k\choose i}$ and ${k-1\choose i}$ are both odd, then $J(2k,k,i)$ cannot
have PST.

###### Proof.

Suppose there is PST on $J(2k,k,i)$. Then, according to Theorem 2.4, we must
have $\mathrm{ord}_{2}(\alpha)=\mathrm{ord}_{2}(\lambda_{0}-\lambda_{1})$,
which implies, using (10), that $\mathrm{ord}_{2}(\alpha)=1$. If $k$ is even,
then according to Proposition 3.5, we have $k-i+2,k-i\in\mathcal{I}^{+}$ and,
according to Theorem 2.4, it must be the case that
$\mathrm{ord}_{2}(\lambda_{0}-\lambda_{k-i+2})>1$ and
$\mathrm{ord}_{2}(\lambda_{0}-\lambda_{k-i})>1$. But then we must have
$4|\lambda_{k-i+2}-\lambda_{k-i}$ which contradicts Lemma 3.15. Also, if $k$
is odd, then $k-i+1,k-i-1\in\mathcal{I}^{+}$ and we get a similar
contradiction with Lemma 3.16. This completes the proof. ∎

Remark 1. In order to get the desired “contradiction” based on the eigenvalue
differences in Lemmas 3.11, 3.15 and 3.16, we have picked some “very special”
eigenvalues. Indeed, these eigenvalues are suggested by some computer
calculations. It is interesting that the eigenvalue differences rarely result
in a contradiction; that is, for majority of the eigenvalues of the graphs,
the “$\mathrm{ord}_{2}$” condition, actually, holds.

Now we can summarize the proof of the main result as follows.

###### Proof of Theorem 3.3.

The proof follows from Proposition 3.1, Corollary 3.2 and Lemmas 3.6 and 3.12,
3.17. ∎

##  4 PST on Sums of the Classes

In this section, we consider sums of the classes of the Johnson scheme
$J(n,k)$ and investigate the possibility of existence of PST on the graphs
obtained by the unions of some of the generalized Johnson graphs. We first
recall the following two results (see [7]).

######  Proposition 4.1.

Suppose $X$ is a regular graph with PST from a vertex $u$ to another vertex
$v$ at time $\tau$. If $\tau$ is an integer multiple of $2\pi/|V(X)|$, then
there is PST from $u$ to $v$ at time $\tau$ in the complement graph
$\overline{X}$ of $X$. ∎

######  Proposition 4.2.

If there is PST in a graph $X$ from $u$ to $v$ and also from $u$ to $w$, then
$u=w$.∎

######  Proposition 4.3.

Let $u$ and $v$ be two vertices of a graph $X$. If there is an automorphism
$\sigma$ of $X$ such that $\sigma(u)=u$ and $\sigma(v)=w\neq v$, then there
cannot be PST between $u$ and $v$.

###### Proof.

There is a permutation matrix $P$ corresponding to the automorphism $\sigma$
such that $P^{T}AP=A$ and the condition on $\sigma$ implies that

$(P^{T}AP)_{u,v}=A_{u,w}.$

Since there is PST between $u$ and $v$, there is a time $\tau$ at which
$|\mathcal{H}(\tau)_{u,v}|=1$, Now since

$\mathcal{H}(\tau)_{u,v}=\left(\mathrm{e}^{i\tau
A}\right)_{u,v}=\left(\mathrm{e}^{i\tau
P^{T}AP}\right)_{u,v}=\left(P^{T}\mathrm{e}^{i\tau
A}P\right)_{u,v}=\left(P^{T}\mathcal{H}(\tau)P\right)_{u,v}=\mathcal{H}(\tau)_{u,w};$

thus

$|\mathcal{H}(\tau)_{u,w}|=1,$

which contradicts Proposition 4.2; hence the result follows. ∎

The following is an immediate consequence of Proposition 4.3, which has
previously been observed in the literature.

######  Corollary 4.4.

For any $n>2$, there is no PST in the complete graph $K_{n}$.∎

In order to prove the next result, we make use of the fact that any
permutation on $\\{1,\ldots,n\\}$, naturally induces an automorphism of a
single class of the Johnson scheme $J(n,k)$ and, thus, it induces an
automorphism of a graph which is the union of any number of the single
classes.

######  Lemma 4.5.

Let $X$ be a graph which is a union of some of the classes of the Johnson
scheme $J(n,k)$. If there is PST between two vertices $A$ and $B$ of $X$, then
the $k$-subsets $A$ and $B$ are complement of each other in
$\\{1,\ldots,n\\}$.

###### Proof.

Suppose $A$ and $B$ are vertices of $X$ which are not complement of each
other. Assume, without loss of generality, that $A=\\{1,\ldots,k\\}$; thus
$B\neq\\{k+1,\ldots,n\\}$. Consider the two possible cases.

Case 1: $A\cap B\neq\varnothing$. In this case, there are elements
$x,x^{\prime}\in A$ such that $x\in A\cap B$ and $x^{\prime}\in A\setminus B$.
Then the transposition $\sigma=(x\;x^{\prime})\in\mathrm{Sym}(n)$ is an
automorphism of $X$ which fixes the vertex $A$ but moves the vertex $B$.
Therefore, according to Proposition 4.3, there cannot be PST between $A$ and
$B$.

Case 2: $A\cap B=\varnothing$. In this case, $B\subsetneq\\{k+1,\ldots,n\\}$.
Hence there are elements $y,y^{\prime}\in\\{k+1,\ldots,n\\}$ such that $y\in
B$ and $y^{\prime}\notin B$. Then the transposition
$(y\;y^{\prime})\in\mathrm{Sym}(n)$ is an automorphism of $X$ which fixes $A$
but moves $B$. Then we get a similar contradiction as in Case 1. ∎

######  Corollary 4.6.

Let $X$ be a graph which is a union of some of the classes of the Johnson
scheme $J(n,k)$. If there is PST between two vertices of $X$, then $n=2k$.∎

Note that Proposition 3.1 is a special case of Corollary 4.6 when $X$ is just
a single class.

In order to see what happens when we consider a union of some classes in the
Johnson scheme $J(2k,k)$, we first look at the initial case where $k=2$. Note
that the scheme $J(4,2)$ consists of the matrices $\\{I,R,T\\}$ where the
$6={4\choose 2}$-vertex graphs corresponding to the matrices $T$ and $R$, are
the Kneser graph $K(4,2)\cong 3K_{2}$ and the graph $K_{6}\setminus(3K_{2})$,
respectively. According to Theorem 3.3, the graph corresponding to $R$ cannot
have PST. Furthermore, the union of these two graph is the complete graph
$K_{6}$ which, according to Corollary 4.4, does not have PST. Therefore, no
union of the graphs in the scheme $J(4,2)$, can have PST (except for the
single class of the graph of $T$). However, the situation is a bit different
for the next case where $k=3$. We observe the following general fact.

######  Corollary 4.7.

Let $X$ be the graph

$X=J(2k,k,1)\cup\cdots\cup J(2k,k,k-1).$

If ${2k\choose k}\equiv 0$ (mod $4$), then for any vertex $A$ of $X$, there is
PST from $A$ to the vertex $\overline{A}$ at time $\pi/2$.

###### Proof.

First note that PST occurs between any vertex $A$ and its complement
$\overline{A}$ in the Kneser graph $K(2k,k)=J(2k,k,0)$ corresponding to the
class $T$ of $J(2k,k)$ at time $\pi/2$. Now since $|V(K(2k,k))|=|V(X)|=4a$,
for some integer $a$, we have

$\frac{\pi}{2}=a\,\frac{2\pi}{|V(x)|},$

hence, according to Proposition 4.1, there is PST between $A$ and
$\overline{A}$ on $X=\overline{K(2k,k)}$ at time $\pi/2$, for any vertex $A$.
∎

For the case $k=3$, we have $|V(J(n,k))|=20$. The scheme has the classes
$\\{I,R_{1},R_{2},T\\}$, where the graphs corresponding to the classes $R_{1}$
and $R_{2}$ are two $9$-regular isomorphic graphs. According to Corollary 4.7,
on the union of these two graphs, PST occurs between any vertex $A$ and its
complement $\overline{A}$ (at time $\pi/2$). Furthermore, the union of all the
classes, i.e. the complete graph, does not have PST. On the other hand,
computer calculations with Maple software, show that there cannot be PST
between any vertex $A$ and $\overline{A}$ on the graph whose adjacency matrix
is $T+R_{1}$ (or $T+R_{2}$). Therefore, the only case where PST can occur on a
union of the classes, is where we consider the union of all the classes except
the Kneser graph $K(6,3)$. Therefore come up with the following important
question.

Question. Which unions of the graphs in the Johnson scheme $J(2k,k)$ can have
PST?

So far, besides Corollary 4.7, the most we can say is the following result.

######  Lemma 4.8.

Let $X$ be a graph which is a union

$J(n,k,i_{1})\cup\cdots\cup J(n,k,i_{s})$

of some of the classes of the Johnson scheme $J(n,k)$, where $s>1$. If there
is PST on $X$ then $n=2k$ and there is a permutation matrix $T$ with no fixed
points and of order two such that $\mathcal{H}_{X}(\tau)=\lambda T$ for some
$\lambda\in\mathbb{C}$ with $|\lambda|=1$.

###### Proof.

Since $X$ is vertex-transitive and, according to Lemma 2.7, it is connected,
the result follows from Theorem 2.3 and Corollary 4.6. Note that since
$\mathcal{H}_{X}(\tau)$ is unitary, we must have $|\lambda|=1$. ∎

##  5 Further Work

We considered the problem of existence of PST on the classes of the Johnson
scheme $J(n,k)$. It was not hard to see that $n=2k$ is a necessary condition
and also to see that the Kneser graph $J(2k,k,0)$, trivially admits PST.
Although the other classes $J(2k,k,i)$ ($1\leq i\leq k-1$), display important
evidences of capability of having PST (see Remark 3.17, for example), using
some eigenvalue analyses, we showed that none of these classes can admit PST.
In addition, we questioned in which unions of the graph in the Johnson scheme
$J(2k,k)$, PST can occur which seems an interesting problem.

It sounds an interesting problem to consider other schemes as well. For
example, given a permutation group $G\leq\mathrm{Sym}(n)$, which classes of
the conjugacy class scheme of $G$ can possibly have PST? It is not hard to see
that two major necessary conditions for $G$ to have PST on any of the graphs
in its conjugacy class scheme are as follows: (a) any conjugacy class of $G$
must be closed under inversion, and (b) $G$ must have a singleton conjugacy
class other than the identity class. As an example of such a group, we can
name the dihedral group $D_{2n}\leq\mathrm{Sym}(n)$, when $n$ is even. Indeed
we can show that there exist PST in some of the classes of the conjugacy class
scheme of $D_{2n}$ (where it occurs on $K_{2}$’s) and the examples show that
there are groups other than the dihedral groups which have PST. Therefore it
seems an interesting problem to classify the permutation groups, acting on
$\\{1,\ldots,n\\}$, which have the (necessary) conditions (a) and (b).

## Acknowledgment

The first author would like to thank the financial support of the Iranian
National Elites’ Foundation.

References

## References

  * [1] Wang-Chi Cheung and Chris Godsil.  Perfect state transfer in cubelike graphs.  Linear Algebra and its Applications, 435(10):2468–2474, 2011.
  * [2] Matthias Christandl, Nilanjana Datta, Artur Ekert, and Andrew J Landahl.  Perfect state transfer in quantum spin networks.  Physical review letters, 92(18):187902, 2004.
  * [3] Gabriel Coutinho, Chris Godsil, Krystal Guo, and Frédéric Vanhove.  Perfect state transfer on distance-regular graphs and association schemes.  Linear Algebra and its Applications, 478:108–130, 2015.
  * [4] Bannai Eiichi and Ito Tatsuro.  Algebraic combinatorics i. association schemes.  Mathematics Lecture Note Series, 1984.
  * [5] Nathan J Fine.  Binomial coefficients modulo a prime.  The American Mathematical Monthly, 54(10):589–592, 1947.
  * [6] Chris Godsil.  Periodic graphs.  Electron. J. Combin, 18(1):P23, 2011.
  * [7] Chris Godsil.  State transfer on graphs.  Discrete Mathematics, 312(1):129–147, 2012.
  * [8] Chris Godsil and Gordon F Royle.  Algebraic graph theory, volume 207.  Springer Science & Business Media, 2013.
  * [9] Marko D. Petković and Milan Bašić.  Further results on the perfect state transfer in integral circulant graphs.  Computers & Mathematics with Applications, 61(2):300 – 312, 2011\.