# On the dissociation number of Kneser graphs

Boštjan Brešara,b
Tanja Draveca,b
bostjan.bresar<EMAIL_ADDRESS>
###### Abstract

A set $D$ of vertices of a graph $G$ is a dissociation set if each vertex of
$D$ has at most one neighbor in $D$. The dissociation number of $G$,
$diss(G)$, is the cardinality of a maximum dissociation set in a graph $G$. In
this paper we study dissociation in the well-known class of Kneser graphs
$K_{n,k}$. In particular, we establish that the dissociation number of Kneser
graphs $K_{n,2}$ equals $\max{\\{n-1,6\\}}$. We show that for any $k\geq 2$,
there exists $n_{0}\in\mathbb{N}$ such that $diss(K_{n,k})=\alpha(K_{n,k})$
for any $n\geq n_{0}$. We consider the case $k=3$ in more details and prove
that $n_{0}=8$ in this case. Then we improve a trivial upper bound
$2\alpha(K_{n,k})$ for the dissociation number of Kneser graphs $K_{n,k}$ by
using Katona’s cyclic arrangement of integers from $\\{1,\ldots,n\\}$. Finally
we investigate the odd graphs, that is, the Kneser graphs with $n=2k+1$. We
prove that $diss(K_{2k+1,k})={2k\choose k}$.

a Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Keywords: dissociation set, $k$-path vertex cover, Kneser graph, odd graphs,
independence number

AMS Subj. Class. (2010): 05C69

##  1 Introduction

The Kneser graph, $K_{n,k}$, where $n,k$ are positive integers such that
$n\geq 2k$, has the $k$-subsets of an $n$-set as its vertices, and two
$k$-subsets are adjacent in $K_{n,k}$ if they are disjoint. The Erdős–Ko–Rado
theorem [8] determined the independence number $\alpha(K_{n,k})$ of the Kneser
graph $K_{n,k}$ to be equal to ${{n-1}\choose{k-1}}$. Another famous result is
Lovász’s proof of Kneser’s conjecture, which determines the chromatic number
of Kneser graphs [17], see also Matoušek for a combinatorial proof of this
result [18]. Many other invariants were later considered in Kneser graphs by a
number of authors. The diameter of a Kneser graph $K_{n,k}$ was computed in
[23] and the hamiltonicity was researched in [7, 22]. The domination number of
Kneser graphs was also studied in several papers [11, 12, 20], but there is no
such complete solution for domination number of Kneser graphs as is the case
with the chromatic and the independence number. Recently, the $P_{3}$-hull
number of Kneser graphs was completely resolved for all Kneser graphs
$K_{n,k}$ with the sole exception of odd graphs, that is, when $n=2k+1$; see
[9]. The problem of independence in graphs can be rephrased as the search for
a (largest) induced subgraph in which all components have only one vertex. In
this paper, we extend the study to search for a largest induced subgraph of a
Kneser graph in which all components have at most two vertices.

A set $D$ of vertices in a graph $G$ is called a dissociation set if the
subgraph induced by vertices of $D$ has maximum degree at most 1. The
cardinality of a maximum dissociation set $D$ in a graph $G$ is called the
dissociation number of $G$, and is denoted by $diss(G)$. The dissociation
number was introduced by Papadimitriou and Yannakakis [21] in relation with
the complexity of the so-called restricted spanning tree problem. A dual
concept to dissociation set can be generalized to $m$-path vertex cover, which
was introduced in [5] and studied in several papers [2, 4, 13]; it is defined
as a set $S$ of vertices in $G$ such that $G-S$ does not contain any path
$P_{m}$. The corresponding invariant, the $m$-path vertex cover number of an
arbitrary graph $G$, is denoted by $\psi_{m}(G)$. Note that dissociation sets
are complements of $3$-path vertex covers of $G$, and so
$diss(G)=|V(G)|-\psi_{3}(G)$. The decision version of the $m$-path vertex
cover number is NP-complete [5], moreover, in the case $m=3$ it is NP-complete
even in bipartite graphs which are $C_{4}$-free and have maximum degree 3 [1];
see also [19] for further strengthening of this result and [14] for an
approximation algorithm. Some variations of the problem were already studied
as well (see e.g. [6, 16]). We mention in passing that graphs in which all
maximal dissociation sets are of the same size were studied in [3].

The independence number of a graph $G$, $\alpha(G)$, can be defined as the
order of the largest induced subgraph of $G$ with maximum degree 0. If 0 in
this definition is replaced by 1, then we get a definition of the dissociation
number of a graphs. Since any independent set of a graph $G$ is also a
dissociation set of $G$, the independence number of $G$ is a lower bound for
the dissociation number of $G$. In addition, one can easily get the upper
bound for the dissociation number of $G$ as a function of $\alpha(G)$. Let $S$
be a dissociation set of $G$ and $A\subseteq S$ a maximum independent subset
of $S$. Then every vertex of $S\setminus A$ has exactly one neighbor in $A$
and any vertex of $A$ has at most one neighbor in $S\setminus A$. Therefore
$|S\setminus A|\leq|A|$. Hence we immediately get the following bounds for the
dissociation number of $G$:

$\alpha(G)\leq diss(G)\leq 2\alpha(G).$

The paper is organized as follows. In Section 2, we first present the exact
result for the dissociation number of Kneser graphs $K_{n,2}$. Then we prove
that for any $k\geq 2$ there exists $n_{0}\in\hbox{\sf
I\kern-1.30005pt\hbox{N}}$ such that $diss(K_{n,k})=\alpha(K_{n,k})$ for any
$n\geq n_{0}$. Also, we find $n_{0}$ for $k=3$; we prove that
$diss(K_{n,3})=\alpha(K_{n,3})$ if and only if $n\geq 8$. In Section 3, we use
Katona’s cyclic arrangement of integers from his proof of Erdős-Ko-Rado
theorem [15] to improve the upper bound $2\alpha(G)$ for the dissociation
number for the case when $G$ is a Kneser graph. In Section 4, we show that the
dissociation number of odd graphs $O_{k}$ (Kneser graphs $K_{2k+1,k}$) equals
${2k\choose k}$ for $k\geq 2.$

In the rest of this section we present the notation used throughout the paper
and some basic results concerning the dissociation number of a graph.

Let $[n]=\\{1,2,\ldots,n\\}$, where $n\in\hbox{\sf I\kern-1.30005pt\hbox{N}}$.
For a graph $G=(V,E)$ and $S\subseteq V(G)$ we write $G[S]$ for the subgraph
of $G$ induced by $S$ and $G-S$ for the subgraph of $G$ induced by the set
$V(G)\setminus S$. The (open) neighborhood of $v\in V(G)$, $N_{G}(v)$, is the
set of all neighbors of $v$, while $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ denotes the
closed neighborhood of $v$. Similarly, for $S\subseteq V(G)$,
$N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$. The degree of a vertex $v$ is
$|N_{G}(v)|$. When the graph $G$ is clear from the context we omit the
subscripts. A matching $M$ in a graph $G$ is a set of edges in $G$ having the
property that no two edges in $M$ have a common endvertex. For a matching $M$
in $G$, we denote by $V(M)$ the set of endvertices of edges from $M$. A set of
pairwise non adjacent vertices in a graph $G$ is called the independent set.
The cardinality of the largest independent set of vertices in $G$ is the
independence number of $G$ and is denoted by $\alpha(G)$.

A center of a Kneser graph $K_{n,k}$ is a set $I(i)=\\{x\in V(K_{n,k}):\,i\in
x\\}$, where $i\in[n]$. Note that $I(i)$ is an independent set of vertices of
$K_{n,k}$, and $|I(i)|=\alpha(K_{n,k})={{n-1}\choose{k-1}}$. Note that for any
$n\geq 2k$, $K_{2k,k}$ is an induced subgraph of $K_{n,k}$ and hence
$diss(K_{n,k})\geq diss(K_{2k,k})=|V(K_{2k,k})|={2k\choose k}$. We state this
as follows.

###### Proposition 1.1

For any $n\geq 2k$, $diss(K_{n,k})\geq{2k\choose k}$.

##  2 Relations with the independence number

We start the study with the simplest non-trivial Kneser graphs, that is,
$K_{n,2}$, where $n\geq 5$. For the Petersen graph $K_{5,2}$, one can easily
see that $D=\\{\\{1,2\\},\\{3,4\\},\\{1,3\\},\\{1,4\\},\\{2,3\\},\\{2,4\\}\\}$
is a dissociation set. Indeed, $D$ induces a subgraph with only three edges,
namely $\\{1,2\\}\\{3,4\\}$,$\\{1,3\\}\\{2,4\\}$ and $\\{1,4\\}\\{2,3\\}$. It
is also a largest dissociation set, hence $diss(K_{5,2})=6$. The same
construction is optimal also in $K_{6,2}$ and $K_{7,2}$, but not for
$K_{n,2}$, with larger $n$, as the following result shows.

###### Proposition 2.1

For $n\geq 5$, $diss(K_{n,2})=\max\\{n-1,6\\}$.

Proof.  Note that a maximum independent set of a Kneser graphs $K_{n,2}$,
where $n>5$, is a center, its size is $n-1$, and it is also a dissociation
set. By the above observation, we get $diss(K_{n,2})\geq\max\\{n-1,6\\}$.
Suppose that $D$ is a dissociation set, which is not independent. Without loss
of generality, let $\\{\\{1,2\\},\\{3,4\\}\\}\subset D$. Note that
$V(K_{n,2})\setminus N[D]=\\{\\{1,3\\},\\{1,4\\},\\{2,3\\},\\{2,4\\}\\}$,
which implies $|D|\leq 6$. Hence, if $n>7$, a maximum dissociation set is
independent, and the proposed equality follows. $\square$

We find a similar feature for Kneser graphs $K_{n,k}$, where $k>2$. Namely, as
soon as $n$ is large enough with respect to $k$, we have
$diss(K_{n,k})=\alpha(K_{n,k})$.

###### Theorem 2.2

For any $k\geq 2$, there exists $n_{0}\in\hbox{\sf I\kern-1.30005pt\hbox{N}}$
such that for all $n$, $n\geq n_{0}$, we have

$diss(K_{n,k})=\alpha(K_{n,k})={{n-1}\choose{k-1}}.$

Proof.  The result for $k=2$ follows from Proposition 2.1. Fix $k\geq 3$, and
suppose that a maximum dissociation set $D$ is not an independent set. Assume
without loss of generality that $x=\\{1,\ldots,k\\}$ and
$y=\\{k+1,\ldots,2k\\}$ belong to $D$. Let $U=V(K_{n,k})\setminus
N[\\{x,y\\}]$. Note that every element in $U$ is a $k$-set that contains at
least one element from $x$ and at least one element from $y$. Setting
$z=\\{2k+1,\ldots,n\\}$ note that any element in $U$ consists of $i$ elements
from $z$, where $0\leq i\leq k-2$, $j$ elements from $x$, where $1\leq j\leq
k-i-1$, and consequently, $k-i-j$ elements from $y$.

Hence

$|U|=\sum_{i=0}^{k-2}{{n-2k\choose i}}\sum_{j=1}^{k-i-1}{{k\choose j}{k\choose
k-j-i}}.$

Note that $\sum_{j=1}^{k-i-1}{{k\choose j}{k\choose k-j-i}}$ is not dependent
on $n$, hence for a fixed $k$ this is a constant, while
$\sum_{i=0}^{k-2}{{n-2k\choose i}}$ is a polynomial in $n$ of degree $k-2$.
Hence $|U|=O(n^{k-2})$, and note that $|D|\leq 2+|U|$. On the other hand,
$\alpha(K_{n,k})={n-1\choose k-1}$, hence the resulting independent (and
dissociation) set is of size $\Omega(n^{k-1})$. Therefore, if $n$ is big
enough, $D$ is not a maximum dissociation set, because its size is less than
${n-1\choose k-1}$. $\square$

Note that the above proof relies on the fact that for any adjacent vertices
$x$ and $y$ of a dissociation set $D$ of $G$, we have $D\subseteq
D_{x,y}^{\prime}=\\{x,y\\}\cup(V(G)\setminus(N[x]\cup N[y]))$. In fact, we
show that for any $k\geq 2$ there exists $n_{0}^{\prime}\in\mathbb{N}$ such
that for any adjacent vertices $x,y\in V(K_{n,k})$ we have
$\alpha(K_{n,k})\geq|D^{\prime}_{x,y}|$ as soon as $n\geq n_{0}^{\prime}$. In
particular, the smallest $n_{0}$ that appears in the statement of Theorem 2.2
may be much smaller than $n_{0}^{\prime}$ which is used in the proof. Note
that $|D_{x,y}^{\prime}|=2+{n\choose k}-(2{n-k\choose k}-{n-2k\choose k})$.
For $k=2$ the smallest $n_{0}^{\prime}$, for which
$\alpha(K_{n,2})\geq|D_{x,y}^{\prime}|$ when $n\geq n_{0}^{\prime}$, is $7$,
which is by Proposition 2.1 also $n_{0}$ from Theorem 2.2 (that is,
$diss(K_{n,2})=\alpha(K_{n,2})$ as soon as $n\geq n_{0}=7$). This is not the
case for $k>2$. For $k=3$ one can easily compute that $n_{0}^{\prime}=17$ (by
solving inequality $\alpha(K_{n,k})\geq|D_{x,y}^{\prime}|$ for $k=3$), but as
we will see in Corollary 2.6, we have $diss(K_{n,3})=\alpha(K_{n,3})$ already
for $n\geq 8$. For $k>3$, we do not know how large must $n_{0}$ be in Theorem
2.2 and we propose this as an open problem.

###### Problem 1

Given an integer $k\geq 4$, what is the smallest integer $n_{0}$ such that for
all $n\geq n_{0}$, $diss(K_{n,k})=\alpha(K_{n,k})$?

From Proposition 1.1 we get the inequality that leads to the lower bound for
$n_{0}$ from Theorem 2.2.

###### Lemma 2.3

The smallest integer $n_{0}$ for which
$diss(K_{n_{0},k})=\alpha(K_{n_{0},k})$, is at least $2k+2$.

Proof.  Let $n\geq 2k$ and $diss(K_{n,k})=\alpha(K_{n,k})$. Then ${n-1\choose
k-1}\geq{2k\choose k}$ by Proposition 1.1. Solving this inequality we infer
$n\geq 2k+2$. $\square$

We follow with establishing the exact value of $diss(K_{8,3})$.

###### Lemma 2.4

$diss(K_{8,3})=\alpha(K_{8,3})$.

Proof.  For the purpose of contradiction assume that $diss(K_{8,3})>21$. Let
$S$ be a maximum dissociation set. Since $|S|>\alpha(K_{8,3})$, $S$ is not
independent. Without loss of generality we may assume that
$x=\\{1,2,3\\},y=\\{4,5,6\\}$ are two adjacent vertices contained in $S$.
Since $S$ is a dissociation set, $S\cap(N[x]\cup N[y])=\\{x,y\\}$. Let $H$ be
the subgraph of $K_{8,3}$ induced by $V(K_{8,3})\setminus(N[x]\cup N[y])$. We
define the following sets

  * •

$U=\\{z\in V(H);7\in z\\}$, $U^{\prime}=\\{z\in V(H);8\in z\\}$;

  * •

$\forall i\in[6]$, $U_{i}=\\{z\in U;i\in z\\}$, $U^{\prime}_{i}=\\{z\in
U^{\prime};i\in z\\}$;

  * •

$D=V(H)\setminus(U\cup U^{\prime})$;

  * •

$D^{\prime}=\\{z\in D;|z\cap x|=2\\}$, $D^{\prime\prime}=\\{z\in D;|z\cap
y|=2\\}$;

  * •

$\forall i,j\in[3],~{}D_{ij}^{\prime}=\\{z\in D^{\prime};i,j\in z\\}$;

  * •

$\forall i,j\in\\{4,5,6\\},~{}D_{ij}^{\prime\prime}=\\{z\in
D^{\prime\prime};i,j\in z\\}$;

  * •

$\forall i\in\\{4,5,6\\},~{}D_{i}^{\prime}=\\{z\in D^{\prime};i\in z\\}$;

  * •

$\forall i\in[3]$ $D_{i}^{\prime\prime}=\\{z\in D^{\prime\prime};i\in z\\}$.

If $z\in V(K_{8,3})$ with $\\{7,8\\}\subseteq z$, then $z\in N[x]\cup N[y]$.
Thus $U\cap U^{\prime}=\emptyset$, and so $[U,U^{\prime},D]$ is a partition of
$V(H)$. Also $[U_{1},U_{2},U_{3}]$ and $[U_{4},U_{5},U_{6}]$ are partitions of
$U$,
$[U_{1}^{\prime},U_{2}^{\prime},U_{3}^{\prime}],[U_{4}^{\prime},U_{5}^{\prime},U_{6}^{\prime}]$
are partitions of $U^{\prime}$,
$[D_{12}^{\prime},D_{13}^{\prime},D_{23}^{\prime}],[D_{4}^{\prime},D_{5}^{\prime},D_{6}^{\prime}]$
are partitions of $D^{\prime}$ and
$[D_{45}^{\prime\prime},D_{46}^{\prime\prime},D_{56}^{\prime\prime}],[D_{1}^{\prime\prime},D_{2}^{\prime\prime},D_{3}^{\prime\prime}]$
are partitions of $D^{\prime\prime}$. Moreover, sets
$U,U^{\prime},D^{\prime},D^{\prime\prime}$ are independent sets of cardinality
9. A spanning subgraph $H^{\prime}$ of a graph $H$ is depicted in Figure 1.
The edges of $H$ that are not in $H^{\prime}$ are the edges between $U$ and
$U^{\prime}$, between $U$ and $D^{\prime\prime}$, between $D^{\prime}$ and
$D^{\prime\prime}$. Note that $H[U\cup D^{\prime}]\cong H[U\cup
D^{\prime\prime}]\cong H[U^{\prime}\cup D^{\prime\prime}]$.

Figure 1: Spanning subgraph of a graph $H$.

###### Claim 1

$|U_{i}\cap S|<3$ for any $i\in\\{4,5,6\\}$.

Proof. Suppose that there exists $i\in\\{4,5,6\\}$ such that $|U_{i}\cap S|=3$
and let $\\{i,j,k\\}=\\{4,5,6\\}$. Hence $(U_{j}^{\prime}\cup
U_{k}^{\prime}\cup D_{jk}^{\prime\prime})\cap S=\emptyset$, as each vertex of
$U_{j}^{\prime}\cup U_{k}^{\prime}\cup D_{jk}^{\prime\prime}$ has exactly 2
neighbors in $U_{i}$. Let $\ell$ be an arbitrary element of $\\{1,2,3\\}$ and
let $\\{\ell,\ell^{\prime},\ell^{\prime\prime}\\}=\\{1,2,3\\}$. Since
$\\{\ell^{\prime},\ell^{\prime\prime},j\\},\\{\ell^{\prime},\ell^{\prime\prime},k\\}$
are both neighbors of $\\{l,i,7\\}\in U_{i}\subseteq S$,
$|\\{\\{\ell^{\prime},\ell^{\prime\prime},j\\},\\{\ell^{\prime},\ell^{\prime\prime},k\\}\\}\cap
S|\leq 1$. Note that subgraphs of $H$ induced by $U_{j}\cup
D_{ik}^{\prime\prime}$ and $U_{k}\cup D_{ij}^{\prime\prime}$ are isomorphic to
$C_{6}$ and thus $|(U_{j}\cup D_{ik}^{\prime\prime})\cap S|,|(U_{k}\cup
D_{ij}^{\prime\prime})\cap S|\leq 4$. If $|(U_{j}\cup
D_{ik}^{\prime\prime})\cap S|=4$, then $S$ contains exactly 2 vertices from
$U_{j}$ and thus it contains at most 2 verices from $U_{i}^{\prime}$ (as
$H[U_{j}\cup U_{i}^{\prime}]\cong C_{6}$). Therefore $|(U_{j}\cup
D_{ik}^{\prime\prime}\cup U_{i}^{\prime})\cap S|\leq 6$. Hence,

$|S\cap V(H)|=|S\cap U_{i}|+|S\cap(U_{j}^{\prime}\cup U_{k}^{\prime}\cup
D_{jk}^{\prime\prime})|+|S\cap(U_{j}\cup D_{ik}^{\prime\prime}\cup
U_{i}^{\prime})|+|S\cap(U_{k}\cup D_{ij}^{\prime\prime})|+|S\cap
D_{12}^{\prime}|+|S\cap D_{13}^{\prime}|+|S\cap D_{23}^{\prime}|\leq
3+0+6+4+2+2+2=19.$ We infer $|S|\leq 21$, a contradiction.  $(\square)$

Analogous arguments imply

###### Claim 2

For any $i\in\\{4,5,6\\}$ $|U_{i}^{\prime}\cap S|<3$.

###### Claim 3

For any $i\in[3]$ let $\\{i,j,k\\}=\\{1,2,3\\}$. Then $D_{jk}^{\prime}\cap
S\neq\emptyset$.

Proof. Suppose that there exists $i\in\\{1,2,3\\}$, such that
$|D_{jk}^{\prime}\cap S|=0$, where $\\{j,k\\}=\\{1,2,3\\}\setminus\\{i\\}$.
For $\ell\in\\{4,5,6\\}$ and
$\\{\ell^{\prime},\ell^{\prime\prime}\\}\in\\{4,5,6\\}\setminus\\{\ell\\}$ let
$A_{\ell}$ be the subgraph of $H$ induced by $U_{\ell}\cup
D_{\ell^{\prime}\ell^{\prime\prime}}^{\prime\prime}\cup U_{\ell^{\prime}}$.
Note that the subgraphs of $A_{\ell}$ induced by $U_{\ell}\cup
D_{\ell^{\prime}\ell^{\prime\prime}}^{\prime\prime}$ and by
$D_{\ell^{\prime}\ell^{\prime\prime}}^{\prime\prime}\cup U_{\ell^{\prime}}$
are isomorphic to $C_{6}$.

Suppose that $|A_{\ell}\cap S|>4$. Then
$D_{\ell^{\prime}\ell^{\prime\prime}}^{\prime\prime}\cap S\neq\emptyset$, as
$|U_{\ell}\cap S|\leq 2$ and $|U_{\ell}^{\prime}\cap S|\leq 2$ by Claims 1 and
2. Without loss of generality we may assume that
$\\{1,\ell^{\prime},\ell^{\prime\prime}\\}\in S\cap
D_{\ell^{\prime}\ell^{\prime\prime}}^{\prime\prime}$. Since
$\\{2,\ell,8\\},\\{3,\ell,8\\},\\{2,\ell,7\\},\\{3,\ell,7\\}$ are all
neighbors of $\\{1,\ell^{\prime},\ell^{\prime\prime}\\}\in S$, we get
$|\\{\\{2,\ell,8\\},\\{3,\ell,8\\},\\{2,\ell,7\\},\\{3,\ell,7\\}\\}\cap S|\leq
1$. Since $\\{1,\ell,8\\},\\{1,\ell,7\\}$ are both neighbors of
$\\{2,\ell^{\prime},\ell^{\prime\prime}\\}$ and
$\\{3,\ell^{\prime},\ell^{\prime\prime}\\}$, the following statements hold.

  * •

If
$\\{\\{2,\ell^{\prime},\ell^{\prime\prime}\\},\\{3,\ell^{\prime},\ell^{\prime\prime}\\}\\}\subseteq
S$, then $S\cap\\{\\{1,\ell,8\\},\\{1,\ell,7\\}\\}=\emptyset$;

  * •

If $|S\cap\\{\\{1,\ell,8\\},\\{1,\ell,7\\}\\}|=2$, then
$S\cap\\{\\{2,\ell^{\prime},\ell^{\prime\prime}\\},\\{3,\ell^{\prime},\ell^{\prime\prime}\\}\\}=\emptyset$.

Thus $S$ contains at most two vertices from
$\\{\\{2,\ell^{\prime},\ell^{\prime\prime}\\},\\{3,\ell^{\prime},\ell^{\prime\prime}\\},\\{1,\ell,8\\},\\{1,\ell,7\\}\\}$
and consequently $|A_{\ell}\cap S|\leq 4$, a contradiction. Hence
$|A_{\ell}\cap S|\leq 4$ for any $\ell\in\\{4,5,6\\}$. Since
$D_{jk}^{\prime}\cap S=\emptyset$, $|S\cap D^{\prime}|\leq 6$ and thus

$|V(H)\cap S|=\sum_{l=4}^{6}|A_{l}\cap S|+|D^{\prime}\cap S|\leq 3\cdot
4+6=18,$

a contradiction.  $(\square)$

For any $i\in[3]$ define $X_{i}^{\prime\prime}$ as a subgraph of $H$ induced
by vertices of $D_{i}^{\prime\prime}\cup U_{i}\cup U_{i}^{\prime}\cup
D_{jk}^{\prime}$, where $\\{j,k\\}=[3]\setminus\\{i\\}$.

Let $i\in[3]$ and $\\{i,j,k\\}=\\{1,2,3\\}$. Since by Claim 3
$D_{jk}^{\prime}\cap S\neq\emptyset$, we have three possibilities.

If $|D_{jk}^{\prime}\cap S|=1$. Let $\ell\in\\{4,5,6\\}$ such that
$\\{j,k,\ell\\}\in S$ and let
$\\{4,5,6\\}\setminus\\{\ell\\}=\\{\ell^{\prime},\ell^{\prime\prime}\\}$.
Since $\\{j,k,\ell\\}$ is adjacent to all vertices from
$A=\\{\\{i,\ell^{\prime},\ell^{\prime\prime}\\},\\{i,\ell^{\prime},7\\},\\{i,\ell^{\prime\prime},7\\},\\{i,\ell^{\prime},8\\},\\{i,\ell^{\prime\prime},8\\}\\}$,
$|S\cap A|\leq 1$. Since $|X_{i}^{\prime\prime}\setminus(A\cup
D_{jk}^{\prime})|=4$, $|S\cap A|\leq 1$ and $|S\cap D_{jk}^{\prime}|=1$ we get
$|S\cap V(X_{i}^{\prime\prime})|\leq 6$.

If $|D_{jk}^{\prime}\cap S|=2$, let $\ell,\ell^{\prime}\in\\{4,5,6\\}$ such
that $\\{j,k,\ell\\},\\{j,k,\ell^{\prime}\\}\in S$ and let
$\\{4,5,6\\}\setminus\\{\ell,\ell^{\prime}\\}=\\{\ell^{\prime\prime}\\}$.
Since $\\{i,\ell^{\prime\prime},7\\},\\{i,\ell^{\prime\prime},8\\}$ are
adjacent to both vertices from $D_{jk}^{\prime}\cap S$,
$\\{i,\ell^{\prime\prime},7\\},\\{i,\ell^{\prime\prime},8\\}\notin S$. Since
$A=\\{\\{i,\ell^{\prime},\ell^{\prime\prime}\\},\\{i,\ell^{\prime},7\\},\\{i,\ell^{\prime},8\\}\\}$
is the set of neighbors in $X_{i}^{\prime\prime}$ of $\\{j,k,\ell\\}\in
D_{jk}^{\prime}\cap S$, at most one vertex from $A$ can be contained in $S$.
Similarly at most one vertex from
$B=\\{\\{i,\ell,\ell^{\prime\prime}\\},\\{i,\ell,7\\},\\{i,\ell,8\\}\\}$ can
be contained in $S$, as all vertices of $B$ are neighbors of
$\\{j,k,\ell^{\prime}\\}$. Since $|X_{i}^{\prime\prime}-(A\cup B\cup
D_{jk}^{\prime})|=1$, $|S\cap V(X_{i}^{\prime\prime})|\leq|S\cap
D_{jk}^{\prime}|+|S\cap A|+|S\cap B|+1\leq 2+1+1+1=5$.

Finally, let $S\cap D_{jk}^{\prime}=D_{jk}^{\prime}$. Then $U_{i}\cap
S=U_{i}^{\prime}\cap S=\emptyset$ and thus $|V(X_{i}^{\prime\prime})\cap
S|\leq 6$.

We have proved that for any $i\in[3]$ it holds $|V(X_{i}^{\prime\prime})\cap
S|\leq 6$. Therefore

$|S\cap V(H)|=|S\cap V(X_{1}^{\prime\prime})|+|S\cap
V(X_{2}^{\prime\prime})|+|S\cap V(X_{3}^{\prime\prime})|\leq 18,$

which is a final contradiction. $\square$

###### Proposition 2.5

Let $n\geq 9$. If $diss(K_{n-1,3})=\alpha(K_{n-1,3})$ then
$diss(K_{n,3})=\alpha(K_{n,3}).$

Proof.  Suppose that there exists $n\geq 9$ with
$diss(K_{n-1,3})=\alpha(K_{n-1,3})$ and
$diss(K_{n,3})>\alpha(K_{n,3})={n-1\choose 2}$. Let $S$ be a maximum
dissociation set in $K_{n,3}$. Since $|S|>\alpha(K_{n,3})$, $S$ is not an
independent set. Note that since $n\geq 9$, $|S|\geq{n-1\choose 2}+1\geq 29$.
Without loss of generality we may assume that $x=\\{1,2,3\\},y=\\{4,5,6\\}\in
S$. Since $S$ is a dissociation set, $(S\cap(N[x]\cup
N[y]))\setminus\\{x,y\\}=\emptyset$. Let $H$ be the subgraph of $K_{n,3}$
induced by $V(K_{n,3})\setminus(N[x]\cup N[y]).$ Let $U=\\{z\in V(H);~{}n\in
z\\}$ and $D=\\{z\in V(H);~{}n\notin z\\}$. Since each vertex $z\in U$
contains exactly one element from $x$ and exactly one element from $y$,
$|U|=9$.

If $D\cap S=\emptyset$, then $|S|\leq 2+9=11$, a contradiction. Hence we may
assume that $D\cap S\neq\emptyset$. Let $z\in D\cap S$. Then at least one
element from $x$, say $i$, and at least one element from $y$, say $\ell$, is
contained in $z$. Denote $z=\\{i,\ell,w\\}$.

Suppose first that $w\notin x\cup y$. Let $\\{1,2,3\\}=\\{i,j,k\\}$,
$\\{4,5,6\\}=\\{\ell,\ell^{\prime},\ell^{\prime\prime}\\}$. Then all vertices
of
$A=\\{\\{j,\ell^{\prime},n\\},\\{j,\ell^{\prime\prime},n\\},\\{k,\ell^{\prime},n\\},\\{k,\ell^{\prime\prime},n\\}\\}\subseteq
U$ are neighbors of $z\in S$. Hence $|S\cap A|\leq 1$ and therefore $|S\cap
U|\leq 6.$ Since vertices of $N[x]\cup N[y]$ that do not contain $n$ together
with $D$ induce $K_{n-1,3}$, $|S|\leq\alpha(K_{n-1,3})+|U\cap
S|\leq{n-2\choose 2}+6$. Hence for any $n\geq 8$ we get
$|S|\leq\alpha(K_{n,3})$, a contradiction.

Hence $w\in x\cup y$, or, in other words, $S$ does not contain vertices
$\\{i,j,z\\}$, where $i\in\\{1,2,3\\},j\in\\{4,5,6\\},z\in\\{7,\ldots,n-1\\}$.
Thus if $d\in S\cap D$, then $d=\\{i_{1},i_{2},\ell\\}$ or
$d=\\{i,\ell_{1},\ell_{2}\\}$, where $i,i_{1},i_{2}\in\\{1,2,3\\}$,
$\ell,\ell_{1},\ell_{2}\in\\{4,5,6\\}$. Hence $|S\cap D|\leq 18$. If $S$
contains $\\{i_{1},i_{2},\ell\\}$ for $\\{i,i_{1},i_{2}\\}=\\{1,2,3\\}$,
$\\{\ell,\ell_{1},\ell_{2}\\}=\\{4,5,6\\}$, then $S$ cannot contain both
$\\{i,\ell_{1},n\\},\\{i,\ell_{2},n\\}\in U$ and thus $|S\cap(U\cup D)|\leq
26$. Therefore $|S|\leq 28$, a contradiction. $\square$

We suspect that Proposition 2.5 also holds for $k$ bigger than $3$, and pose
it as a problem.

###### Problem 2

Is it true that $diss(K_{n,k})=\alpha(K_{n,k})$ implies
$diss(K_{n+1,k})=\alpha(K_{n+1,k})$ for all $k\geq 2$ and $n\geq 2k+2$?

As a direct corollary of Lemma 2.3, Lemma 2.4 and Proposition 2.5 we get that
$diss(K_{n,3})=\alpha(K_{n,3})$ for any $n\geq 8$.

###### Corollary 2.6

For $k=3$, $diss(K_{n,k})=\alpha(K_{n,k})$ if and only if $n\geq 8$.

##  3 An upper bound for $diss(K_{n,k})$

In this section, we consider upper bounds for the dissociation number of
Kneser graphs $K_{n,k}$. We already know that $\alpha(K_{n,k})\leq
diss(K_{n,k})\leq 2\alpha(K_{n,k})$ and that if $n$ is large enough, then the
dissociation number coincide with the independence number. Thus the bound is
interesting only when $n<n_{0}$, where $n_{0}$ is the integer that appears in
Theorem 2.2 and Problem 1. Our aim of this section is to improve the upper
bound $2\alpha(K_{n,r})$ for $n<n_{0}$.

We will improve the upper bound by using Katona’s cyclic arrangement of
integers from his proof of Erdős-Ko-Rado theorem. Let $\cal D$ be a maximum
dissociation set of $K_{n,k}$. We count in two different ways the number of
ordered pairs $(D,C)$, where $D\in\cal D$ and $C$ is a cyclic arrangement of
integers from $[n]$ in which $D$ appears as a substring.

Let $n=2k+r$, thus we consider $K_{2k+r,k}$, where $r\geq 1$. If one takes any
set from $\cal D$, then it appears as a substring in $k!(n-k)!$ different
cyclic arrangements. Thus, altogether there are $|{\cal D}|k!(n-k)!$ such
ordered pairs $(D,C)$. Second, note that there are $(n-1)!$ different cyclic
arrangements of integers from $[n]$. Next, let us bound from above the number
of sets from $\cal D$ that appear as substrings in any given cyclic
arrangement.

We distinguish two cases. First, let $r>k-2$. We claim that in any given
cyclic arrangement there are at most $k+1$ elements from $\cal D$ that appear
as its substrings. Suppose that all elements of $\cal D$ that appear as
substring in $C$ pairwise intersect. Then, it is easy to see that at most $k$
elements from $\cal D$ appear as substrings in $C$. Without loss of
generality, let $D_{1}:1,2,\ldots,k$, and $D_{2}:k+t,k+t+1,2k+t-1$,
$t\in[n-2k+1]$, be the substrings in $C$ that correspond to elements of $\cal
D$. Since the sets that correspond to $D_{1}$ and $D_{2}$ form an edge in
$K_{n,r}$, we infer that all other sets of $\cal D$ that appear as substrings
in $C$ must intersect both $D_{1}$ and $D_{2}$. Since $r>k-2$, we infer that
there are at most $k-1$ such substrings of length $k$ that intersect both
$D_{1}$ and $D_{2}$. This implies that there are at most $k+1$ elements from
$\cal D$ that appear as substrings, as claimed. Thus, when $n>3k-2$, we get

$diss(K_{n,k})\leq\frac{k+1}{k}{n-1\choose k-1}\,.$ (1)

The second case is $r\leq k-2$. Again, let $D_{1}:1,2,\ldots,k$ be a substring
in a cyclic arrangement $C$ that corresponds to an element of $\cal D$ (by
abuse of language, we denote this element by $D_{1}$ as well). Clearly, there
is at most one set in $\cal D$ that does not intersect $D_{1}$. Note that a
set $D$ in ${\cal D}\setminus\\{D_{1}\\}$ can intersect $D_{1}$ in two
different ways, either $1\in D$ or $k\in D$. We denote by $A_{i}$ the
substring in $C$ for which $A_{i}\cap D_{1}=[i]$, and by $B_{i}$ the substring
in $C$ for which $B_{i}\cap D_{1}=[k]\setminus[i]$. If for some $i\in[n-1]$,
$A_{i}\in\cal D$ and $B_{i}\in\cal D$, then $i$ is a double point. On the
other hand, if just one of $A_{i}\in\cal D$ or $B_{i}\in\cal D$ holds, then
$i$ is a single point. Let $d$ be the number of double points and $s$ the
number of single points. Note that the number of substrings of $C$ that
correspond to elements of $\cal D$ is bounded from above by $2+s+2d$, where 2
coresponds to $D_{1}$ and possibly one more element from $\cal D$ that does
not intersect $D_{1}$.

Suppose that $i$ is a double point. Since $\cal D$ is a dissociation set, any
set in ${\cal D}\setminus\\{A_{i},B_{i}\\}$ must intersect both $A_{i}$ and
$B_{i}$. This in turn implies that $A_{i-1},\ldots,A_{\max\\{i-r,1\\}}$ do not
belong to $\cal D$ and also $B_{i+1},\ldots,B_{\max\\{i+r,k\\}}$ do not belong
to $\cal D$. In other words, a double point can appear at most in every $2r+1$
turn, that is, at most $\lceil\frac{k}{2r+1}\rceil$ times. Hence, the number
of substrings of $C$ that correspond to elements of $\cal D$ is bounded from
above by $2+s+2d=2+k-1+\lceil\frac{k}{2r+1}\rceil\leq 2+k+\frac{k}{2r+1}$.
This yields

$|{\cal D}|(n-k)!k!\leq(2+k+\frac{k}{2r+1})(n-1)!\,$

which implies

$diss(K_{2k+r,k})\leq 2\frac{rk+2r+k+1}{k(2r+1)}{n-1\choose k-1}\,.$ (2)

##  4 Dissociation number of odd graphs

In this section, we use the famous Hall’s marriage theorem, which we next
formulate. Let $G$ is a bipartite graph, where a bipartition of $V(G)$ is
$[X,Y]$. A matching $M$ in $G$ is an $X$-matching of $G$ if every vertex in
$X$ is incident with an edge of $M$.

###### Theorem 4.1

[10] A bipartite graph $G$ with $V(G)=[X,Y]$ has an $X$-matching if and only
if for every subset $W\subset X$ we have $|N(W)|\geq|W|$.

Perhaps the most interesting class of Kneser graphs is that of odd graphs,
$O_{k}=K_{2k+1,k}$. The dissociation number of odd graph $O_{k}$ is by
Proposition 1.1 bounded below by ${2k\choose k}$. Proposition 2.1 implies that
this bound is also an upper bound for $k=2$. In the next result we prove that
the bound is the exact value also for $k>2$.

###### Theorem 4.2

For any $k\geq 2$, $diss(O_{k})={2k\choose k}$.

Proof.  By Proposition 1.1, $diss(O_{k})\geq{2k\choose k}$.

Let $S$ be a maximum dissociation set of $O_{k}$. Let $D=\\{x\in
V(O_{k});2k+1\notin x\\}$ and $U=V(O_{k})\setminus D$, that is, $U=\\{x\in
V(O_{k});2k+1\in x\\}$. Note that $O_{k}[D]$ is isomorphic to $K_{2k,k}$ which
is in turn isomorphic to $\frac{1}{2}{2k\choose k}K_{2}$. On the other hand,
$U$ is a center $I(2k+1)$ of $K_{2k+1,k}$, hence an independent set.

If $S\cap D=\emptyset$, then $|S|\leq|U|={2k\choose k-1}\leq{2k\choose k}$ and
the proof is done. If $S\cap U=\emptyset$, then $|S|\leq|D|={2k\choose k}$
which also completes the proof. Thus it remains to consider the case when
$D\cap S\neq\emptyset$ and $L=U\cap S\neq\emptyset$. Set $\ell=|L|$. Since
$|D|={2k\choose k}$ and $|S\cap U|=\ell$, it suffices to prove that at least
$\ell$ vertices from $D$ are not contained in $S$.

Let $E$ be the set of edges having one endvertex in $L$ and the other
endvertex in $N_{O_{k}}(L)$, where $N_{O_{k}}(L)$ is a subset of $D$. Now,
$|E|=(k+1)|L|$, since any $u\in L$ has exactly $k+1$ neighbors in $D$. On the
other hand, any $x\in N_{O_{k}}(L)$ has exactly $k$ neighbors in $U$ and hence
$|E|\leq k|N_{O_{k}}(L)|$. Therefore $|N_{O_{k}}(L)|\geq\frac{k+1}{k}|L|>|L|$.
The same argument applies for any subset of $L$; that is, if
$L^{\prime}\subset L$, then
$|N_{O_{k}}(L^{\prime})|\geq\frac{k+1}{k}|L^{\prime}|>|L^{\prime}|$. Thus, by
Theorem 4.1, there is an $L$-matching
$M=\\{u_{1}x_{1},u_{2}x_{2},\ldots,u_{\ell}x_{\ell}\\}$ in a bipartite graph
$G=(L\cup N_{O_{k}}(L),E)$, where $u_{i}\in L$ and $x_{i}\in N_{O_{k}}(L)$ for
any $i\in[\ell]$. Let $[M^{\prime},M^{\prime\prime}]$ be a partition of $M$,
where $M^{\prime}$ is the set of edges in $M$ with both endvertices contained
in $S$. Since $L\subseteq S$, exactly one endvertex of each edge in
$M^{\prime\prime}$ (that is, the endvertex from $L$) is contained in $S$.
Denote by $Z$ (resp. $A^{\prime}$) the set of endvertices in $L$ (resp.
$N_{O_{k}}(L)$) of edges in $M^{\prime}$ and let $W$ (resp. $B^{\prime}$) be
the set of endvertices of edges in $M^{\prime\prime}$ that are contained in
$L$ (resp. $N_{O_{k}}(L)$). Furthermore, let
$A^{\prime\prime}=(N_{O_{k}}(L)\cap S)\setminus A^{\prime}$ and
$B^{\prime\prime}=(N_{O_{k}}(L)\setminus S)\setminus B^{\prime}$. This
definitions directly imply that
$[A^{\prime},A^{\prime\prime},B^{\prime},B^{\prime\prime}]$ is a partition of
$N_{O_{k}}(L)$. Note that $A^{\prime}\cup A^{\prime\prime}$ consists exactly
of the vertices of $N_{O_{k}}(L)$ that are contained in $S$, and
$B^{\prime}\cup B^{\prime\prime}$ contains the vertices from $N_{O_{k}}(L)$
not contained in $S$.

To complete the proof, we count the number of edges between $L$ and
$B^{\prime}\cup B^{\prime\prime}$. Denote the set of those edges by
$E^{\prime}$. Since $Z\cup A^{\prime}\cup A^{\prime\prime}$ is a subset of a
dissociation set $S$ and $u_{i}x_{i}\in M$ is an edge in $O_{k}[S]$, $x_{i}$
is the only neighbor of $u_{i}\in Z$ that is contained in $S$. Hence all other
$k$ neighbors of $u_{i}$ in $D$ are from $B^{\prime}\cup B^{\prime\prime}$.
Since $W\cup A^{\prime}\cup A^{\prime\prime}\subseteq S$, any vertex $u_{i}\in
W$ has at most one neighbor in $A^{\prime\prime}$ and all other $k$ neighbors
of $u_{i}$ in $D$ are from $B^{\prime}\cup B^{\prime\prime}$. Thus
$|E^{\prime}|\geq k(|Z|+|W|)=k|L|$. Since each vertex $x\in B^{\prime}\cup
B^{\prime\prime}$ has exactly $k$ neighbors in $U$ and as $L$ is a subset of
$U$, we get $|E^{\prime}|\leq k(|B^{\prime}|+|B^{\prime\prime}|)$.
Consequently $|B^{\prime}|+|B^{\prime\prime}|\geq|L|$. Hence $B^{\prime}\cup
B^{\prime\prime}\subseteq D\setminus S$ is a set of at least $\ell$ vertices
in $D$ that are not contained in $S.$ $\square$

##  5 Concluding remarks

In this paper, we found the dissociation number of several families of Kneser
graphs $K_{n,k}$. This includes the cases $k\in\\{2,3\\}$ and $n=2k+1$. As
proved in Theorem 2.2, when $n$ is large enough with respect to $k$, then the
dissociation number equals the independence number of the corresponding Kneser
graph. The point when this happens for a given $k$, the integer $n_{0}$, is
open, and we give a lower bound for it. Two problems posed in Section 2 are
related to $n_{0}$. Establishing exact values of $diss(K_{2k+r,k})$, where $r$
is a small integer greater than $1$, is another challenge.

The dissociation number is dual invariant to the $3$-path vertex cover number
(as is the independence number dual to the ($2$-path) vertex cover number). A
natural problem is to consider the $m$-path vertex cover number of Kneser
graphs, for any given $m>3$. An alternative extension of the problem studied
in this paper is the following. Since a dissociation set induces a subgraph
with maximum degree at most $1$, it would be interesting to find the largest
size of a subset of vertices in $K_{n,k}$ that induces a subgraph with maximum
degree $\Delta$, for any given $\Delta\geq 2$.

## Acknowledgements

B.B. and T.D. acknowledge the financial support from the Slovenian Research
Agency (research core funding No. P1-0297 and project grants No. J$1$-$9109$
and N$1$-$0095$).

## References

  * [1] R. Boliac, K. Cameron, V.V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241–253.
  * [2] C. Brause, I. Schiermeyer, Kernelization of the 3-path vertex cover problem. Discrete Math. 339 (2016) 1935–1939.
  * [3] B. Brešar, B.L. Hartnell, D.F. Rall, Uniformly dissociated graphs, Ars Math. Contemp. 13 (2017) 293–306.
  * [4] B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin, A. Taranenko, On the vertex $k$-path cover, Discrete Appl. Math. 161 (2013) 1943–1949.
  * [5] B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math. 159 (2011) 1189–1195.
  * [6] B. Brešar, R. Krivoš-Belluš, G. Semanišin, P. Šparl, On the weighted k-path vertex cover problem, Discrete Appl. Math. 177 (2014) 14–18.
  * [7] Y. Chen, Triangle-free Hamiltonian Kneser graphs, J. Combin. Theory (B) 89 (2003) 1–16.
  * [8] P. Erdős, C. Ko, R. Rado, Intersection theorem for system of finite sets, Quart. J. Math. 12 (1961) 313–318.
  * [9] L.N. Grippo, A. Pastine, P. Torres, M. Valencia-Pabon, J.C. Vera, On the $P_{3}$-Hull Number of Kneser Graphs, Electron. J. Combin. 28 (2021) P3.32, 9 pp.
  * [10] P. Hall, On Representatives of Subsets, J. London Math. Soc. 10 (1935) 26–30.
  * [11] C. Hartman, D.B. West, Covering designs and domination in Kneser graphs; unpublished manuscript, 2003.
  * [12] J. Ivančo, B. Zelinka, Domination in Kneser graphs, Math. Bohem. 118 (1993) 147–152.
  * [13] M. Jakovac, A. Taranenko, On the $k$-path vertex cover of some graph products, Discrete Math. 313 (2013) 94–100.
  * [14] F. Kardoš, J. Katrenič, I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci. 412 (2011) 7009–7017.
  * [15] G.O.H. Katona, A simple proof of the Erdős-Chao Ko-Rado theorem, J. Combin. Theory (B) 13 (1972) 183–184.
  * [16] Y. Li, Z. Yang, W. Wang, Complexity and algorithms for the connected vertex cover problem in 4-regular graphs, Appl. Math. Comput. 301 (2017) 107–114.
  * [17] L. Lovász, Kneser’s Conjecture, Chromatic Numbers and Homotopy, J. Combin. Theory (A) 25 (1978) 319–324.
  * [18] J. Matoušek, A Combinatorial Proof of Kneser’s Conjecture, Combinatorica 24 (2004) 163–170.
  * [19] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (2011) 1352–1366.
  * [20] P. R. J. Östergård, Z. Shao, X. Xu, Bounds on the Domination Number of Kneser Graphs, Ars Math. Contemp. 9 (2015) 197–205.
  * [21] C.H. Papadimitriou, M. Yannakakis, The complexity of restricted spanning tree problems, J. Assoc. Comput. Mach. 29 (1982) 285–309.
  * [22] I.B. Shields, Hamilton cycle heuristics in hard graphs, North Carolina State University, 2004.
  * [23] M. Valencia-Pabon, J.C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383–385.


# Observation of nonlocal Josephson effect on double InAs nanowires

Sadashige Matsuo<EMAIL_ADDRESS>Center for Emergent Matter
Science, RIKEN, 2-1 Hirosawa, Wako-shi, Saitama 351-0198, Japan  JST, PRESTO,
4-1-8 Honcho, Kawaguchi, Saitama 332-0012, Japan  Joon Sue Lee  California
NanoSystems Institute, University of California, Santa Barbara, CA 93106, USA
Department of Physics and Astronomy, University of Tennessee, Knoxville,
Tennessee 37996, USA  Chien-Yuan Chang  Center for Emergent Matter Science,
RIKEN, 2-1 Hirosawa, Wako-shi, Saitama 351-0198, Japan  Yosuke Sato  Center
for Emergent Matter Science, RIKEN, 2-1 Hirosawa, Wako-shi, Saitama 351-0198,
Japan  Department of Applied Physics, University of Tokyo, 7-3-1 Hongo,
Bunkyo-ku, Tokyo 113-8656, Japan  Kento Ueda  Department of Applied Physics,
University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
Christopher J. Palmstrøm  California NanoSystems Institute, University of
California, Santa Barbara, CA 93106, USA  Electrical and Computer Engineering,
University of California, Santa Barbara, CA 93106 USA  Materials Department,
University of California, Santa Barbara, CA 93106, USA  Seigo Tarucha
<EMAIL_ADDRESS>Center for Emergent Matter Science, RIKEN, 2-1 Hirosawa,
Wako-shi, Saitama 351-0198, Japan  Department of Physics, Tokyo University of
Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan

###### Abstract

Short-range coherent coupling of two Josephson junctions (JJs) are predicted
to generate a supercurrent in one JJ nonlocally modulated by the phase
difference in the other. We report on observation of the nonlocal Josephson
effect on double InAs nanowires as experimental evidence of the coherent
coupling. We measured one JJ sharing one superconducting electrode with the
other JJ and observed switching current oscillation as a control of the
nonlocal phase difference. Our result is an important step toward engineering
of novel superconducting phenomena with the short-range coherent coupling.

The development of Josephson junction (JJ) physics Josephson (1962) is of
significance for exploiting novel coherent macroscopic quantum phenomena and
superconducting (SC) device applications in various quantum information
technologies Krantz  _et al._ (2019). In particular, coherent coupling between
two JJs is the key for SC circuit designs to engineer qubit-qubit couplings
and realise a novel SC phase in multiple JJ arrays. Recently, the Andreev
molecular state (AMS), a new concept for producing short-range coherent
coupling between two JJs on nanowires has been introduced Pillet  _et al._
(2019); Kornich  _et al._ (2019, 2020). In the two adjacent JJs, upper (JJU)
and lower (JJL), on the nanowires sharing one SC electrode, as described in
Fig. 1(a), the respective Andreev bound states (ABSs) Furusaki and Tsukada
(1991); Beenakker and van Houten (1991) are hybridised because of the
penetration of the ABS wave functions into the shared SC electrode, forming an
AMS as the bonding and anti-bonding states. ABSs have been utilised for the
Andreev qubit Chtchelkatchev and Nazarov (2003); Zazunov  _et al._ (2003);
Janvier  _et al._ (2015), and AMS physics holds the possibility of producing
short-range coherent coupling between qubits. In such a device, the ABS energy
and supercurrent in JJU depend on not only $\delta_{U}$, the phase difference
on JJU, but also on the ABS energy and the phase difference, $\delta_{L}$, of
JJL. Consequently, the supercurrent in JJU can be controlled nonlocally by
manipulation of JJL, which is referred to as the nonlocal Josephson effect
Pillet  _et al._ (2019). The AMS has been observed in a double dot coupled
with SCs Kurtossy  _et al._ ; however, experimental studies of superconducting
transport related to the AMS, such as the nonlocal Josephson effect, have not
been reported.

When two nanowires are coherently coupled through an SC electrode, the
coupling forms a nonlocal SC correlation on the double nanowire. Such nonlocal
SC correlation is an essential ingredient for engineering time-reversal
invariant topological SCs and can be applied in topological quantum computing
with Majorana fermions or parafermions in SC-semiconductor hybrid systems
Klinovaja and Loss (2014); Gaidamauskas  _et al._ (2014); Haim  _et al._
(2014). The nonlocal SC correlation on double nanowires has been addressed in
electrically tunable devices Baba  _et al._ (2018); Ueda  _et al._ (2019);
Kurtossy  _et al._ . Experimental study of the nonlocal Josephson effect is an
important step to address the phase control of the nonlocal SC correlation; it
paves the way for realising time-reversal invariant topological SC devices.

Figure 1: Concept of this study and device structure. (a) AMS formation is
shown. The ABSs of JJU and JJL penetrate the SC electrodes, as illustrated in
the middle panel. When the separation of the two JJs is short, the ABSs in the
respective nanowires are hybridised to form an AMS. (b) SEM image of the
3-terminal JJ on a double nanowire. The two JJs share the left SC electrode,
but on the right side, the two SC electrodes were placed on the respective
nanowires. (c) SEM image of sample B. The shared and lower SC electrodes in
(b) are connected by a superconductor loop.

Considering that multiple phase differences dominate the junction properties,
the coupled JJs in Fig. 1(a) resemble multiterminal JJs Freyn  _et al._
(2011); Pfeffer  _et al._ (2014); Feinberg  _et al._ (2015); Strambini  _et
al._ (2016); Cohen  _et al._ (2018); Draelos  _et al._ (2019); Pankratova  _et
al._ (2020); Graziano  _et al._ (2020), providing a platform for topological
physics van Heck  _et al._ (2014); Yokoyama and Nazarov (2015); Riwar  _et
al._ (2016); Xie  _et al._ (2017). In this sense, establishing the physics of
the coupling between JJs will also help to develop multiterminal JJ physics,
as studies on not only devices of a single normal conductor with multiple SC
electrodes but also those of two or more coupled JJs on various independently
controllable materials may be conducted.

Here, we report experimental evidence of the nonlocal Josephson effect using
gate-tunable InAs nanowires to demonstrate the coherent coupling between two
JJs on a double nanowire. Our results provide a means to nonlocally control
the D.C. Josephson effect. Our strategy for this demonstration is to determine
whether the SC correlation between any two SC electrodes exists and then
measure the switching current in JJU dependent on $\delta_{L}$.

We prepared two coupled JJ devices, named samples A and B. We chose an InAs
double-nanowire structure, created using the selective area growth (SAG)
method as this method allows the preparation of two spatially separated
parallel nanowires with high yield compared to using self-assembled nanowires
Baba  _et al._ (2017, 2018); Ueda  _et al._ (2019). Additionally, aluminium is
epitaxially grown on InAs nanowires, which provides a highly transparent
interface Krogstrup  _et al._ (2015). The two SAG nanowires were spatially
separated by 60 nm. JJU and JJL were formed on InAs nanowires U and L,
respectively. The SC electrode on the left side is shared by the two JJs, but
the two right SC electrodes contact nanowire U and nanowire L separately.
Sample A was fabricated into a 3-terminal JJ device (left shared SC, right
upper SC, and right lower SC electrodes) on nanowires U and L. A scanning
electron microscope (SEM) image of the same structure is shown in Fig. 1(b).
For sample B, JJL is embedded in an SC loop to change $\delta_{L}$ by a
magnetic field ($B$) penetrating the SC loop. The two gate electrodes were
used to electrically control JJU and JJL with gate voltages of $V_{\rm gU}$
and $V_{\rm gL}$, respectively. The SEM image of sample B is shown in Fig.
1(c). The junction of sample B has the same structure as that of sample A, but
the shared and lower SC electrodes are connected to an SC loop. Sample A was
used to confirm the SC correlation between any two SC electrodes and sample B
to demonstrate the nonlocal control of the D.C. Josephson effect.

First, we measured sample A at 10 mK to study the correlation between the SC
electrodes. For this purpose, we simultaneously measured $V_{\rm U}$ and
$V_{\rm L}$, the voltages of the upper and lower SC electrodes with the shared
SC grounded by sweeping the bias currents $I_{\rm U}$ and $I_{\rm L}$ through
JJU and JJL, respectively (see Fig. 2(a)). Figs. 2(b) and (c) show the
measured differential resistances $dV_{\rm U}/dI_{\rm U}$ and $dV_{\rm
L}/dI_{\rm L}$ as functions of $I_{\rm U}$ and $I_{\rm L}$, respectively. In
the square region of -30 nA$<I_{\rm U}<30$ nA and -60 nA$<I_{\rm L}<60$ nA,
$dV_{\rm U}/dI_{\rm U}$ and $dV_{\rm L}/dI_{\rm L}$ almost vanish in both
figures, indicating that the supercurrent flows between the upper and the
shared SC and between the lower and the shared SC. This means that the
switching current is almost 30 nA for JJU and 60 nA for JJL.

Figure 2: 3 terminal measurement of the two coupled Josephson junctions on the
double nanowire. (a) shows a schematic of the electrical circuit used for
measurement of sample A. (b) and (c) show the differential resistances of JJU
and JJL, respectively, as a function of $I_{\rm U}$ and $I_{\rm L}$, measured
simultaneously. The supercurrent flows in both JJs in the central blue regions
of -30 nA $<I_{\rm U}<30$ nA and -60 nA $<I_{\rm L}<60$ nA. In the regions
arranged with ${\rm SC_{US}}$, ${\rm SC_{LS}}$, and ${\rm SC_{UL}}$ extending
outward from the central blue supercurrent region, the local supercurrent
remains between a pair of the two SC electrodes with the dissipative current
in the other pairs.

From the supercurrent region, the three additional regions where the
differential resistance is reduced are extended, as labelled with ${\rm
SC_{US},SC_{LS},andSC_{UL}}$ in Figs. 2(b) and (c). These diagonal features
have also been reported in multiterminal Josephson junctions Draelos  _et al._
(2019); Pankratova  _et al._ (2020); Graziano  _et al._ (2020). In these
regions, the supercurrent flowing between any two contacts remains within
these contacts, whereas the dissipative current flows between the other
contacts. For example, in ${\rm SC_{US}}$, there is considerable reduction, as
seen in Fig. 2(b), but not in Fig. 2(c). In addition, ${\rm SC_{US}}$ is
strongly dependent on $I_{\rm U}$ but is slightly sensitive to $I_{\rm L}$.
This means that the supercurrent between the upper and shared SC electrodes
remains in ${\rm SC_{US}}$ with the dissipative current at JJL because
$|I_{\rm L}|>60$ nA. For similar reasons, ${\rm SC_{LS}}$ can be assigned to
the region where the supercurrent between the lower and shared SC electrodes
remains.

As for ${\rm SC_{US}}$ and ${\rm SC_{LS}}$ regions, the figures indicate that
the differential resistance in the remained supercurrent regions is finite.
For example $dV_{\rm U}/dI_{\rm U}$ in ${\rm SC_{US}}$ is around 300 Ohm at
$I_{\rm L}\sim\pm 400$ nA (see supplemental material (SM)). This can be
assigned to the Joule heating effect derived from the normal transport in JJL.
The heating increases the electron temperature in JJU, resulting in the phase
diffusion which produces the finite differential resistance even in the
supercurrent region Ambegaokar and Halperin (1969). Additionally, ${\rm
SC_{US}}$ and ${\rm SC_{LS}}$ have finite tilts on the $V_{\rm U}V_{\rm L}$
plane. These tilts can be derived from the cotunneling of the quasiparticles.
For example, when a finite potential difference on JJU is present, the current
in JJU flows from the upper SC to the shared SC. Additionally, due to the
cotunneling through the shared SC, the finite current also flows to the lower
SC. This cotunneling current generates the finite tilt of ${\rm SC_{LS}}$.

We focus on the diagonal feature ${\rm SC_{UL}}$ in which both $dV_{\rm
U}/dI_{\rm U}$ and $dV_{\rm L}/dI_{\rm L}$ are slightly reduced, as shown in
Figs. 2(b) and (c). A supercurrent can exist in three pairs of upper, lower,
and shared SC electrodes. The supercurrent in the upper and shared SC pair is
assigned to ${\rm SC_{US}}$, and that in the lower and shared SC pair is
assigned to ${\rm SC_{LS}}$. Therefore, ${\rm SC_{UL}}$ can be assigned to the
supercurrent between the upper and lower SC electrodes. This result indicates
that a nontrivial SC correlation exists between the upper and lower SC
electrodes, although the shared SC electrode only intermediates two nanowires;
no other material connects the two SC electrodes. This is a signature of the
nonlocal SC correlation between the two Josephson junctions. However, the
${\rm SC_{UL}}$ signal is small and vague because the dissipative current and
nonequilibrium quasiparticles coexist with the supercurrent. Therefore, a
detailed discussion of the nonlocal SC correlation from these 3-terminal
results is difficult.

Figure 3: Switching current oscillation indicating a coherent coupling between
two Josephson junctions. (a) shows a schematic of the measurement circuit for
sample B . (b) illustrates the $I_{\rm U}-V_{\rm U}$ curves obtained at
several $V_{\rm gU}$ points, indicating that the supercurrent in JJU can be
tuned by $V_{\rm gU}$ locally. (c) indicates $V_{\rm U}$ vs. $I_{\rm U}$ at
$B=1.9$ mT and several $V_{\rm gL}$. The supercurrent in JJU is little
controllable by $V_{\rm gL}$. (d) shows $V_{\rm U}$ as a function of $I_{\rm
U}$ and $B$. The boundary between the red and blue regions corresponds to the
switching current in JJU as a function of $B$. The image clearly indicates the
oscillation of the switching current in the JJU.

Then, we use another strategy to control the phase difference $\delta_{L}$ in
sample B. We measured $V_{\rm U}$ by changing $I_{\rm U}$ and $B$ at several
$V_{\rm gU}$ and $V_{\rm gL}$, the gate voltages on JJU and JJL respectively
(see Fig. 3(a)). Fig. 3(b) represents $V_{\rm U}$ vs. $I_{\rm U}$ at $B=0$ mT
and several $V_{\rm gU}$. At $I_{\rm U}=105$ nA for $V_{\rm gU}=0$ V, the
supercurrent region is switched to the normal region. The switching current
$I_{\rm sw}$ decreases as $V_{\rm gU}$ decreases, indicating that JJU can be
controlled electrically. $V_{\rm gU}=-5$ V provides about half of $I_{\rm sw}$
at $V_{\rm gU}=0$ V. Figure 3(c) indicates $V_{\rm U}$ vs. $I_{\rm U}$ at
$B=1.9$ mT and several $V_{\rm gL}$. $V_{\rm gL}=-4.4$ V provides about 0.9 of
$I_{\rm sw}$ at $V_{\rm gL}=0$ V, meaning that $I_{\rm sw}$ of JJU depends
weakly on $V_{\rm gL}$ in the present range.

We measured $V_{\rm U}$ vs. $I_{\rm U}$ at various magnetic field strengths.
The obtained values of $V_{\rm U}$ as a function of $I_{\rm U}$ and $B$ are
shown in Fig. 3(d). As illustrated, the switching current around 100 nA,
corresponding to the boundary between the blue and red regions, oscillates
with $B$. The oscillation period is 0.22 mT, which reasonably agrees with the
calculated value of 0.30 mT, derived from the superconducting loop area (6.88
${\rm\mu m^{2}}$). The magnetic field changes only $\delta_{L}$ and the phase
difference of JJL in the SC loop. Therefore, $B$ would not affect the $I_{\rm
sw}$ of JJU if there were no nonlocal SC correlation between JJU and JJL. The
obtained switching current oscillation was reproduced in different devices on
a single or double nanowire (see SM). Furthermore, we confirmed that this
oscillation disappeared as the distance between the two junctions increased,
as expected from the theory that the distance should be shorter than the
coherence length of SC to form the coupling. Disappearance of the oscillation
with the long distance implies that the single JJ on the single nanowire
produces no oscillation of the switching current (see SM). Consequently, we
present the observation of the nonlocal Josephson effect derived from the
coupling between JJU and JJL through the shared SC electrode. Additionally,
our observation of JJU switching current in sample B proves coherence of the
coupling because the nonlocal phase modulation is observed on the supercurrent
which is one of the phase coherent phenomena.

To clarify that the $I_{\rm sw}$ oscillation originates not only from the JJU,
but also from the properties of JJL, we studied the gate voltage control of
the nonlocal Josephson effect signal. We evaluated the peak-to-peak value and
the average of $I_{\rm sw}$ vs. $B$ at the respective gate voltages. First, we
indicate the $V_{\rm gU}$ dependence of $I_{\rm sw}$ vs. $B$ with $V_{\rm
gL}=0$ V, indicating local gate control. Both the peak-to-peak value and the
average of $I_{\rm sw}$ change with $V_{\rm gU}$, as shown in Fig. 4(a). Then,
we move onto the $V_{\rm gL}$ dependence with $V_{\rm gU}=0$ V; this refers to
nonlocal gate control. As shown in Fig. 4(b), the average of $I_{\rm sw}$ is
almost constant, whereas the peak-to-peak value decreases as $V_{\rm gL}$
decreases (see SM). This indicates that the average is affected only by the
local gate voltage; the oscillation is affected by both the local and nonlocal
gate voltages. Therefore, the oscillation originates from the coherent
coupling between the two JJs.

Figure 4: Local and nonlocal gate control of the switching current oscillation
in JJU. (a) and (b) show the peak-to-peak value in red and the average in blue
of the switching current in JJU as a function of $V_{\rm gU}$ and $V_{\rm
gL}$, respectively. In the local gate control case in (a), both the amplitude
and average change with $V_{\rm gU}$. However, only the peak-to-peak value
largely varies in the non-local gate control case in (b). This means that the
switching current oscillation is derived from the hybridisation between JJU
and JJL.

Finally, we discuss the microscopic origin of the observed coherent coupling
between JJU and JJL. In the literature, the coupling in the ballistic
junctions is dominantly formed by the double elastic cotunneling through the
shared SC. The observed tilt of ${\rm SC_{LS}}$ in Fig. 2 provides a ratio of
the cotunneling current to the current in JJU as around $0.14$. This value is
similar to a ratio of the peak to peak value to the average of $I_{\rm sw}$
found in Fig. 4. Therefore, the similarity between the cotunneling ratio and
the oscillation ratio seems to imply that the coherent coupling in our devices
is dominantly originated from the cotunneling process as theoretically
expected in the ballistic JJs.

Although our experiments clearly provide evidence of existence of the nonlocal
Josephson effect, we only addressed the nonlocal control of the switching
current. In order to unveil the local and nonlocal transport on the coupled
JJs, it is significant to evaluate the current phase relation, which gives the
supercurrent as a function of local and nonlocal phase differences. In
addition, microscopic mechanism to produce the coherent coupling should be
revealed experimentally. Further studies on the coupled JJs are necessary.

In summary, we confirmed the nonlocal superconducting correlation between two
JJs in a 3-terminal device and observed the nonlocal Josephson effect in a
double JJ device with a superconducting loop. These demonstrated that the
short-range coherent coupling between the two different Josephson junctions
can be formed through a superconductor. The observed coherent coupling is not
just for the semiconductor-superconductor junctions but expected in various
kinds of Josephson junctions coupled through superconductors. Our results pave
the way to engineering short-range coherent coupling between superconducting
qubits, such as the Andreev qubit Chtchelkatchev and Nazarov (2003); Zazunov
_et al._ (2003); Janvier  _et al._ (2015), and provide a new building block
for designing novel SC devices consisting of the two JJs on the different
materials.

## Acknowledgments

We thank P. Stano, C.-H. Hsu, Y. Tanaka, and S. Nakosai for fruitful
discussions Funding: This work was partially supported by a JSPS Grant-in-Aid
for Scientific Research (S) (Grant No. JP19H05610); JST PRESTO (grant no.
JPMJPR18L8); Advanced Technology Institute Research Grants; Ozawa-Yoshikawa
Memorial Electronics Research Foundation; the US Department of Energy under
Award No. DE-SC0019274.

## Supplementary Information

### Supplementary Note 1: Normal transport in sample B

Before starting the condensation and circulation of the dilution fridge, we
measured sample B at 4 K. At this temperature, aluminium is not
superconductive, and we can examine the normal transport properties of sample
B. Figure S1 (a) shows the conductance $G$ in units of $2e^{2}/h$ as a
function of $V_{\rm gL}$ and $V_{\rm gU}$. The line profiles are shown in Fig.
S1 (b). The normal transport result has a small cross-capacitance effect
between the upper and lower gate electrodes. This cross-capacitance effect can
cause $V_{\rm gL}$ to change the carrier density of the nanowire U, which
results in a small change in the average of $I_{\rm sw}$ as a function of
$V_{\rm gL}$, as shown in Fig. 4 (b). In addition, we studied the resistance
as a function of the magnetic field at 4 K, as shown in Fig. S1 (c). The
result includes a small fluctuation but no clear periodic oscillation, like
that seen in the switching current measurement shown in Fig. 3 (c). Then, the
switching current oscillation obtained at the base temperature of our dilution
fridge can be assigned to the hybridization of the ABSs in the two JJs, not to
the normal state properties.

### Supplementary Note 2: Reproducibility in sample C

We measured other selective area growth (SAG) double-nanowire devices with the
same structure as sample B (two Josephson junctions on the double nanowire,
one of which is embedded in a superconducting loop). We named this device
sample C and repeated the measurements. Figure S2 represents $V_{\rm U}$ as a
function of $I_{\rm U}$ and $B$ in sample C. An oscillating switching current
similar to that in Fig. 3(c) was observed, as shown in Fig. S2. This result
indicates the reproducibility of the result obtained for sample B.

### Supplementary Note 3: Nonlocal Josephson effect on a single nanowire

To study the nonlocal Josephson effect through the proximitized region, we
fabricated a double JJ device on a SAG InAs single nanowire. The scanning
electron microscope (SEM) image is shown in Fig. S3. JJ1 is embedded in a
superconducting loop, whereas JJ2 is out of the loop. The distance between the
two JJs is 200 nm. We measured two samples, D and E, which have the same JJ
structure, but with sample E having gate electrodes on the respective
junctions. Figure S4 indicates $V_{\rm 2}$ of the voltage on JJ2 as a function
of $I_{\rm 2}$, the bias current on JJ2, and $B$ of sample D. The result
clearly shows the switching current oscillation, as seen in Fig. 3 in the main
text. We observed a similar oscillation in sample E, as shown in Fig. S5 (a).
We checked the gate voltage dependence of the switching current and evaluated
the peak-to-peak value and the average of the oscillation as a function of
$V_{\rm g1}$ and $V_{\rm g2}$, which represent the gate voltages on JJ1 and
JJ2 as seen in Fig. S5 (b) and (c), respectively. The $I_{\rm sw}$ evolution
with $V_{\rm g1}$ and $V_{\rm g2}$ has the same relation as that in Fig. 4(a)
and (b). The local gate voltage changes both the peak-to-peak value and the
average, while the nonlocal gate voltage changes only the peak-to-peak value.
These results indicate that the nonlocal Josephson effect is generally
obtained in the two coupled JJs on the semiconductor nanowires.

### Supplementary Note 4: Dependence on the separation between two JJs on a
single nanowire

When the AMS is formed on the two JJs, the correlation is expected to vanish
when the separation between two JJs is greater than the coherence length of
the superconductivity between the two JJs. To measure whether the oscillations
vanish in a device with a long separation between JJs, we fabricated four
devices with the same structure as sample F, but with different separations of
0.2, 0.4, 0.6, and 1.0 ${\rm\mu m}$, on a single SAG nanowire. The SEM image
is shown in Fig. S6. The observed $I_{\rm sw}$ values of the coupled JJ
devices with different separations $L$ are shown in Fig. S7(a). We note that
the quality of the SAG nanowire is inhomogeneous even in a single nanowire;
therefore we cannot ensure that all JJs have the same properties. However, the
results indicate that a longer distance between two JJs produces less or no
oscillation of the switching current. We executed the additional measurement
on the single nanowire device with 150 nm separation on the different wafer as
shown in Fig. S7(b). As a result, we found bigger amplitude of the oscillation
whose ratio to the Isw average is about 0.2. These results indicate that the
longer separation device tends to generate less oscillation.

The oscillation vanishes in devices of length 0.6 and 1.0 ${\rm\mu m}$. In
this study of the length dependence, we used the single nanowire samples.
Therefore, the two JJs are coupled through the proximity region beneath the
shared SC. The coherence length is modified as the formula of $\hbar v_{\rm
F}/\pi\Delta$ where $v_{\rm F}$ and $\Delta$ indicate the Fermi velocity and
the superconducting energy, respectively. Since we cannot pinch off the
nanowires due to the interfacial problem, we are not sure how large the
carrier density and the Fermi velocity are. However, around 600 nm in the
similar InAs/Al systems was reported previously Mayer  _et al._ (2019, 2020).
This length is comparable to the shortest distance between the two JJs in our
devices which did not show the oscillation. Then this length dependence is
qualitatively consistent with AMS physics that the nonlocal SC correlation
disappears when two JJs are at a larger distance than the coherence length.

We note that the selective area growth nanowires are not uniform and the
Josephson junction quality highly depends on the nanowires and also the
junction location on the single nanowire. In case the grain boundary or
impurities happen to appear in the junction, the junction quality can easily
become small. Therefore, we assume that the general trend of decreasing
modulation amplitude with increasing distance between nanowires is consistent
between the prediction and experiment but only qualitatively.

### Supplementary Note 5: Sample growth

The SAG InAs double nanowires were grown by molecular beam epitaxy (MBE)
Schmid  _et al._ (2015); Krizek  _et al._ (2018); Friedl  _et al._ (2018);
Aseev  _et al._ (2018); Vaitiekėnas  _et al._ (2018); Lee  _et al._ (2019).
Prior to the InAs growth, nanowire structures were patterned using standard
electron-beam lithography on ${\rm SiO_{x}}$ (30 nm)/${\rm Al_{2}O_{3}}$ (3
nm) layers on an Fe-doped semi-insulating InP(001) substrate. The patterns
were formed by dry-etching of the ${\rm SiO_{x}}$ masking layer and wet-
etching of the ${\rm Al_{2}O_{3}}$ etch-stop layer. The patterned nanowires
are along the [100] ridge direction. The processed InP surface was further
cleaned by ultraviolet-ozone and diluted HCl Lee  _et al._ (2019). In a III-V
MBE chamber, the patterned InP substrate was desorbed at 520°C with a flux of
${\rm As_{4}}$ molecules. 80-nm-thick InAs nanowires were grown at a growth
rate of 0.1 ML/second under As-rich growth conditions. After InAs growth, the
substrate was transferred to an interconnected MBE chamber and cooled to
$\sim$80 K using liquid nitrogen on a cold-head manipulator for Al layer
growth. To achieve a continuous Al layer between two adjacent InAs nanowires
along the [100] ridge direction, a 10-nm-thick Al layer was first grown at
+20° with respect to the [100] ridge direction, and another 10-nm-thick Al
layer was grown at -20° with respect to the [100] ridge direction. Immediately
after Al growth, the substrate was transferred to a loadlock within 5-6 min
and exposed to ${\rm O_{2}}$ gas for oxidation of the Al surface to preserve a
smooth and continuous Al layer prepared at a cryogenic temperature.

### Supplementary Note 6: Device fabrication

Epitaxial aluminium is grown globally on the substrate, and the two parallel
nanowires are intermediated by the Al film. In the fabrication process, we
removed the unnecessary epitaxial aluminium by wet etching with a type-D
aluminium etchant to form JJs and superconducting loops. Then, we grew a 20
nm-thick aluminium oxide layer through atomic layer deposition and fabricated
a separate gate electrode on each nanowire with Ti 5 nm and Au 20 nm.
Following the measurement, we checked that the upper and lower SC electrodes
were disconnected by SEM. Due to the interface quality of InP substrate and
InAs nanowire Krizek  _et al._ (2018), we cannot pinch off the conductance by
the top gate voltages.

### Supplementary Note 7: Measurement

For the measurement of sample A, we injected bias currents from the upper and
lower SC electrodes, with the shared SC electrode grounded. When we measured
$dV_{\rm U}/dI_{\rm U}$ ($dV_{\rm L}/dI_{\rm L}$), we added a small
oscillating current of 1 nA $\Delta I_{\rm U}(\Delta I_{\rm L})$ with 23 Hz on
$I_{\rm U}(I_{\rm L})$ and detected the oscillation component of the voltage
$\Delta V_{\rm U}(\Delta V_{\rm L})$ using the lock-in technique. For the
measurement of sample B, we only injected a DC bias current $I_{\rm U}$ and
detected $V_{\rm U}$. All measurements were performed at 10 mK, the base
temperature of our CryoConcept wet dilution fridge.

### Supplementary Note 8 : IV curves

In our device, the normal resistance is a few hundred Ohm, and the gate
structure works as the parallel capacitance. In the RCSJ model Stewart (1968);
McCumber (1968) which has been utilized for the Josephson junction analysis,
$\beta$ (McCumber parameter) term is an important parameter to determine if
the junction is overdamped or underdamped. When the beta is highly smaller
than 1, then the junction is overdamped, and hysteresis in the IV curve does
not appear. The estimated $\beta$ in sample B is around 0.025 at $B=0$ mT
which means the junction is highly overdamped. Therefore, we did not observe
the clear hysteresis in our study.

### Supplementary Note 9 :Line profiles of Fig. 2

We exhibit several line profiles of Figs. 2(b) and (c) on the main text.
Figures S8(a) and (b) indicate the line profiles on Fig. 2(b) at $I_{\rm
L}=\pm 400,\pm 200,0$ nA and on Fig. 2(c) at $I_{\rm U}=\pm 200,\pm 100,0$ nA.
At $I_{\rm L}=0$ nA, $dV_{\rm U}/dI_{\rm U}$ is not perfectly 0 nA in Fig.
S8(a). This is because of the phase diffusion Ambegaokar and Halperin (1969).
As $I_{\rm L}$ becomes far from 0 nA, suppression of $dV_{\rm U}/dI_{\rm U}$
corresponding to ${\rm SC_{US}}$ becomes smaller. This is assigned to the
Joule heating effect on JJL accelerating the phase diffusion in JJU. The same
features can be seen in Fig. S8(b).

Figure 5:  (a) shows the conductance as a function of $V_{\rm gL}$ and $V_{\rm
gU}$ of sample B measured at 4 K. The line profiles at various VgLs appear in
(b). The small measured $V_{\rm gL}$ dependence can be attributed to the
cross-capacitance contribution. (c) Resistance as a function of $B$ at 4 K.
There appear small fluctuations but no periodic oscillation.  Figure 6:
$V_{\rm U}$ as a function of $I_{\rm U}$ and $B$ obtained from sample C. A
clear oscillation, as seen in Fig. 3 (c), was measured.  Figure 7:  SEM image
of the double Josephson junction on an SAG single nanowire. The two JJs were
separated at 200 nm. The JJ length is 80 nm.  Figure 8:  Switching current of
the sample D oscillates as a function of $B$.  Figure 9:  (a) indicates the
differential resistance of sample E as a function of $B$ and $I_{\rm 2}$.
Oscillation is observed as in Fig. 3 (c); the peak-to-peak value and the
average hold the local and nonlocal gate voltage dependence similar to that in
Figs. 4 (a) and (b).  Figure 10:  SEM image of double JJs on single nanowire
with different separations. From left to right, the separations were 0.2, 0.4,
0.6, and 1.0 ${\rm\mu m}$.  Figure 11:  (a)$I_{\rm sw}$ as a function of $B$
of the coupled JJ devices with different separations in sample F is
represented. Coupled JJ devices with separation longer than 0.6 ${\rm\mu m}$
have no oscillation. (b)$I_{\rm sw}$ as a function of $B$ of the coupled JJ
devices with 150 nm separation is represented.  Figure 12:  (a)The line
profiles of Fig. 2(b) at $I_{\rm L}=\pm 400,\pm 200,0$ nA. (b)The line
profiles of Fig. 2(c) at $I_{\rm U}=\pm 200,\pm 100,0$ nA.  Figure 13:
$V_{\rm U}$ results as a function of $B$ and $I_{\rm U}$ at several $V_{\rm
gL}$ are shown. From these panels, we estimated the switching current and
constructed Fig. 4 (b) on the main.

## References

## References

  * Josephson (1962) B. Josephson, Physics Letters 1, 251 (1962).
  * Krantz  _et al._ (2019) P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, Applied Physics Reviews 6, 021318 (2019).
  * Pillet  _et al._ (2019) J.-D. Pillet, V. Benzoni, J. Griesmar, J.-L. Smirr, and Ç. O. Girit, Nano Letters 19, 7138 (2019).
  * Kornich  _et al._ (2019) V. Kornich, H. S. Barakov, and Y. V. Nazarov, Physical Review Research 1, 033004 (2019).
  * Kornich  _et al._ (2020) V. Kornich, H. S. Barakov, and Y. V. Nazarov, Physical Review B 101, 195430 (2020).
  * Furusaki and Tsukada (1991) A. Furusaki and M. Tsukada, Physical Review B 43, 10164 (1991).
  * Beenakker and van Houten (1991) C. W. J. Beenakker and H. van Houten, Phys. Rev. Lett. 66, 3056 (1991).
  * Chtchelkatchev and Nazarov (2003) N. M. Chtchelkatchev and Y. V. Nazarov, Physical Review Letters 90, 226806 (2003).
  * Zazunov  _et al._ (2003) A. Zazunov, V. S. Shumeiko, E. N. Bratus’, J. Lantz, and G. Wendin, Physical Review Letters 90, 087003 (2003).
  * Janvier  _et al._ (2015) C. Janvier, L. Tosi, L. Bretheau, C. O. Girit, M. Stern, P. Bertet, P. Joyez, D. Vion, D. Esteve, M. F. Goffman, H. Pothier, and C. Urbina, Science 349, 1199 (2015).
  * (11) O. Kurtossy, Z. Scherubl, G. Fulop, I. E. Lukacs, T. Kanne, J. Nygard, P. Makk, and S. Csonka, arXiv http://arxiv.org/abs/2103.14083v2 .
  * Klinovaja and Loss (2014) J. Klinovaja and D. Loss, Phys. Rev. B 90, 045118 (2014).
  * Gaidamauskas  _et al._ (2014) E. Gaidamauskas, J. Paaske, and K. Flensberg, Physical Review Letters 112, 126402 (2014).
  * Haim  _et al._ (2014) A. Haim, A. Keselman, E. Berg, and Y. Oreg, Physical Review B 89, 220504 (2014).
  * Baba  _et al._ (2018) S. Baba, C. Junger, S. Matsuo, A. Baumgartner, Y. Sato, H. Kamata, K. Li, S. Jeppesen, L. Samuelson, H. Q. Xu, C. Schonenberger, and S. Tarucha, New Journal of Physics 20, 063021 (2018).
  * Ueda  _et al._ (2019) K. Ueda, S. Matsuo, H. Kamata, S. Baba, Y. Sato, Y. Takeshige, K. Li, S. Jeppesen, L. Samuelson, H. Xu, and S. Tarucha, Science Advances 5, eaaw2194 (2019).
  * Freyn  _et al._ (2011) A. Freyn, B. Douçot, D. Feinberg, and R. Mélin, Physical Review Letters 106, 257005 (2011).
  * Pfeffer  _et al._ (2014) A. H. Pfeffer, J. E. Duvauchelle, H. Courtois, R. Mélin, D. Feinberg, and F. Lefloch, Physical Review B 90, 075401 (2014).
  * Feinberg  _et al._ (2015) D. Feinberg, T. Jonckheere, J. Rech, T. Martin, B. Douçot, and R. Mélin, The European Physical Journal B 88, 99 (2015).
  * Strambini  _et al._ (2016) E. Strambini, S. D. Ambrosio, F. Vischi, F. S. Bergeret, Y. V. Nazarov, and F. Giazotto, Nature Nanotechnology 11, 1055 (2016).
  * Cohen  _et al._ (2018) Y. Cohen, Y. Ronen, J.-H. Kang, M. Heiblum, D. Feinberg, R. Mélin, and H. Shtrikman, Proceedings of the National Academy of Sciences 115, 6991 (2018).
  * Draelos  _et al._ (2019) A. W. Draelos, M.-T. Wei, A. Seredinski, H. Li, Y. Mehta, K. Watanabe, T. Taniguchi, I. V. Borzenets, F. Amet, and G. Finkelstein, Nano Letters 19, 1039 (2019).
  * Pankratova  _et al._ (2020) N. Pankratova, H. Lee, R. Kuzmin, K. Wickramasinghe, W. Mayer, J. Yuan, M. G. Vavilov, J. Shabani, and V. E. Manucharyan, Physical Review X 10, 031051 (2020).
  * Graziano  _et al._ (2020) G. V. Graziano, J. S. Lee, M. Pendharkar, C. J. Palmstrøm, and V. S. Pribiag, Physical Review B 101, 054510 (2020).
  * van Heck  _et al._ (2014) B. van Heck, S. Mi, and A. R. Akhmerov, Physical Review B 90, 155450 (2014).
  * Yokoyama and Nazarov (2015) T. Yokoyama and Y. V. Nazarov, Physical Review B 92, 155437 (2015).
  * Riwar  _et al._ (2016) R.-P. Riwar, M. Houzet, J. S. Meyer, and Y. V. Nazarov, Nature Communications 7, 11167 (2016).
  * Xie  _et al._ (2017) H.-Y. Xie, M. G. Vavilov, and A. Levchenko, Physical Review B 96, 161406 (2017).
  * Baba  _et al._ (2017) S. Baba, S. Matsuo, H. Kamata, R. S. Deacon, A. Oiwa, K. Li, S. Jeppesen, L. Samuelson, H. Q. Xu, and S. Tarucha, Applied Physics Letters 111, 233513 (2017), https://doi.org/10.1063/1.4997646 .
  * Krogstrup  _et al._ (2015) P. Krogstrup, N. L. B. Ziino, W. Chang, S. M. Albrecht, M. H. Madsen, E. Johnson, J. Nygård, C. M. Marcus, and T. S. Jespersen, Nature Materials 14, 400 (2015).
  * Ambegaokar and Halperin (1969) V. Ambegaokar and B. I. Halperin, Phys. Rev. Lett. 22, 1364 (1969).
  * Mayer  _et al._ (2019) W. Mayer, J. Yuan, K. S. Wickramasinghe, T. Nguyen, M. C. Dartiailh, and J. Shabani, Applied Physics Letters 114, 103104 (2019).
  * Mayer  _et al._ (2020) W. Mayer, M. C. Dartiailh, J. Yuan, K. S. Wickramasinghe, E. Rossi, and J. Shabani, Nature Communications 11, 212 (2020).
  * Schmid  _et al._ (2015) H. Schmid, M. Borg, K. Moselund, L. Gignac, C. M. Breslin, J. Bruley, D. Cutaia, and H. Riel, Applied Physics Letters 106, 233101 (2015).
  * Krizek  _et al._ (2018) F. Krizek, J. E. Sestoft, P. Aseev, S. Marti-Sanchez, S. Vaitiekėnas, L. Casparis, S. A. Khan, Y. Liu, T. Stankevič, A. M. Whiticar, A. Fursina, F. Boekhout, R. Koops, E. Uccelli, L. P. Kouwenhoven, C. M. Marcus, J. Arbiol, and P. Krogstrup, Physical Review Materials 2, 093401 (2018).
  * Friedl  _et al._ (2018) M. Friedl, K. Cerveny, P. Weigele, G. Tutuncuoglu, S. Marti-Sanchez, C. Huang, T. Patlatiuk, H. Potts, Z. Sun, M. O. Hill, L. Guniat, W. Kim, M. Zamani, V. G. Dubrovskii, J. Arbiol, L. J. Lauhon, D. M. Zumbuhl, and A. F. i Morral, Nano Letters 18, 2666 (2018).
  * Aseev  _et al._ (2018) P. Aseev, A. Fursina, F. Boekhout, F. Krizek, J. E. Sestoft, F. Borsoi, S. Heedt, G. Wang, L. Binci, S. Martí-Sánchez, T. Swoboda, R. Koops, E. Uccelli, J. Arbiol, P. Krogstrup, L. P. Kouwenhoven, and P. Caroff, Nano Letters 19, 218 (2018).
  * Vaitiekėnas  _et al._ (2018) S. Vaitiekėnas, A. Whiticar, M.-T. Deng, F. Krizek, J. Sestoft, C. Palmstrøm, S. Marti-Sanchez, J. Arbiol, P. Krogstrup, L. Casparis, and C. Marcus, Physical Review Letters 121, 147701 (2018).
  * Lee  _et al._ (2019) J. S. Lee, S. Choi, M. Pendharkar, D. J. Pennachio, B. Markman, M. Seas, S. Koelling, M. A. Verheijen, L. Casparis, K. D. Petersson, I. Petkovic, V. Schaller, M. J. W. Rodwell, C. M. Marcus, P. Krogstrup, L. P. Kouwenhoven, E. P. A. M. Bakkers, and C. J. Palmstrøm, Physical Review Materials 3, 084606 (2019).
  * Stewart (1968) W. C. Stewart, Applied Physics Letters 12, 277 (1968).
  * McCumber (1968) D. E. McCumber, Journal of Applied Physics 39, 3113 (1968).
  * Ambegaokar and Halperin (1969) V. Ambegaokar and B. I. Halperin, Phys. Rev. Lett. 22, 1364 (1969).