\section{Introduction}
The graphs in this paper are simple. Let $V(G)$ denote the vertex set of a graph $G$ and let $E(G)$ denote its edge set. If two distinct vertices $v_i, v_j \in V(G)$ are adjacent in $G$, we write $v_i\sim v_j$, otherwise, $v_i \not \sim v_j$. The \emph{adjacency matrix}, $A(G)=(a_{ij})$, of a graph $G$ with $V(G)=\{v_1,\ldots,v_n\}$ is an $n\times n$ $(0,1)$ symmetric matrix in which $a_{ij}=1$ if and only if $v_i \sim v_j$. The \emph{spectrum} of $G$  is the multiset of the eigenvalues of $A(G)$.  Several parameters of a graph can be deduced from the spectrum of $A(G)$. For example,   $\text{trace}(A(G)^k)=\sum_{i=1}^n\lambda_i^k$ is the number of all closed walks, of length $k$ in $G$, so in particular, $|E(G)|=\frac{1}{2}\text{trace}(A(G)^2)$ and the number of triangles in $G$ is $\frac{1}{6}\text{trace}(A(G)^3)$. Thus it is interesting to know which graphs are determined (up to isomorphism) by their spectrum, that is, graphs for which there exist no   non-isomorphic graph with the same spectrum. Two non-isomorphic graphs $G$ and $H$ are \emph{cospectral} if they have the same spectrum. A classical example of non-isomorphic cospectral graphs is given in Figure \ref{nnn} \cite{cvetkovic1971graphs}; their common spectrum is $\{[2]^1, [0]^3, [-2]^1\}$ (exponents indicate multiplicities). The complete graph $K_n$ and the path graph $P_n$ are determined by their spectrum.

Let $V(G)=\{v_1,\ldots,v_n\}$. Then $D(G)=(d_{ij})$ is the diagonal matrix with $d_{ii}$ the degree of $v_i$. Let $I$ denote the identity matrix and $J$ the all-ones matrix. A linear combination of $A(G), D(G), J$ and $I$ is called a \emph{generalised adjacency matrix}. There are many results on the spectra of generalised adjacency matrices, see the excellent surveys \cite{van2003graphs,haemers2004enumeration,vanDamHaemers2009}.  Generalised adjacency matrices include the {\it Laplacian}, $L(G)=D(G)-A(G)$, the {\it signless Laplacian}, $Q(G)=D(G)+A(G)$, and the {\it Seidel matrix} $S(G)=J-I-2A(G)$. Note that  the Seidel matrix $S(G)= (s_{ij})$ of $G$ is the square matrix of order $n$ defined by
\[s_{ij}=\begin{cases}
0 & \mbox{if $v_i=v_j$},\\
1 & \mbox{if $v_i\not \sim v_j$, $v_i\neq v_j$},\\
-1 & \mbox{if $v_i\sim v_j$, $v_i\neq v_j$.}
\end{cases}\]  Other matrices for which the spectrum is of interest are the \emph{distance matrix}, where the $(i,j)$ entry is the distance between $v_i$ and $v_j$, and the
 {\it normalized Laplacian}, $\mathcal{L}(G)=D(G)^{-\frac{1}{2}}L(G)D(G)^{-\frac{1}{2}}$. Let $X\in \{$generalised adjacency, Laplacian, signless Laplacian, normalised Laplacian, distance, Seidel$\}$. The \emph{$X$ spectrum} of $G$ is the spectrum of the $X$ matrix of $G,$ and the references mentioned above contain many results on finding non-isomorphic $X$ cospectral graphs (i.e., non-isomorphic graphs that have the same $X$ spectrum) or showing that a graph is determined by its $X$ spectrum. In addition, some graphs that are determined by the normalized Laplacian spectrum are given in \cite{butler2016cospectral,berman2018family}, and the references there. Our paper is a small contribution to the rich literature on graphs that are determined by their $X$ spectrum. This is done by considering the Seidel spectrum of complete multipartite graphs. We mention in passing, that complete multipartite graphs are determined by the spectrum of the distance matrix but not by the spectrum of the adjacency matrix \cite{Delorme2012,jin2014complete}.

 Let $U,W\subseteq V(G)$ form a partition of $V(G)$. A \emph{Seidel switching} with respect to $U$ transforms $G$ to a graph $H$ by deleting the edges between $U$ and $W$ and adding an edge between vertices $u\in U$ and $w\in W$ if $(u,w)\notin E(G)$. For more details on Seidel matrices and related topics, see \cite{van1991equilateral,sciriha2018two,szollHosi2018enumeration,balla2018equiangular} and the references there. Seidel switching is an equivalence relation and we say that $G$ and $H$ are \emph{switching equivalent}. In general, $G$ and $H$ are not isomorphic, but since $S(H)=\Lambda S(G) \Lambda$, where $\Lambda$ is a signature matrix (a diagonal matrix with $1$  entries corresponding to vertices of $U$ and $-1$  entries corresponding to vertices of $W$), $S(H)$ and $S(G)$ are similar and have the same spectrum. Hence such $G$ and $H$ are cospectral, so no graph with more than one vertex is determined by its Seidel spectrum.  Hence we say that a graph $G$ is \emph{Seidel determined, up to switching,} (or, in short, {\it $S$-determined}) if the only graphs with same Seidel spectrum are switching equivalent to a graph isomorphic to $G$.

\begin{figure}[!ht]
\begin{center}
\begin{tikzpicture}[scale=0.8]

\draw[thick] (0,2)--(2.8,0);
\draw[thick] (0,0)--(2.8,2);

\draw[fill](0,0) circle[radius=0.1];
\draw[fill](0,2) circle[radius=0.1];
\draw[fill](2.8,0) circle[radius=0.1];
\draw[fill](2.8,2) circle[radius=0.1];
\draw[fill](1.4,1) circle[radius=0.1];

\draw[thick] (6,0)--(6,2)--(8.8,2)--(8.8,0)--cycle;

\draw[fill](6,0) circle[radius=0.1];
\draw[fill](6,2) circle[radius=0.1];
\draw[fill](8.8,0) circle[radius=0.1];
\draw[fill](8.8,2) circle[radius=0.1];
\draw[fill](7.4,1) circle[radius=0.1];

\end{tikzpicture}
\caption{A pair of on-isomorphic cospectral graphs   \label{nnn}}
\end{center}\vspace{-8pt}
\end{figure}

The paper is organized as  follows. In Section \ref{no&pri} we discuss some notations and preliminaries used in the main results. In Section \ref{comultipar} we consider   complete multipartite graphs. We show that each graph  Seidel cospectral with a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and describe  cases when   complete multipartite graphs are $S$-determined. Complete tripartite graphs are considered in Section \ref{comtripar}, where we present triples $p,q,r$ for which $K_{p,q,r}$ is $S$-determined and examples of non-isomorphic, non switching equivalent, Seidel cospectral complete tripartite graphs. We conclude with a conjecture on complete tripartite graphs on more than 18 vertices.

\section{Notations and preliminaries}\label{no&pri}

We begin with presenting the Seidel spectrum of some graphs.

\begin{lemma}\label{spectra1}
\begin{enumerate}
\item[{\rm(a)}] The  Seidel spectrum of the empty graph on $n$ vertices is $\{[n-1]^1,[-1]^{n-1} \}$.
\item[{\rm(b)}] The Seidel spectrum of the complete graph $K_n$ is $\{[1]^{n-1}, [1-n]^1 \}$.
\item[{\rm(c)}] The Seidel spectrum of the complete bipartite graph $K_{p,q}$ is $\{[p+q-1]^1,[-1]^{p+q-1}\} $.
\end{enumerate}
\end{lemma}

\begin{proof}
The Seidel matrix of the empty graph on $n$ vertices is the $n\times n$ matrix $J-I$. The Seidel matrix of $K_n$ is $I-J$,  and the graph
 $K_{p,q}$ is   obtained by switching from the empty graph on ${p+q}$ vertices, where $U$ is any subset of $p$ vertices.
\end{proof}

To prove our main theorem we need the  Seidel spectra of some graphs on $5$ vertices with an isolated vertex.

\begin{figure}[!ht]
\begin{center}
\begin{tikzpicture}[scale=0.8]

\draw[thick] (0,1.2)--(0,0)--(1.2,0)--(1.2,1.2);

\draw[fill](0,0) circle[radius=0.1];
\draw[fill](1.2,0) circle[radius=0.1];
\draw[fill](0,1.2) circle[radius=0.1];
\draw[fill](1.2,1.2) circle[radius=0.1];
\draw[fill](.6,2) circle[radius=0.1];

\draw[thick] (4,1.2)--(4,0);
\draw[thick] (5.2,0)--(5.2,1.2);

\draw[fill](4,0) circle[radius=0.1];
\draw[fill](5.2,0) circle[radius=0.1];
\draw[fill](4,1.2) circle[radius=0.1];
\draw[fill](5.2,1.2) circle[radius=0.1];
\draw[fill](4.6,2) circle[radius=0.1];

\draw[thick] (8.6,.8)--(8,0)--(9.2,0)--(8.6,.8)--(8.6,1.5);

\draw[fill](8,0) circle[radius=0.1];
\draw[fill](9.2,0) circle[radius=0.1];
\draw[fill](8.6,.8) circle[radius=0.1];
\draw[fill](8.6,1.5) circle[radius=0.1];
\draw[fill](8.6,2.2) circle[radius=0.1];

\end{tikzpicture}
\caption{$K_1\cup P_4$, $K_1\cup K_2\cup K_2$  and  $K_1\cup H$   \label{fig:paw}}
\end{center}\vspace{-8pt}
\end{figure}

\begin{lemma}\label{spectra2}
\begin{enumerate}
\item[{\rm(a)}] The Seidel spectrum of $K_1\cup P_4$ is $[\sqrt{5}]^2, [0]^1, [-\sqrt{5}]^2$;  $-\sqrt{5}\approx -2.2361$.
\item[{\rm(b)}]  The  Seidel spectrum of $K_1\cup K_2\cup K_2$ is $\left[\frac{1+\sqrt{17}}{2}\right]^1,[1]^2,\left[\frac{1-\sqrt{17}}{2}\right]^1, [-3]^1$;
    $\frac{1-\sqrt{17}}{2}\approx -1.5616$.
\item[{\rm(c)}] The Seidel spectrum of the $K_1\cup H$, where $H$ is the paw graph
{\begin{tikzpicture}[scale=0.4] \draw[thick](.6,.8)--(0,0)--(1.2,0)--(.6,.8)--(.6,1.5);
\draw[fill](0,0) circle[radius=0.1];
\draw[fill](1.2,0) circle[radius=0.1];
\draw[fill](.6,.8) circle[radius=0.1];
\draw[fill](.6,1.5) circle[radius=0.1];
\end{tikzpicture}}, is  \\$\left[\frac{1+\sqrt{17}}{2}\right]^1,[1]^2,\left[\frac{1-\sqrt{17}}{2}\right]^1, [-3]^1$.
\end{enumerate}
\end{lemma}

\begin{proof}
Parts (a) and (b) are found by direct computation. For (c) note that $K_1\cup H$ is obtained from $K_1\cup K_2\cup K_2$ by switching with respect to
$U=\{u\}$, where $u$ is an end vertex of one of the two edges.
\end{proof}

\section{Complete multipartite graphs}\label{comultipar}
For considering general complete multipartite graphs, we need some facts about their Seidel spectrum.
The Seidel spectrum of the complete multipartite graph $K_{p,p,\ldots, p}$ was found
in \cite{LvWeiZhao2012} by computing the characteristic polynomial of the graph. We
include here a different proof.

\begin{lemma}\label{spectra0}
The Seidel spectrum of the graph $K_{p,p,\ldots, p}$ on $n=kp$ vertices is
\[\{[2p-1]^{k-1},[-1]^{n-k}, [-n+2p-1]^1\}.\]
\end{lemma}

\begin{proof}
The  Seidel matrix of  $K_{p,p, \ldots, p}$ is $(2I_k-J_k)\otimes J_p -I_n$, where
$\otimes$ denotes the Kronecker product, and $n=kp$. The spectrum of $2I_k-J_k$ is $\{[2]^{k-1},[2-k]^1\}$, and that of $J_p$ is $\{[p]^1,[0]^{p-1}\}$. The spectrum of
their Kronecker product consists of all the products of these eigenvalues: $\{[2p]^{k-1},[0]^{(p-1)k}, [(2-k)p]^1 \}=\{[2p]^{k-1},[0]^{n-k}, [2p-n]^1 \}$. Thus the Seidel spectrum
of $K_{p,p, \ldots, p}$   is $\{[2p-1]^{k-1},[-1]^{n-k}, [-n+2p-1]^1\}$.
\end{proof}

The next lemma is mostly implicit in \cite[Corollaries 2.2 and 2.3, and eq. (3)]{WangZhaoLi2014}.
We include a partial explanation for better clarity.

\begin{lemma}\label{spectra3}
Let $p_1\ge p_2\ge \ldots\ge p_k\ge 1$. Denote the  Seidel eigenvalues of the complete $k$-partite graph $K_{p_1, p_2, \ldots, p_k}$
by $\lambda_1\ge \lambda_2\ge \ldots \ge \lambda_n$, where $n=p_1+p_2+\ldots+p_k$. Then
\begin{enumerate}
\item[(1)] $\lambda_1\ge \lambda_2\ge \ldots \ge  \lambda_{k-1}>0>\lambda_{k}=-1=\ldots=-1=\lambda_{n-1}\ge \lambda_n$.
\item[(2)] $ 2p_1-1\ge \lambda_1\ge 2p_2-1\ge \lambda_2\ge \ldots\ge 2p_{k-1}-1 \ge\lambda_{k-1}\ge 2p_k-1$,
\item[(3)] $(2-k)p_k-1\ge \lambda_n\ge 2p_k-n-1$.
\item[(4)] For $i=1, \ldots, k-1$, if $p_i>p_{i+1}$, then $2p_i-1>\lambda_i>2p_{i+1}-1$.
\end{enumerate}
\end{lemma}

\begin{proof}
The graph $K_{p_k,p_k,\ldots, p_k}$ is an induced subgraph of $K_{p_1, p_2, \ldots, p_k}$, with
Seidel eigenvalues $\mu_1\ge \mu_2\ge \ldots \ge \mu_{kp_k}$. By Lemma \ref{spectra0},
\[\mu_1=\ldots=\mu_{k-1}=2p_k-1>0.\]
By interlacing we get that
\[\lambda_i\ge \mu_i>0\]
for every $i=1, \ldots, k-1$,
and
\[(2-k)p_k-1=\mu_{kp_k}\ge \lambda_{n-kp_k+kp_k}=\lambda_n.\]
Let $S$ be the Seidel matrix of $K_{p_1,p_2,\ldots, p_k}$. It is easy to see that  in $I+S$ there are only $k$ different rows (the $i$-th of which is repeated
$p_i$
times, $i=1,\ldots, k$). Thus $\rank(I+S)\le k$, and $-1$ is an  eigenvalue of $S$ of multiplicity at least $n-k$. This completes the proof of (1) (and part of (3)).

The more detailed inequalities  on the Seidel eigenvalues in  (2) and (4) follow  from analysis of the characteristic polynomial of $S$, done in \cite[Theorem 2.2]{WangZhaoLi2014}. The polynomial
is
\[(x+1)^{n-k}\left[\prod_{i=1}^k\left(x-2p_i+1\right)+ \sum_{j=1}^k p_j\prod_{\underset{i\ne j}{i=1}}^k (x-2p_i+1),\right]\]
and thus the $n-k$ eigenvalues of $S$ other than the known  $-1$'s are the roots of
\[f(x)=\prod_{i=1}^k\left(x-2p_i+1\right)+ \sum_{j=1}^k p_j\prod_{\underset{i\ne j}{i=1}}^k (x-2p_i+1). \]
The inequality $\lambda_n\ge 2p_k-n-1$ follows from
\[0=\sum_{i=1}^n\lambda_i\le \sum_{i=1}^{k-1}(2p_i-1)+(n-k)(-1)+\lambda_n,\]
combined with $\sum_{i=1}^{k-1}p_i=n-p_k$. This completes the proof of (3).
\end{proof}

\begin{theorem}\label{main}
Let the Seidel spectrum of $G$ be equal to that of  the complete $k$-partite graph $K_{p_1, p_2, \ldots, p_k}$. Then
$G$ is a complete $k$-partite graph, up to switching.
\end{theorem}

\begin{proof}
We first show that $G$ is complete multipartite up to switching.
By using a switching with respect to the neighborhood of a single vertex, we may assume that
$G=K_1\cup D$. As the Seidel spectrum of $G$ is equal to that of $K_{p_1, p_2, \ldots, p_k}$,
$\lambda_{n-1}=-1$. If  $\mu_1\ge \ldots\ge \mu_5$ are the Seidel eigenvalues of an  induced subgraph of $G$ on $5$ vertices,  $\mu_{4}\ge \lambda_{n-5+4}=-1$ by interlacing. Hence,
by Lemma \ref{spectra2}, $G$ cannot have an induced $K_1\cup K_2\cup K_2$, or an induced
$K_1\cup P_4$, or an induced $K_1\cup  H$, where $H$ is the paw graph. Therefore $D$ cannot contain an induced $K_2\cup K_2$ or an induced $P_4$, or an induced paw.

At most one of the components of $D$ may contain an edge, since otherwise
$D$ contains an induced $K_2\cup K_2$, contrary to the assumption.
Let  $\chi(D)=t$ be the chromatic number of $D$. If $t>1$ then $D$ contains (exactly one) component $C$ with
at least one edge, and $\chi(D)=\chi(C)$.
Let $C=V_1\cup V_2\cup \ldots\cup V_t$, such that $v{\not\sim}u$ whenever $v, u\in V_i$,
and for each $i\ne j$ there is an edge with one end in $V_i$ and one end in $V_j$.
Let $v\in V_i$ and $u\in V_j$ be neighbors. If $w\in V_i$, $w\ne v$, then
$w$ has to be a neighbor of $u$ too. To see that, suppose on the contrary that $w{\not\sim}u$. Then by the connectivity of $C$, $w$ has a neighbor $z\ne u$.
As $v{\not\sim}w$, the subgraph of $D$ induced on vertices  $\{v,u,z,w\}$ is one of the following: either
an induced $K_2\cup K_2$ (if it has only the edges $vu$ and $wz$), or  an induced $P_4$ (if $u\sim z$ and $v\not\sim z$), or  an induced paw (if $v$ and $u$ are both neighbors of $z$).
This contradicts the observation above, that none of these is a possible induced subgraph of $D$. Thus every neighbor of $v\in V_i$ is also
a neighbor of all the other vertices in $V_i$. Suppose $u\in V_j$, $j\ne i$. By the same argument, each vertex in $V_j$
is a neighbor of each of the vertices in $V_i$. Hence the graph induced on $V_i\cup V_j$ is complete bipartite.
Since this holds for any  $i\ne j$,  the graph $C$ is complete $t$-partite graph. Therefore $D$, and thus $G$, consists of a complete multipartite graph and isolated vertices.

Let $U$ be the set of all isolated vertices of $K_1\cup D$. Switching with respect to $U$ yields a complete $(t+1)$-partite graph.
Hence $G$ is a complete $r$-partite graph for some $r$ (up to switching). The number of positive Seidel eigenvalues of $G$
is therefore $r-1$. On the other hand, the Seidel eigenvalues of $G$ are those of $K_{p_1, p_2, \ldots, p_k}$, hence $r-1=k-1$, implying that $G$ is a
complete $k$-partite graph, up to switching.
\end{proof}

According to the next theorem, two complete $k$-partite graphs, $k\ge 3$, can be switching equivalent only if they are isomorphic.

\begin{theorem}\label{difkpart}
Let $p_1\ge p_2\ge \ldots \ge p_k\ge 1$ and $q_1\ge q_2\ge \ldots \ge q_k\ge 1$ be  two different $k$-tuples, $k\ge 3$, such
that $\sum_{i=1}^kp_i=\sum_{i=1}^kq_i$. Then $K_{p_1, p_2, \ldots, p_k}$ and $K_{q_1, q_2,\ldots, q_k}$
are not switching-equivalent.
\end{theorem}

\begin{proof}
Let $V_i$ denote the independent set in $G=K_{p_1, p_2, \ldots, p_k}$ of size $p_i$,  $i=1,\ldots, k$.
Let $W_i$, $i=1,\ldots, k$, be the independent sets in $K_{q_1, q_2,\ldots, q_k}$.
Suppose there exists $U\subseteq \cup_{i=1}^k V_i$ such that
switching $G$ with respect to $U$ yields $G'=K_{q_1, q_2,\ldots, q_k}$. The set $U$ is not
empty, since by the assumption on the $k$-tuples $G'\ne G$.

We denote $V_{i1}=V_i\cap U$, and $V_{i2}=V_i\setminus V_{i1}$.
In $G'$, each vertex in $V_{i1}$ is connected by an edge with each vertex in $V_{i2}$, and
with each vertex in $V_{j1}$, $j\ne i$, and to no other vertices. Similarly, each vertex in $V_{i2}$ is connected also
with each vertex in $V_{j2}$, $j\ne i$.

Suppose without loss of generality that $V_{11}\ne \emptyset$. Then at most one of $V_{i2}$, $i=2, \ldots, k$,
is not empty. For if $V_{i2}, V_{j2}\ne \emptyset$, for $i, j\ge 2$, $i\ne j$, then
as $V_{11}\subseteq W_\ell$ for some $\ell$, and $V_{11}\cup V_{i2}$ is independent in $G'$,
also $V_{i2}\subseteq W_\ell$. Similarly, $V_{j2}\subseteq W_\ell$. But since there are
edges between $V_{i2}$ and $V_{j2}$, this contradicts the independence of $W_\ell$.
So suppose without loss of generality that $V_{i2}=\emptyset$ for $3\le i\le k$.
Then $V_{i1}=V_i$ for $3\le i\le k$.

Now both $V_{11}$ and $V_{k1}$ are not empty. If $V_{22}\ne \emptyset$, then $V_{11}\cup V_{22}$ is independent in $G'$
and thus contained in $W_\ell$. But then since $V_{k1}\cup V_{22}$ is independent, also $V_{k1}\subseteq W_\ell$. A
contradiction, since there is an edge between $V_{11}$ and $V_{k1}$. Hence $V_{22}$ is empty, and
$V_{21}=V_2$ is non-empty. By the independence of both $V_{k1}\cup V_{12}$ and $V_{21}\cup V_{12}$ in $G'$, and
the existence of edges between $V_{k1}$ and $V_{21}$,
we get that $V_{12}$ has also to be empty. That is, $V_{11}=V_1$, and thus $U$ consists of all the vertices of $G$,
which means that $G'=G$, contrary to the assumption that the $k$-tuples are different.
\end{proof}

The last theorem leaves out the case $k=2$.

\begin{remark}\label{Kpq=Kst}
{\rm By Lemma \ref{spectra1} all complete bipartite graphs are Seidel cospectral.
However, any two complete bipartite graphs are also switching equivalent:
Let $K_{p,q}$ and $K_{s,t}$ be two non-isomorphic complete bipartite graphs, with $p+q=s+t=n$, $\{s,t\}\ne \{p,q\}$.
Suppose $p\ge q$, $s\ge t$, and $p>s$.
Let $V_1$ and $V_2$ be the independent sets in $K_{p,q}$, $|V_1|=p$, $|V_2|=q$.
Let $U\subseteq V_1$ be any set of $s-q$ vertices
(by our assumptions, $p-t=s-q$  and $p-t>s-t\ge 0$, so $p>s-q>0$). Then after switching $K_{p,q}$ with
respect to $U$, we get $K_{s,t}$  with independent sets $W_1=U\cup V_2$ and $W_2=V_1\setminus U$.}
\end{remark}

Combining Remark \ref{Kpq=Kst} with Theorem \ref{main} we get that if a graph $G$
is cospectral with $K_{p,q}$, then $G$ is switching equivalent to  a complete bipartite graph, and therefore
to $K_{p,q}$.

\begin{theorem}
Any complete bipartite graph is $S$-determined.
\end{theorem}

In some cases a complete $k$-partite graph is  determined by its
Seidel spectrum up to switching. The following is one such case.

\begin{theorem}\label{Kpiqi}
Let $p_1> \ldots > p_l\ge  1$. The graph $K_{\underset{s_1}{\underbrace{p_1,...,p_1}},\ldots,\underset{s_l}{\underbrace{p_l,...,p_l}}}$, where $s_i\geq 3$ for every $i=1,\ldots,l$, is $S$-determined.
\end{theorem}
\begin{proof}
Let  $r_i=\sum_{j=1}^{i}s_j, i=1,2,\ldots,l$, $r_0=0$. Denote $k=r_l$. Let $\lambda_1\ge \ldots\ge \lambda_n$, where
$n=\sum_{i=1}^l s_ip_i$, be the Seidel eigenvalues of the $k$-partite graph $K_{\underset{s_1}{\underbrace{p_1,...,p_1}},\ldots,\underset{s_l}{\underbrace{p_l,...,p_l}}}$. By Lemma \ref{spectra3},
for  $i=1, \ldots, l$
\[\lambda_j=2p_i-1,\quad j=r_{i-1}+1, \ldots, r_i-1,\]
and
\[2p_i-1>\lambda_{r_i}>2p_{i+1}-1.\]

If for $q_1\ge q_2\ge \ldots \ge q_k$ the graph
$K_{q_1, q_2, \ldots, q_k}$ has the same Seidel spectrum, then by Lemma \ref{spectra3}(2), for $i=1,\ldots,l$,
\[2q_j-1\geq \lambda_j=2p_i-1 \geq 2q_{j+1}-1, j=r_{i-1}+1,\ldots,  r_{i}-1.\]
Hence $q_{j}=p_i$ for  $j=r_{i-1}+2,\ldots, r_{i}-1$.

By Lemma \ref{spectra3}(4),   $q_{r_{i-1}+1}>q_{r_{i-1}+2}$  is impossible, since otherwise
\[2q_{r_{i-1}+1}-1>\lambda_{r_{i-1}+1}>2q_{r_{i-1}+2}-1,\] contrary to $\lambda_{r_{i-1}+1}=2p_i-1=2q_{r_{i-1}+2}-1$ obtained above. Hence, $q_{j}=p_i$, for $j=r_{i-1}+1,\ldots, r_{i}-1$, $i=1, \ldots, l$.

Since $\sum_{j=1}^k q_j=\sum_{i=1}^k s_ip_i$, we have     $\sum_{i=1}^{l}q_{r_i}=\sum_{i=1}^{l}p_i$.
As $q_{r_i}\le q_{r_i-1}=p_i$  for every $i=1, \ldots, l$, the latter equality of  sums implies that
$q_{r_i}=p_i$ for every $i$.
\end{proof}

In general, however, there may be complete $k$-partite graphs that are not switching-equivalent and have
the same Seidel spectrum. Some examples of such tripartite graphs are included in the next section.

\section{Complete tripartite graphs}\label{comtripar}
It was shown in \cite{LvWeiZhao2012} that the
characteristic polynomial of the Seidel matrix of the complete tripartite graph $K_{p,q,r}$ is
\[(\lambda+1)^{n-3}(\lambda^3+\lambda^2(3-n)+\lambda(3-2n)+(4pqr-n+1)),\]
where $n=p+q+r$. Thus if $\lambda_1>\lambda_2$ are the two positive Seidel eigenvalues of $K_{p,q,r}$ and
$\lambda_n$ is its smallest Seidel eigenvalue, then $\lambda_1, \lambda_2, \lambda_n$
are the roots of the polynomial \[\lambda^3+\lambda^2(3-(p+q+r))+\lambda(3-2(p+q+r))+(4pqr-(p+q+r)+1).\]
As  the other $n-3$ eigenvalues in both graphs are all equal to $-1$, $K_{x,y,z}$ has exactly the same Seidel
spectrum as $K_{p,q,r}$  if and only if
the following two equalities hold:
\begin{align}
x+y+z&=p+q+r   \label{p+q+r}\\
xyz&=pqr ~~.\label{pqr}
\end{align}
Combined with Theorem \ref{difkpart} this implies the following.

\begin{observation}\label{dif3part}
The complete tripartite graph $K_{p,q,r}$ is $S$-determined  if and only if
the unique solution (up to permutation) to the system of equations \eqref{p+q+r} and \eqref{pqr} is
 $\{x,y,z\}=\{p,q,r\}$.
\end{observation}

\begin{example}\label{661}
The graphs $K_{6,6,1}$ and $K_{9,2,2}$ have the same Seidel spectrum, but are not switching-equivalent.
\end{example}

We mention a few more observations:
\begin{itemize}
\item Suppose one of $x,y,z$ is equal to one of $p,q,r$, say $x=p$. Then
$y$ and $z$ have to have the same sum and the same product as $q$ and $r$. But $q,r$ is the only pair of integers
with sum $q+r$ and product $qr$. Thus if $K_{x,y,z}$ has the same Seidel spectrum as $K_{p,q,r}$  and is
not switching-equivalent to $K_{p,q,r}$, then $\{x,y,z\}\cap\{p,q,r\}=\emptyset$.
\item  If $K_{x,y,z}$ has
the same Seidel spectrum as $K_{p,q,r}$, then $K_{kx,ky,kz}$ has the same spectrum as $K_{kp,kq,kr}$.
Thus if $K_{p,q,r}$ is not   $S$-determined, then for every positive
integer $k$ the graph $K_{kp,kq,kr}$ is not  $S$-determined.  The converse does not hold: $K_{10,2,2}$
has the same Seidel spectrum as $K_{8,5,1}$, but $K_{5,1,1}$ is $S$-determined, see Theorem \ref{pq1} below.
\end{itemize}

It is not hard to find infinitely many pairs of different triples $p, q, r$ and $x, y, z$ such that
$K_{p,q,r}$ and $K_{x,y,z}$ have the same Seidel spectrum. Some examples will be given below. In fact, it was shown in \cite{Schinzel1996} that for every  positive integer $m$
there
are infinitely many sets of $m$ different primitive triples sharing the same sum and the same product   (where a triple is primitive
if the greatest common divisor of its elements is $1$).

In the remainder of this section, we mention some cases when complete tripartite graphs are $S$-determined, and some cases when they are not.

\begin{theorem}\label{casesdetermined}
In the following cases the graph $K_{p,q,r}$ is $S$-determined:
\begin{enumerate}
\item[{\rm(a)}]  $p=q=r$.
\item[{\rm(b)}]   $p,q,r$ are all powers of the same prime $a$.
\item[{\rm(c)}] $\max\{p,q,r\}$ is prime.
\end{enumerate}
\end{theorem}

\begin{proof}
Part (a) is a special case of Theorem \ref{Kpiqi}. Part (b) holds since in this case if $K_{x,y,z}$ has
the same Seidel spectrum as $K_{p,q,r}$, then $xyz=pqr$ implies that each of $x$, $y$, $z$ is a power of $a$.
Since there is a unique way to write $p+q+r$ as a sum of powers of the prime $a$, the triple $x,y,z$ is
equal to $p,q,r$.

We now prove part (c). Suppose $p\ge q\ge r$ and $p$ is prime.
If $xyz=pqr$, then $p$ divides one of $x,y,z$, say $x$. If $x=kp$, $k\ge 2$, then
\[3p\ge p+q+r=x+y+z\ge kp+2\]
implies that $k=2$. But then
\[qr=2yz ~\text{  and }~ q+r=p+y+z,\]
and thus $q\ge q+r-p= y+z\ge 2z$. This in turn implies
\[2yz=qr\ge 2zr,\]
hence $y\ge r$. We get that
\[p+y\ge q+r =p+y+z>p+y,\]
a contradiction. Thus $x=p$, and therefore the triple $p,q,r$ and the triple $x,y,z$ are identical.
\end{proof}

We now consider whether slightly weaker conditions may suffice for $K_{p,q,r}$ to be $S$-determined.
Does equality of exactly two elements in the triple $p,q,r$ suffice? Does a prime in the triple, but
not the largest, suffice? Do two primes suffice? In general, the answer to each of these questions is
negative:

\begin{example}\label{prrppr}
{\rm For every positive integer $k$ ($k$ and $2k-1$ not necessarily prime) the graphs
$K_{k(2k-1), k(2k-1), 1}$ and  $K_{(2k-1)^2, k, k}$ are Seidel cospectral, and for $k>1$ they are non-isomorphic.
Thus for every $r>1$ there exists $p>r$ such that $K_{p,r,r}$ is not $S$-determined, and
for every $r\ge 1$ there exist infinitely many non-prime $p$'s such that $K_{p,p,r}$ is not $S$-determined.}
\end{example}

To point out some cases where $K_{p,p,r}$, $p>r$, is $S$-determined, we first prove an auxiliary result.

\begin{lemma}\label{p=q>r}
Let $p>r$ and let $K_{x,y,z}$ be Seidel cospectral with $K_{p,p,r}$, where $x\ge y\ge z$ and $x,y,z\notin\{p,r\}$. Then
\[x>p>y\ge z>r \text{ and } x+y<2p.\]
Let $K_{x,y,z}$ be Seidel cospectral with $K_{p,r,r}$, where $x\ge y\ge z$ and $x,y,z\notin\{p,r\}$. Then
\[p>x\ge y>r>z \text{ and } x+y<2p.\]
\end{lemma}

\begin{proof}
let $\lambda_1\ge \lambda_2$ be the two positive Seidel eigenvalue  of $K_{p,p,r}$. By Lemma \ref{spectra3}, since $p>r$, \[2p-1\ge \lambda_1\ge 2p-1> \lambda_2> 2r-1.\]
Thus $\lambda_1=2p-1$, and $\lambda_2>2r-1$. By Lemma   \ref{spectra3},
\[2x-1\ge 2p-1\ge 2y-1\ge \lambda_2\ge 2z-1.\]
Since $2x-1, 2y-1\ne 2p-1$ the first two inequalities are strict, and hence $x>p>y$.
So $x=p+a$, $y=p-b$, with $a$ and $b$ positive integers.
As
\[p+a+p-b+z=2p+r,\]
we get that $r=z+a-b$. Thus from $xyz=p^2r$ we get
\[(p+a)(p-b)z=p^2(z+a-b),\]
implying that
\[(a-b)pz-abz=(a-b)p^2,\]
or
\[(a-b)p(z-p)=abz.\]
As in the last equality the right hand side is positive, and $z\le y<p$, we must have $a<b$, and
\[x+y=p+a+p-b<2p.\]
This in turn implies that
\[z=2p+r-(x+y)>r.\]
The proof of the second claim in the lemma is similar.
\end{proof}

\begin{theorem}\label{ababa}
Let $a$ and $b$ be  different  primes. Then $K_{ab,ab,a}$ is $S$-determined if and only if the ordered pair $(a,b)\ne (2,3)$.
\end{theorem}

\begin{proof}
For the only if note that the tripartite graph $K_{6,6,2}$ is Seidel cospectral with $K_{8,3,3}$.

Now suppose $(a,b)\ne (2,3)$.   By by Lemma \ref{p=q>r} combined with  \eqref{p+q+r} and \eqref{pqr}, the graph $K_{x,y,z}$, $x\ge y\ge z$ and $x,y,z\notin\{ab,a\}$,
is Seidel cospectral with $K_{ab,ab,a}$ if and only if
the following three conditions are satisfied:
\begin{align}
x+y+z&=2ab+a    \label{2ab+a}\\
xyz&=a^3b^2   \label{a3b2}\\
x>ab&>y\ge z>a  \label{x>ab>..z>a}
\end{align}
By \eqref{a3b2} $z$ cannot be a product of at least two primes, since otherwise $xy$ is a product of at most three primes, which cannot occur in combination with $x>y\ge z$.
Hence $z$ is a prime.
In the case that $b<a$,  $K_{ab,ab,a}$ is $S$-determined since in this case there is no prime $z>a$ which divides $a^3b^2$.
If $b>a$, then $z=b$. Then $xy=a^3b$, $x>y\ge b$, $x,y\notin\{ab,a\}$, holds
only if $x=a^3$, $y=z=b$.
By \eqref{2ab+a}, $a^3+2b=2ab+a$ , so $a^3-a=2b(a-1)$ and therefore $a(a+1)=2b$. But this last equality is satisfied only if $a=2$ and $b=3$, contrary to our
assumption. Therefore $K_{ab,ab,a}$ is $S$-determined in this case also.
\end{proof}

In the next result, we consider $K_{p,p,1}$, where $p$ is a product of two different primes.

\begin{theorem}\label{abab1}
If $p=ab$, where $a>b$ are both prime, and $K_{p,p,1}$ is not $S$-determined, then
$a=2b-1$ and the only complete tripartite graph Seidel cospectral with $K_{p,p,1}$ is $K_{a^2,b,b}$.
\end{theorem}

\begin{proof}
By the assumption and Lemma \ref{p=q>r}, there exist $x>p>y\ge z>1$ such that
$K_{x,y,z}$ is Seidel cospectral with $K_{p,p,1}$. Then
$xyz=a^2b^2$. By Lemma \ref{p=q>r}, $x>ab$, and as $y,z\notin\{ab,1\}$, $x\notin \{a^2b^2\,,\, a^2b\, ,\, ab^2\}$. Thus either $x=b^2$
or $x=a^2$. Suppose $x=b^2$. Then $yz=a^2$ and, since $y,z\ne 1$, necessarily $y=z=a$. By \eqref{p+q+r} we get
that
\[b^2+2a=2ab+1,\]
and therefore
\[b^2-1=2a(b-1),\]
implying that $b+1=2a$. But this is impossible by the assumption that $a>b(>1)$.
By the same computation, in the remaining case, that $x=b^2$, necessarily $y=z=a$ and we get that $a+1=2b$.
The graphs $K_{ab,ab,1}$ and $K_{a^2,b,b}$ do have the same Seidel spectrum when $a=2b-1$ (see also Example \ref{prrppr}).
\end{proof}

In the next result, we consider the general case that one element in the triple is $1$.

\begin{theorem}\label{pq1}
$K_{p,q,1}$ is $S$-determined if $q\le 4$. For every $q>4$ there exists a positive integer $p$ such that $K_{p,q,1}$ is
not $S$-determined.
\end{theorem}

\begin{proof}
If
\begin{align}
x+y+z&=p+q+1   \label{p+q+1} \\
xyz&=pq  ~~,\label{pq}
\end{align}
where $x\ge y\ge z$ is a triple different from $p, q, 1$, then in particular $y\ge z\ge 2$, and by
Theorem \ref{casesdetermined}(c) $x$ is not prime.
 Multiplying \eqref{p+q+1} by $q$ and substituting $pq$ by $xyz$ we get
\[q(x+y+z)=xyz+q^2+q,\]
and thus $q(y+z-q-1)=x(yz-q)$. As $y\ge z\ge 2$,  $yz\ge y+z$. Thus
\begin{equation} x(yz-q)\le q(yz-q-1).  \label{xle}\end{equation}

For the first part of the theorem, suppose on the contrary that such $x\ge y\ge z$ exist for $q\le 4$.
As $y,z\ge 2$, we have $yz\ge 4\ge q$. And $yz\ne q$, since
otherwise  in \eqref{xle} we get that $0\le -q$. Thus $yz>q$ and
\[x\le q\frac{yz-q-1}{yz-q}<q.\]
But since $q\le 4$ this means that $x$ is  prime, and we get a contradiction.

For the second part of the theorem suppose first that $q>4$ is odd, then $K_{\frac{(q-1)^2}{2},q,1}$ and $K_{q\frac{q-1}{2}, \frac{q-1}{2},2}$
have the same Seidel spectrum. This covers in particular the case that $q$ is prime.

If $q>4$ and $q=ab$, where $a>1$ and $b>2$, let $p=(b-1)(ab-a-b+2)$.
Then  $x=b(ab-a-b+2)$, $y=b-1$, $z=a$ form a triplet such that $K_{x,y,z}$ has the same
Seidel spectrum as $K_{p,q,1}$.
\end{proof}

\begin{corollary}\label{cornge 3 det}
 For any intger $n\ge 3$  there exists an $S$-determined complete tripartite graph of order $n$.
\end{corollary}

By computer check, complete tripartite graphs on $n$ vertices, $n<13$ or $n=15$ or $n=18$ are $S$-determined.
 For $n=13,14,16,17$ there exist complete tripartite graphs which are not $S$-determined. For $n=13, K_{9,2,2}, K_{6,6,1}$ are Seidel cospectral.
 For $n=14, K_{8,3,3}, K_{6,6,2}$ are Seidel cospectral.
 For $n=16, K_{9,5,2}, K_{10,3,3}$ are Seidel cospectral.
For $n=17, K_{9,4,4}, K_{8,6,3}$ are Seidel cospectral.

\begin{remark}{\rm
A natural question is for which integers $n$ there exist complete tripartite graphs on $n$
vertices that are not $S$-determined. This question was settled in an Undergraduate Research Project at
the Technion by Ramy Masalha and Eli Bogdanov \cite{MasalhaBogdanov2018}. They showed that for $n=7k-\alpha$, $\alpha\in \{1,2,3,4,5,6,7\}$, the
following two triples have the same sum  and the same product:
\[ \alpha, 3k,4k-2\alpha ~\text{ and }~ 2\alpha, k, 6k-3\alpha.\]
For $n\notin\{22,24,30,36,42\}$ these are two different triples. For the remaining values of $n$ they found the following pairs
of triples:
\begin{align*}
n=22:&\quad 9,8,5 \quad\text{and}\quad 10,6,6\\
n=24:&\quad 12,10,2 \quad\text{and}\quad 16,5,3\\
n=30:&\quad 20,7,3 \quad\text{and}\quad 21,5,4\\
n=36:&\quad 21,13,2 \quad\text{and} \quad 26,7,3\\
n=42:&\quad 24,16,2  \quad\text{and}\quad 32,6,4
\end{align*}
Thus for every $n\ge 13$,  other than $n=15$ and $n=18$, there exists a complete tripartite graph on $n$ vertices that is
not $S$-determined.
}\end{remark}

{\bf Acknowledgements}
 The authors would like to thank the anonymous referee for suggestions and comments  on the early version of this paper.


\section{Introduction}
\noindent For any two graphs $G$ and $H$, the \textit{Ramsey number} $r(G,H)$ is the smallest positive integer $n$ such that $K_n\rightarrow (G,H)$.   The \textit{classical Ramsey number} $r(s, t)$ is defined as $r(K_s,K_t)$ and the \textit{diagonal Ramsey number} is defined as  $r(K_n,K_n)$.  These numbers have been studied extensively in the last five decades. The difficulty in exact determination of \textit{diagonal Ramsey number} $r(n, n)$, swifts expeditiously from the apparent $r(3,3)=6$ to the unmanageable $r(5,5)$. Currently, the best known lower and upper bounds for $r(5,5)$ are  43 and 48 (see \cite{Ra}). Many interesting variations of the basic problem of finding  classical Ramsey numbers have emerged. One such variation  is the calculation of the number of \textit{Ramsey critical  $(G,H)$ graphs}, for any pair of graphs $(G,H)$. In this paper,  we show that there are exactly 68  Ramsey critical $r(C_n, K_6)$   graphs, for all $n$ exceeding fourteen.

\vspace{14pt}

\section{Notation}
\noindent The \textit{complete graph} on $n$ vertices, a \textit{cycle} on  $n$ vertices and a \textit{Star} on $n+1$ (see \cite{JaSa}) vertices are denoted by $K_n$, $C_n$  and $K_{1,n}$ respectively. Given a graph $G$ and a vertex $v \in V(G)$, we define the \textit{neighbourhood of $v$ in $G$},  $\Gamma(v)$, as the set of vertices adjacent to $v$ in $G$. The \textit{degree} of a vertex $v$, $d(v)$, is defined as the cardinality of  $ $ $\Gamma(v)$, $ $ i.e. $d(v)=| \Gamma(v)|$. The minimum degree of a graph $G(V,E)$ denoted by $\delta(G)$ is defined as  $ $ $ \min\{ d(v) | v\in V  \}$.

\vspace{8pt}

\noindent Given a graph $G$, we say $I \subseteq V(G)$ is an \textit{independent set}, if no pair  of  vertices of $I$ is adjacent to each other in $G$. Equivalently, $I$ forms a clique in $G^c$.  Given a graph $G=(V,E)$, we define \textit{the independence number}, $\alpha(G)$, as the size of the largest independent set. Thus, $\alpha(G)=\max \{ \left| I\right| : I$ is an independent set of $G \}$. In the special case of $H=K_m$, alternatively $r(G,K_m)$ can be viewed as the smallest positive integer $n$ such that every graph  of order $n$ either contains $G$ as a subgraph or else satisfies $\alpha(G) \geq m$. For a non-empty subset $S$ of $V$, \textit{the induced subgraph of $S$ in $G$} denoted by $G[S]$ is defined as the  subgraph obtained by deleting all the vertices of $S^c$ from $G$. For two disjoint subgraphs $H$ and $K$ of $G$, we denote the set of edges between $H$ and $K$ by $E(H,K)$.

\vspace{10pt}

\section{Lemmas used to generate  Ramsey critical $(C_n,K_6)$  graphs for $n \geq 15$}

In an attempt to prove Bondy and Erd{\"o}s conjecture  $r(C_n,K_m) = (n-1)(m-1)+1$, for all $(n,m)\neq(3,3)$ satisfying $n \geq m \geq 3$ under certain restrictions, Schiermeyer has proved that  $r(C_n,K_6) = 5(n - 1)+1$, for $n \geq 6$  (see \cite{Ra,Sc}). Characterizing all  Ramsey critical $(C_n,K_6)$ graphs boils down to  finding all (red/blue) colorings of $K_{r(C_n,K_6)-1}$ such that there is no red $C_n$ or a blue $K_6$. This is achieved by finding all $C_n$-free graphs on $K_{r(C_n,K_6)-1}$ vertices such that $\alpha(G)<6$. We first  prove that any $C_n$ -free graph (where $n \geq 15$) of order $5(n-1)$ with $\alpha(G) \leq 5$  contains a $5K_{n-1}$. To prove this, we use seven lemmas of which the first three are already proven results. For ease of reference, we reiterate Lemma \ref{l1a} from \cite{JaRo1}, Lemma  \ref{l1b} from \cite{Ja} and Lemma  \ref{l2}  by Bollob{\'a}s et al from \cite{BoJaSh}.
\vspace{10pt}

\begin{lemma}
\label{l1a}
\noindent (\cite{JaRo1}, Lemma 2; \cite{JaRo1}). A $C_n$- free graph $G$ of order $N$  with independent number  less than or equal to $m$ has minimal degree  greater than or equal to $N-r(C_n,K_{m})$.
\end{lemma}

\vspace{2pt}

\begin{lemma}
\label{l1b}
\noindent (\cite{Ja}, Lemma 8).  A $C_n$- free graph (where $n \geq 7$) of order $4(n-1)$ with no independent set of 5 vertices  contains a  $4K_{n-1}$.
\end{lemma}

\vspace{2pt}

\begin{lemma} (\cite{BoJaSh}, Lemma 5)
\label{l2}
\noindent Suppose $G$ contains the cycle $(u_1, u_2, ... , u_{n-1}, u_1)$ of length $n - 1$ but
no cycle of length $n$. Let $Y = V(G) \setminus \{u_1, u_2, ... , u_{n-1}\}$. Then,

\vspace{8pt}
\noindent \textbf{(a)} No vertex $x \in Y$ is adjacent to two consecutive vertices on the cycle.

\vspace{8pt}
\noindent \textbf{(b)} If $x \in Y$ is adjacent to $u_i$ and $u_j$ then $u_{i+1}u_{j+1} \notin E(G)$.

\vspace{8pt}
\noindent \textbf{(c)} If $x \in Y$ is adjacent to $u_i$ and $u_j$ then no vertex $x' \in Y$ is adjacent to both
$u_{i+1}$ and $u_{j+2}$.

\vspace{8pt}
\noindent \textbf{(d)} Suppose $\alpha(G) = m - 1$ where $m \leq  \frac {n + 2}{2}$ and $\{x_1, x_2, ... ,x_{m -1} \} \subseteq Y$ is an $(m - 1)$-element independent set. Then, no member of this set is adjacent to $m -2$ or more vertices on the cycle (We have taken the liberty of making a slight correction to the inequality $m \leq \frac {n + 2}{2}$ of the original \cite{BoJaSh}, Lemma 5(d)).
\end{lemma}

\vspace{12pt}

\noindent The next lemma plays a pivotal role in proving the main results of this paper.

\vspace{4pt}
\begin{lemma}
\label{l3}
\noindent A $C_n$ -free graph (where $n \geq 15$) of order $5(n-1)$ with no independent set of 6 vertices contains a $5K_{n-1}$.
\end{lemma}

\noindent {\bf Proof.} We shall assume that in each of the three cases  $n = 15$, $n = 16$ and $n \geq 17$ we consider,  $G$ as a  graph on $5(n-1)$ vertices  satisfying $C_n \not \subseteq G$ and $\alpha(G) \leq 5$. Since  $r(C_{n-1}, K_6)=5n-9 \leq 5(n-1)$ (see \cite{BoJaSh,Ra}), there exists a cycle $C=(u_1, u_2, ... , u_{n-1}, u_1)$ of length $n - 1$ in $G$. In consistent with the notation of \cite{BoJaSh}, define $H$  as the induced subgraph of $G$ not containing the vertices of the cycle $C$. Then, $|V(C)|=n-1$ and $|V(H)|=4(n-1)$.

\vspace{6pt}

\noindent Suppose  there exists an independent set $Y=\{y_1, y_2,y_3, y_4, y_5 \}$ of size 5 in $H$, so that $\alpha(G)=5$. From  Lemma \ref{l2} (as $5\leq \frac{n+2}{2}$), it follows that no vertex of $Y$ is adjacent to four or more vertices of the $C_{n-1}$. Thus, $\left| E(Y,V(C)) \right| \le 15$.  For ease of reference, we define such a graph structure as a  \textbf{Standard Configuration ($n$)}.

\vspace{10pt}

\noindent \textbf{Case 1: $n \geq 17$}

\vspace{6pt}
\noindent  Now, $\left| E(Y,V(C)) \right| \le 15 < n-1$. Thus, there exists a vertex $x\in V(C)$ adjacent to no vertex of $Y$. This gives, an independent set $Y \cup \{x\}$ of size 6, a contradiction.

\vspace{10pt}
\noindent \textbf{Case 2: $n = 16$}

\vspace{6pt}
\noindent In this case as $n-1=15$, in order to avoid an independent set of size 6, each vertex of $V(C)$ must be adjacent to at least one vertex of $Y$. Thus, we get that for each  $1\leq i\leq 5$,  $\left|\Gamma (y_i) \cap V(C) \right|=3$ and for each $1\leq j  < j' \leq 5$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$.

\vspace{10pt}

\noindent By Lemma \ref{l1a}, as $\delta(G) \geq 14$,  $\left|\Gamma (y_i) \cap V(H \setminus Y)\right| \geq 11$ for  $i=1,2$. Since $r(P_3,K_6)=11$ and $\alpha(G) < 6$, each of $G[\Gamma (y_1) \cap V(H \setminus Y)]$ and  $G[\Gamma (y_2) \cap V(H \setminus Y)]$ contains a copy of $P_3$. Thus, $P_3 \subseteq \Gamma (y_1) \cap V(H \setminus Y)$, where the $P_3$ is induced by  $\{x,y,z\}$ such that $(x,y), (y,z) \in E(G)$ and $P_3 \subseteq \Gamma (y_2) \cap V(H \setminus Y)$,  where this $P_3$ is induced by  $\{p,q,r\}$ such that $(p,q), (q,r) \in E(G)$.

\vspace{10pt}

\noindent Suppose that $x$ is not adjacent to any vertex of $\{y_2,y_3,y_4,y_5\}$ and $p$ is not adjacent to any vertex of $\{y_1,y_3,y_4,y_5\}$. Re-order the vertices of the cycle such that $y_1\in Y$ is adjacent to $u_1$. In this ordering, let $y_1$ be also adjacent to $u_t$ where $2 \leq t \leq 15$.

\begin{center}
\input{graph1.tex}
\end{center}
\begin{center}
Figure 1. Configuration for $n=16$
\end{center}

\noindent By Lemma \ref{l2}(a), $t \neq 2$. In order to avoid an independent set of size 6, induced by $\{x,u_t,y_2,y_3,y_4,y_5\}$, we get that $(x,u_t) \in E(G)$. However, $t \neq 3$, in order to avoid a  $C_{16}$ comprising $(u_1,y_1,x, u_3,...,u_{15},u_1)$. Also, $t \neq 4$ in order to avoid a $C_{16}$ comprising  $(u_1,y_1,y,x,u_4,...,u_{15},u_1)$  and $t \neq 5$ in order to avoid a $C_{16}$ comprising  $(u_1,y_1,z,y,x, u_5,...,u_{15},u_1)$.

\vspace{8pt}
\noindent Thus, any pair of vertices adjacent to $y_1$ in $C$ cannot be separated by a path of length 1, 2, 3 or 4  along $C$. Thus, $\Gamma (y_1) \cap C =\{u_1,u_6,u_{11}\}$. In this scenario, we use the prerogative that $(y_2,u_2)\in E(G)$. Then,  by the previous argument $\Gamma (y_2) \cap C =\{u_2,u_7,u_{12}\}$. But by Lemma \ref{l2}(b),  $(u_2,u_7)\notin E(G)$. Henceforth, we will get that $\{u_2,u_7,y_1,y_3,y_4,y_6\}$  is an independent set of size 6, a contradiction.
\vspace{10pt}

\noindent This implies that there is a vertex of $X=\{x,y,z\}$ adjacent to some vertex of $\{y_2,y_3,y_4,y_5\}$ or there is a vertex of $\{p,q,r\}$ adjacent to some vertex of $\{y_1,y_3,y_4,y_5\}$. Therefore, without loss of generality, we may assume that $y_1$ is adjacent to $X=\{x,y,z\} \subseteq V(H \setminus Y)$ and $y_1$ is adjacent to $X'=\{x',y',z'\} \subseteq V(C)$ where $X'$ induces a  $P_3$  and $y_2$ is adjacent to $x$. Next since $C$ has 15 points without loss of generality, $\{x',y',z'\}=\{u_1,u_3,u_5\}$ or $\{x',y',z'\}=\{u_1,u_3,u_6\}$ or $\{x',y',z'\}=\{u_1,u_3,u_7\}$  or  $\{x',y',z'\}=\{u_1,u_3,u_8\}$ or  $\{x',y',z'\}=\{u_1,u_3,u_9\}$ or $\{x',y',z'\}=\{u_1,u_4,u_7\}$ or $\{x',y',z'\}=\{u_1,u_4,u_8\}$ or $\{x',y',z'\}=\{u_1,u_4,u_9\}$ or $\{x',y',z'\}=\{u_1,u_4,u_{10}\}$ or $\{x',y',z'\}=\{u_1,u_5,u_9\}$ or $\{x',y',z'\}=\{u_1,u_5,u_{10}\}$ or $\{x',y',z'\}=\{u_1,u_6,u_{11}\}$. Moreover, as $y_1$ and $y_2$ are connected by paths of lengths 2, 3 and 4 in $H$, no pair of vertices selected from  $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. Using this  we argue that when $\{x',y',z'\}=\{u_1,u_3,u_5\}$, $\Gamma (y_2) \cap V(C) = \phi$,  when $\{x',y',z'\}=\{u_1,u_3,u_6\}$, $\Gamma (y_2) \cap V(C) = \phi$ and when  $\{x',y',z'\}=\{u_1,u_3,u_7\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_9\}$.  Similarly, when $\{x',y',z'\}=\{u_1,u_3,u_8\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_9,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_3,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_4,u_7\}$, $\Gamma (y_2) \cap V(C) = \phi$ and when $\{x',y',z'\}=\{u_1,u_4,u_8\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_{10}\}$. When $\{x',y',z'\}=\{u_1,u_4,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_3,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_4,u_{10}\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_3\}$,  when $\{x',y',z'\}=\{u_1,u_5,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_3,u_7\}$ and when $\{x',y',z'\}=\{u_1,u_5,u_{10}\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_{3}\}$ and  when $\{x',y',z'\}=\{u_1,u_6,u_{11}\}$, $\Gamma (y_2) \cap V(C) =\phi$. Since none of these give a viable configuration, we get a contradiction.

\vspace{8pt}
\noindent \textbf{Case 3: $n = 15$}

\vspace{8pt}

\noindent To deal with the case $n = 15$, we first prove three Lemmas. Lemma $\ref{l31}$, deals with the possible scenarios generated by the Standard Configuration ($15$). Lemmas $\ref{l32}$ and $\ref{l33}$ deal with showing that none of the scenarios generated by Lemma $\ref{l31}$ give viable configurations.

\vspace{4pt}

\begin{lemma}
\label{l31}
\noindent In the Standard Configuration $(n=15)$, one of the following three scenarios $(a)$, $(b)$ and $(c)$ will occur:

\vspace{8pt}
\noindent \textbf{(a)} $y_1 \in Y$ is a vertex of the subgraph $K_4$ (see Figure 2(a)) in $H$.\vspace{8pt}

\vspace{8pt}
\noindent \textbf{(b)} $y_1,y_2\in Y$ are vertices of the subgraph $K$ (see Figure 2(b1)) or subgraph $K'$ (see Figure 2(b2)) in $H$.

\vspace{8pt}
\noindent \textbf{(c)} $y_1,y_2\in Y$ are vertices of the subgraph $L$ (see Figure 2(c)) in $H$.
\end{lemma}

\begin{center}
\input{graph1b.tex}
\end{center}
\hspace{20pt} \textit{scenario (a)}                 \hspace{85pt}           \textit{scenario (b)}  \hspace{88pt}     \textit{scenario (c)}
\vspace{8pt}
\begin{center}
Figure 2: (a),(b1), (b2) and (c). The first three scenarios, \textit{scenario} (a),  \textit{scenario} (b) and \textit{scenario} (c) of the Standard Configuration $(n=15)$.
\end{center}

\noindent {\bf Proof.}
\noindent As in the case of $n=16$, we get that without loss of generality $1\leq i\leq 4$, $\left|\Gamma (y_i) \cap V(C)\right| =3$ and for each $1\leq j  < j' \leq 4$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$.
Also $\left|\Gamma (y_5) \cap V(C)\right| \in \{ 2,3\}$. In particular, if $\left|\Gamma (y_5) \cap V(C)  \right|=2$ then, for each $1\leq j  < j' \leq 5$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$ and if  $\left|\Gamma (y_5) \cap V(C)\right| =3$ then, for each $1\leq j < j' \leq 5$,
\[
\left|\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)\right|=
\begin{cases}
$ $ 1 & \text{if }  j,j' \in \{4,5\}, \\
\hspace{20pt} & \\
$ $ 0 & \text{otherwise. }    \\
\end{cases}
\]

\vspace{8pt}

\noindent By Lemma \ref{l1a}, as $\delta(G) \geq 13$, we get that $\left|\Gamma (y_i) \cap V(H \setminus Y)\right| \geq 10$.  Suppose that there is some $1\leq i\leq 3$ (say $i=1$) such that $\left|\Gamma (y_i) \cap V(H \setminus Y)\right|\geq 11$. Then as $r(P_3,K_6)=11$ we get scenario $(a)$. Next, assume that for all $1\leq i\leq 3$,  $\left|\Gamma (y_i) \cap V(H \setminus Y)\right|=10$.  By the classification of the Ramsey critical $(P_3,K_6)$ graphs, we get that for all $1\leq i\leq 3$, $G[\Gamma (y_i) \cap V(H \setminus Y)] \supseteq 5K_2$.

\vspace{8pt}

\noindent This gives  two possibilities. The first possibility is $\left|{\cup}_{i=1}^3 \Gamma (y_i) \cap V(H \setminus Y)\right|=10$. In this case, as for all $1\leq i\leq 3$, $5K_2 \subseteq G[\Gamma (y_i) \cap V(H \setminus Y)]$ we get scenario $(c)$.
The second possibility if $\left|{\cup}_{i=1}^3 \Gamma (y_i) \cup V(H \setminus Y)\right|\geq 11$. Without loss of generality, we may assume that $\left| \Gamma (y_1) \cup  \Gamma (y_2) \cup V(H \setminus Y)\right|\geq 11$.  Let $x_{11}$ be any vertex of $\Gamma (y_2)   \cap (\Gamma (y_1))^c \cup V(H \setminus Y)$. Since  $r(P_3,K_6)=11$, we get that $G[\Gamma (y_1) \cup V(H \setminus Y) \cup \{x_{11}\}]$ contains a subgraph $P$ isomorphic to a $P_3$. If  $P$ is contained in $G[\Gamma (y_1) \cup V(H \setminus Y)]$ we  get scenario $(a)$. Otherwise, $x_{11} \in P$. However, $x_{11}$ is an element of $5K_2 \subseteq G[\Gamma (y_2) \cap V(H \setminus Y)]$ and therefore, $x_{11}$ is adjacent to some other vertex say $w$ in $G[\Gamma (y_2) \cap V(H \setminus Y)]$. Depending on whether or not $w$ belongs to $V(P)$,  we get scenarios $(b2)$ or $(b1)$ respectively. Hence the Lemma.
\vspace{4pt}

\begin{lemma}
\label{l32}
\noindent In the Standard Configuration $(n=15)$,  $y_1\in Y$ can not be a vertex of a  $K_4$  in $H$ (see Figure 2(a)).
\end{lemma}

\noindent {\bf Proof.} As indicated in Figure 2(a), let  $x \in \Gamma (y_1) \cap V(H \setminus Y)$.
Then we get two possibilities depending on whether or not  $x$ is  adjacent to a vertex of $\{y_2,y_3,y_4,y_5\}$. In the first possibility,  $x$ is adjacent to some vertex of  $Y$ (say $y_2$). Then, as $y_1$ and $y_2$ are connected by paths of lengths 2, 3 and 4 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. However, as argued in $n=16$, we get that $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$ and $\left|\Gamma (y_2) \cap V(C)\right| = 2$ only when $\{x',y',z'\}=\{u_1,u_3,u_{8}\}$, $\{x',y',z'\}=\{u_1,u_4,u_{9}\}$ or $\{x',y',z'\}=\{u_1,u_5,u_{9}\}$. This gives a contradiction. In the second possibility, re order the vertices of the cycle such that $y_1\in X$ is adjacent to $u_1$. In this ordering, suppose further that $y_1$ is also adjacent to $u_t$ where $2 \leq t \leq 14$.  By the argument used in $n=16$, we get that any pair of vertices adjacent to $y_1$ in $C$ cannot be separated by a path of length 1, 2, 3 or 4  along  $C$. However, this again leads to a contradiction.
\vspace{14pt}

\begin{lemma}
\label{l33}
\noindent In the Standard Configuration $(n=15)$, the vertices $y_1,y_2\in Y$ can not be  vertices of the  subgraph $K$, $K'$ or $L$ in $H$ (see Figure 2).
\end{lemma}

\noindent {\bf Proof.} In the case $y_1,y_2 \in K$, since $y_1$ and $y_2$ are connected by paths of lengths 3, 4 and 5 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 4, 5 or 6 along the cycle $C$. The cardinality of the possible vertex sets of  $\Gamma (y_i) \cap V(C)$ ($i=1,2$), subject to this condition, are presented in Table 1.

\begin{center}
\begin{tabular}{ ||p{1.89cm}||p{4.55cm}||p{6.8cm}|| }
 \hline
\begin{center}$\{x',y',z'\}$ equals \end{center}
  &
	\begin{center}$\Gamma (y_2) \cap V(C)$ is contained in \end{center}
	&
	\begin{center}Cardinality of $\Gamma (y_2) \cap V(C)$ \end{center} \\

 \hline
$\{u_1,u_3,u_5\}$     &   $\{u_2,u_4\}$   &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$  \\
 \hline
$\{u_1,u_3,u_6\}$     &   $\{u_4\}$   &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq  1$  \\
 \hline
$\{u_1,u_3,u_7\}$     &   $\{u_4,u_{14}\}$  &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq 2$  \\
 \hline
$\{u_1,u_3,u_8\}$     &   $ $  $  $ $\phi$     &  $\left|\Gamma (y_2) \cap V(C)\right| = 0$  \\
 \hline
$\{u_1,u_3,u_9\}$     &   $\{u_{2}\}$    &  $\left|\Gamma (y_2) \cap V(C)\right| \leq  1$  \\
 \hline
$\{u_1,u_4,u_7\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$   \\
 \hline
$\{u_1,u_4,u_8\}$     &   $ $  $  $ $\phi$  &  $\left|\Gamma (y_2) \cap V(C)\right| =0$  \\
 \hline
$\{u_1,u_4,u_9\}$     &   $\{u_2\}$   &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq 1$  \\
 \hline
$\{u_1,u_5,u_9\}$     &   $\{u_2,u_8,u_{12}\}$  & $\left|\Gamma (y_2) \cap V(C)\right|  \leq  3$ \\
\hline
$\{u_1,u_5,u_{10}\}$  &   $\{u_3,u_8,u_{12}\}$  & $\left|\Gamma (y_2) \cap V(C)\right|  \leq  3$ \\
 \hline
\end{tabular}
\end{center}
\begin{center}
Table 1: Cardinality of $\Gamma (y_2) \cap V(C)$: Graph $K$.
\end{center}

\vspace{8pt}

\noindent Because  $\Gamma (y_2) \cap V(C)=3$, we are only left to deal with the last two possibilities of Table 1 for $\Gamma (y_2) \cap V(C)$. In both possibilities, $\Gamma (y_1) \cap V(C)$ will induce a $C_3$ by Lemma \ref{l2}(b). In the first possibility, $\Gamma (y_1) \cap V(C)=\{u_1,u_5,u_9\}$  gives rise to the 15-cycle given by  $(u_1,u_5,...,u_8,y_2,y,x,y_1, u_9,...,u_{14},u_1)$, a contradiction.  In the second possibility, $\Gamma (y_1) \cap V(C)=\{u_1,u_5,u_{10}\}$  gives rise to the 15-cycle given by $ (u_1,u_5,u_6,...,u_8,y_2,z,y,x,y_1,u_{10},...,u_{14},u_1)$, a contradiction.

\vspace{8pt}

\noindent In the case $y_1,y_2 \in K'$, since $y_1$ and $y_2$ are connected by paths of lengths 2, 3 or 4 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. The cardinality of the possible vertex set of  $\Gamma (y_1) \cap V(C)$ is presented in Table 2 and each of these leads to a contradiction as $\Gamma (y_2) \cap V(C)<3$

\vspace{10pt}

\begin{center}
\begin{tabular}{ ||p{1.9cm}||p{2.7cm}||p{4.7cm}|| }
 \hline
\begin{center}$\{x',y',z'\}$ equals \end{center}
  &
	\begin{center}$\Gamma (y_2) \cap V(C)$ is contained in \end{center}
	  &
	\begin{center}Cardinality of $\Gamma (y_2) \cap V(C)$ \end{center}
		\\
 \hline
$\{u_1,u_3,u_5\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$    \\
$\{u_1,u_3,u_6\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$   \\
$\{u_1,u_3,u_7\}$     &   $\{u_9\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$   \\
$\{u_1,u_3,u_8\}$     &   $\{u_2,u_9\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$    \\
$\{u_1,u_3,u_9\}$     &   $\{u_2\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$    \\
$\{u_1,u_4,u_7\}$     &   $ $  $  $ $\phi$  &  $\left|\Gamma (y_2) \cap V(C)\right| =0$    \\
$\{u_1,u_4,u_8\}$     &   $\{u_2\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$    \\
$\{u_1,u_4,u_9\}$     &   $\{u_2,u_3\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$   \\
$\{u_1,u_5,u_9\}$     &   $\{u_3,u_7\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$   \\
$\{u_1,u_5,u_{10}\}$  &   $\{u_3\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$     \\
 \hline
\end{tabular}
\end{center}
\begin{center}
Table 2: Cardinality of $\Gamma (y_2) \cap V(C)$: Graph $K'$.
\end{center}
\vspace{4pt}

\noindent In the case $y_1,y_2 \in K'$, since  $y_1$ and $y_2$ are connected by paths of lengths 2, 3, 4 and 5 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by  paths of length 3, 4, 5 or 6 along the cycle $C$. Thus, Table 2 will give us the required contradiction. Similarly,  in the case $y_1,y_2 \in L$, since  $y_1$ and $y_2$ are connected by paths of lengths 2, 3, 4, 5 and 6 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by  paths of length 3, 4, 5, 6 or 7 along the cycle $C$. As before, for all possibilities  $\left|\Gamma (y_2) \cap V(C)\right| <3$, a contradiction. Thus, lemmas 5, 6 and 7 imply that $H$ cannot have an independent set of size 5.

\vspace{8pt}
\noindent Having proved that  $H$ cannot have an independent set of size 5 in all three cases $n=15,16$ and 17,  we next continue with the main proof. Since, $H$  satisfies all conditions of Lemma  \ref{l1b}, $H$ contains a $4K_{n-1}$.

\vspace{8pt}
\noindent Next we show that $V(C_{n-1})$ induced a $K_{n-1}$. Suppose that there exists two vertices  of $V(C)$, say $v$ and $w$, such that $(v,w) \not \in E(G)$. In order to avoid a $C_n$ both $v$ and $w$ will have to be adjacent to at most one vertex of each of the four copies of $K_{n-1}$ in $H$. Moreover, any vertex of any copy of $K_{n-1}$ in $H$ will have to be adjacent to at most one vertex of another copy of a $K_{n-1}$ in $H$. Thus, each copy of a $K_{n-1}$  will have at most 5 vertices adjacent to some vertex outside that of $K_{n-1}$, in $V(H) \cup \{v,w\}$. Since $(n-1)-5 \geq 1$, we can select $x_1$ in the first $K_{n-1}$, $x_2$ in the second $K_{n-1}$, $x_3$ in the third $K_{n-1}$ and $x_4$ in the fourth $K_{n-1}$ such that $\{x_1, x_2, x_3, x_4\}$ is an independent set of size four and no vertex of $\{x_1, x_2, x_3, x_4\}$ is adjacent to any vertex of $\{v, w\}$. Hence $\{x_1, x_2, x_3, x_4, v, w\}$ is an independent set of size 6, a contradiction. Therefore, we get that any two pair of vertices of $V(C)$ are  connected by an edge. Hence, $G[V(C_{n-1})]=K_{n-1}$ as required. This $K_{n-1}$ along with the $4K_{n-1}$ contained in $H$  gives the required result.

\section{ All Ramsey $(C_n,K_6)$ critical graphs for $n \geq 15$}

\noindent We have already observed that any Ramsey $(C_n,K_6)$ critical graph will consist of a red graph containing $5K_{n-1}$, with respect to the red/blue coloring. Let $\{V_i : $ $ i \in \{1,2,...,5\} \}$ be the vertex set of  the five $K_{n-1}$ graphs.  We notice that there are two types of Ramsey $(C_n,K_6)$ critical graphs. The first type (Type1) of Ramsey $(C_n,K_6)$ critical graphs will satisfy the condition that at most one vertex of each $V_i$ is adjacent to any other vertex in $V_i^c$. The second type (Type2) of Ramsey $(C_n,K_6)$ critical graphs  will satisfy the condition that there exists a  $V_k$ for some $1 \leq k \leq 5$ such that at least two vertices of $V_k$ have neighbors in  $V_k^c$. Moreover, it is  worth noting that a  Type1 critical graph is completely determined by the structure of the external edges between $V_i$'s and not by the $\binom{n}{2}$ edges inside each of the five $V_i$'s. This fact is taken into consideration when representing the Ramsey $(C_n,K_6)$ critical graphs.
\vspace{10pt}

\noindent Each subgraph of $K_5$ generates a unique Ramsey $(C_n,K_6)$ critical graph of Type1. Thus, as illustrated in the following figure, there are 34 critical graphs ($R_i$,$ $  $1 \leq i \leq 34$) of Type1 generated by the 34 subgraphs of $K_5$.
\vspace{2pt}

\begin{center}
\input{graph81.tex}
\vspace{4pt}
\input{graph82.tex}
\vspace{4pt}
\input{graph83.tex}
\vspace{4pt}
\input{graph84.tex}
\vspace{4pt}
\input{graph85.tex}
\vspace{4pt}
\input{graph86.tex}
\vspace{12pt}

Figure 3. Ramsey $(C_n,K_6)$ critical graphs of Type1, $R_i$ ($1 \leq i \leq 34$)
\end{center}
\vspace{8pt}

\noindent First note that each and every Type2 critical graph is obtained by an appropriate vertex splitting of some Type1 critical graph. As illustrated in the Figure 4, there are exactly 34 Type2 critical graphs (labeled $S_i$ where $1 \leq i \leq 34$) generated by 18 critical graphs of Type1, since exactly sixteen Type1 critical graphs do not generate  Type2 critical graphs.

\vspace{2pt}

\begin{center}
\input{graph91.tex}
\vspace{4pt}
\input{graph92.tex}
\vspace{4pt}
\input{graph93.tex}
\vspace{4pt}
\input{graph94.tex}
\vspace{4pt}
\input{graph95.tex}
\vspace{4pt}
\input{graph96.tex}
\vspace{4pt}
\input{graph97.tex}
\vspace{4pt}
\input{graph98.tex}
\vspace{4pt}
\input{graph99.tex}
\vspace{4pt}
\input{graph910.tex}
\vspace{12pt}

Figure 4. Ramsey $(C_n,K_6)$ critical graphs of Type2 ($S_i$,  $1 \leq i \leq 34$)
\end{center}
\vspace{8pt}

\noindent Henceforth, we conclude that there are exactly 68  Ramsey $(C_n,K_6)$ critical graphs out of which 34 are  categorized as Type1 critical graphs (labeled $R_i$, $1 \leq i \leq 34$ ) and the balance 34 are categorized as Type2 critical graphs (labeled $S_i$, $1 \leq i \leq 34$).


\section{Introduction}
Semiconductor-superconductor hybrids combine coherence effects at the macroscopic scale (superconductors) with the ease of tuning by means of electric and magnetic fields (semiconductors). An ever-growing class of phenomena enabled by these hybrids include quantum phase transitions\cite{sachdev2011} such as superconductor-insulator transition\cite{han2014,mooij2015,bottcher2018} or topological superconducting transitions\cite{albrecht2016,vaitiekenas2018_2,mourik2012,das2012,deng2016,nichele2017,menard2017,zhang2018,chen2017}, gate-tunable transmon \cite{larsen2015,delange2015,casparis2017}, and proposed topological Majorana qubits \cite{aasen2016,karzig2017}. Quasiparticle poisoning\cite{aumentado2004,vanwoerkom2015,vanveen2018,zgirski2011,albrecht2017,rainis2012} presents a significant source of decoherence for hybrid and superconducting qubits\cite{martinis2009,catelani2011,sun2012,riste2013,gustavsson2016,mannila2018}. This is especially true due to lower induced gap in the semiconducting part of the heterostructure.

This article describes a method that can significantly reduce the detrimental effects of quasiparticle poisoning. Specifically, we introduce a tunable quasiparticle filter made from an InAs nanowire with an epitaxial aluminum shell on two facets\cite{krogstrup2015,chang2015,gazibegovic2017}. Such a component can provide electrical connection, with Cooper pairs as charge carriers, while keeping quasiparticle transport to a minimum between two segments of the device: one that is poisoned and another that needs to remain quasiparticle-free.

An example of a system that is in need of a quasiparticle filter is a Majorana-based topological qubit\cite{aasen2016,karzig2017}. Proposed designs of such a qubit commonly require large-scale (potentially strongly poisoned) superconducting networks connected to non-superconducting leads and smaller regions of topological superconductor hosting Majorana zero modes, which decohere as a result of the poisoning\cite{goldstein2011,rainis2012,budih2012}.

The devices under study consist of two gapless regions (metallic lead and soft-gapped proximitized nanowire) separated by a clean InAs nanowire segment with an epitaxial aluminum shell~\cite{krogstrup2015,chang2015,gazibegovic2017} with a tunable gap~\cite{mikkelsen2018,antipov2018}. To enable charge detection, the clean InAs/Al and soft-gapped regions are configured as a single island (i.e., quantum dot). By means of radio-frequency charge sensing with microsecond temporal resolution\cite{jung2012,petersson2010,barthel2010,DR2018,HQN2018}, we observe single-electron tunneling events between two zero-gapped regions while tuning the superconducting gap of the filter by electrostatic gating and applied magnetic field. Increasing the coupling of the semiconductor part of the clean nanowire segment to the superconductor, resulting in the hard gap, suppresses the single-electron tunneling events between the zero-gapped regions. At the same time, the island remains strongly coupled to the lead as revealed by observed quantum charge fluctuations.

This article is organized as follows. Section~\ref{device_and_methods} presents the description of the devices and methods. Section~\ref{DC_characterization} is dedicated to the characterization of the device using conventional lock-in techniques and radio-frequency measurements. Section~\ref{RF_charge_diagram} introduces charge stability diagrams of the studied island. Section~\ref{method} describes specific measurement and analysis protocol used to quantify the quasiparticle poisoning rate. In Section~\ref{efficiency} we use these protocols to perform analysis of the quasiparticle poisoning rate as a function of gate voltages and external magnetic field. Section~\ref{fluctuations} demonstrates evidence of quantum charge fluctuations in the device configuration characterized by low poisoning rate. Finally, summary of findings and potential applications of the quasiparticle nanowire filter are presented in Section~\ref{conclusions}.

\section{Device and experimental methods}
\label{device_and_methods}

\begin{figure}[bt]
	\includegraphics[width=0.48\textwidth]{idea}
    \caption{(a) Colorized scanning electron micrograph of one of the devices under investigation. The devices are based on an InAs nanowire (dark-grey) with epitaxial aluminum shell on two of the six facets (green). The aluminum shell is nominally 5~nm thick, but due to oxidation in contact with air we expect it to be effectively 2-3~nm thick. Red-colored regions are Ti/Au ohmic contacts. Gates are used to define and control occupancy of the two islands (yellow). NbTiN/(Au) structure (blue) emulates complex high-field--compatible superconducting network. Capacitive coupling between the islands is enhanced by a floating metallic bridge (white-colored). (b) Simplified schematic of the device. During the key measurements the barrier connecting the large island to the lead on the left side \emph{L} is fully pinched-off preventing any tunneling events on a minute timescale, meanwhile the right barrier \emph{R} is operated in the tunneling regime. The smaller island is operated as a rf charge sensor. The 40~MHz LC resonant circuit is indicated by a coil symbol.}
    \label{device}
\end{figure}

The study was performed on two lithographically similar devices, illustrated in Fig.~\ref{device}. In the following, we specify in the caption of each figure for which of the two devices (A or B) the corresponding data set was obtained. We first describe their structure from the fabrication perspective and later discuss the purpose that each element serves in our experiment.

The devices are based on an InAs nanowire with a 2~nm thick MBE-grown Al shell on two facets\cite{krogstrup2015}. The nanowire is placed on a SiO$_2$ insulating substrate, and the metallic contacts and gates are deposited using e-beam lithography. The nanowire is contacted by three Ti/Au leads (colored in red in Fig.~\ref{device}(a)), deposited after local wet etching of the Al shell using Transcene D and Ar milling to obtain ohmic contact with the semiconductor. Blue-colored 150~nm NbTiN is in electrical contact with the wire. In case of device A, NbTiN is covered by 5~nm of gold, intended as a quasiparticle trap. The nanowire, ohmic contacts, and NbTiN/(Au) structure are covered by 7~nm of ALD-grown HfO$_2$. We deposit additional Ti/Au gates on top of the oxide layer. The voltage on yellow-colored gates is controlled, while the gray-colored gate is electrically floating.

The device consists of two islands defined in the Al-covered nanowire. In the experiment, we study 1$e$ charging rates of the larger, left island, detected using the small, right island as a charge sensor\cite{jung2012,barthel2010,DR2018,HQN2018}. Charge sensing is enhanced by means of a floating gate which increases the capacitive coupling between the two islands.

The main (left) island consists of two different parts. The first one, labeled ``1$e$ region'' in Fig.~\ref{device}(b), is connected to the blue-colored NbTiN structure. This segment is gapless due to at least one of these effects: the choice of the gate voltage $V_G$ for which weakly-proximitized states in the semiconductor are highly populated\cite{antipov2018}, the intrinsic softness of the superconducting gap observed in hybrid InAs/NbTiN and Al/NbTiN structures\cite{vanwoerkom2015,gul2018} and, in case of device A, gold quasiparticle traps evaporated on top of the NbTiN structure.

The second part of the quantum dot, labeled ``filter'' in Fig. \ref{device}(b), is a nanowire covered by epitaxial Al. By applying a voltage $V_F$ to the neighboring gate, the coupling between the semiconducting wire and the superconducting shell in the segment can be tuned, effectively tuning a subgap density of states\cite{vaitiekenas2018,mikkelsen2018,antipov2018}. The Al shell of the nanowire is continuous throughout the island, which prevents the creation of an unintentional barrier dividing a single island in two.

The main island (1$e$ region and filter) is connected via gateable barriers to two normal-metal leads, one neighboring the 1$e$ region, the other neighboring the filter. Adjusting barrier gate voltages $V_L$ and $V_R$ allows us to tune the barriers to the two leads from open regime (conductance through the barrier $>$~2~$e^2/h$), to tunneling regime (conductance $\simeq$~0.5~$e^2/h$), to fully closed (tunneling times of minutes or longer).

Measurements are performed using several techniques. The differential conductance through the main island can be measured using standard lock-in techniques. Alternatively, a radio-frequency resonant circuit connected to the central lead (indicated by a coil symbol in Fig.~\ref{device}) is also used in order to perform an effective differential conductance measurement through the main or sensor island, by using rf reflectometry combined with analog homodyne demodulation. When conductance through the sensor island is suppressed, reflectometry can be used as a substitute for lock-in measurements\cite{DR2018}. Finally, when conductance through the main island is suppressed, and the sensor island is tuned to the slope of the Coulomb peak, the charge on the main island can be detected with microsecond temporal resolution\cite{DR2018}.

The experiment was performed in a dilution refrigerator equipped with a vector superconducting magnet. The mixing chamber plate of the refrigerator was at base temperature of 20~mK and, unless mentioned otherwise, no magnetic field was applied.

\section{Low frequency characterization}
\label{DC_characterization}

We first characterize the main island in our device using standard lock-in techniques or equivalent reflectometry measurements\cite{DR2018}. Figure~\ref{DC_superconducting} summarizes our findings for zero external magnetic field.

\begin{figure}[tb]
    \includegraphics[width=0.48\textwidth]{characterization}
    \caption{Tunneling spectroscopy of the superconducting gap at the left (a) and right (b) end of the main island obtained using lockin techniques. The inset text indicate the status of the left (L) and right (R) barriers. (c) Coulomb diamonds with very strongly suppressed zero bias conductance obtained by reflectometry measurements. Bottom panel shows cuts through the data at various $V_{sd}$. Data for device A.}
    \label{DC_superconducting}
\end{figure}

\begin{figure}[tb]
    \includegraphics[width=0.48\textwidth]{characterization_norm}
    \caption{Coulomb diamonds at $B = 500$~mT, in plane of the sample, not parallel to the nanowire obtained by lockin techniques. No conductance suppression occurs at low $V_{sd}$, as exemplified with the cuts presented in the bottom panel. Data for device A.}
    \label{DC_normal}
\end{figure}

Panels (a) and (b) in Fig.~\ref{DC_superconducting} characterize the superconducting gap of the 1$e$ region and the filter, respectively, by mean of tunneling spectroscopy. The tunneling spectroscopy on the left end of the main island reveals a soft gap. In contrast, the right end of the island shows a hard gap ($\Delta_0$ = 308$\pm$2~$\mu$V). We gain further insight into the properties of the 1$e$ region and the filter region in the Coulomb-diamonds measurements presented in Fig.~\ref{DC_superconducting}(c). Besides the 1$e$ periodicity of the diamonds at high DC bias, a zero bias conductance is strongly suppressed. This is shown by the cuts at different bias values in the bottom panel. The zero-bias suppression of conductance at zero magnetic field stands in contrast to the Coulomb diamonds measurement with a magnetic field of 500~mT (Fig.~\ref{DC_normal}) applied in the plane of the sample, but not along the nanowire, to suppress superconductivity in the nanowire Al shell. In this case, the Coulomb peaks have a significant height even at zero DC bias.

From the measurements presented in Figs.~\ref{DC_superconducting},~\ref{DC_normal} we conclude that at zero magnetic field the left side of the device can exchange both single electrons and (Cooper) pairs with the neighboring lead, while the right side can only exchange electron pairs. In particular the suppression of conductance at zero DC bias in Fig.~\ref{DC_superconducting}(c) can be explained as follows. Zero-bias conductance through the right end of the island can only occur if $N$ and $N+2$ occupancy of the island are degenerate and have the lowest energy. However, this never takes place since at the degeneracy point the $N+1$ occupancy has the lowest energy and can be easily reached by exchanging an electron on the left end of the island. This blockade is lifted in magnetic field (Fig.~\ref{DC_normal}), when aluminum becomes normal and both ends of the island can exchange single electrons with the leads.

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{gap}
\caption{Tunneling spectroscopy of the superconducting gap at the filtered end of the main island as a function of external magnetic field $B$ applied approximately 20$^\circ$ away from the wire direction. Bottom panel shows the extracted superconducting gap $\Delta$. The fit of Eq.~\eqref{eq_gap} to the data, presented with a solid line, was used in the further analysis of poisoning rates in the external magnetic field. Data for device A.}
    \label{gap_closing}
\end{figure}

To complete the low frequency characterization of the device, we study the superconducting gap closing on the right side of the device as a function of the magnetic field $B$ (applied in the plane of the device, approximately 20$^\circ$ away from the wire direction); Fig.~\ref{gap_closing}). Panel Fig.~\ref{gap_closing}(b) shows extracted gap size $\Delta$ as a function of $B$. The dependence $\Delta(B)$ is well described by the formula\cite{douglass1961}
\begin{equation}
    \Delta (B) = \Delta_0 \sqrt{1-(B/B_c)^2},
    \label{eq_gap}
\end{equation}
where $\Delta_0 = 308 \pm 2$~$\mu$eV is the fitted superconducting gap at zero field and $B_c=183\pm1$~mT is the fitted critical field (see Appendix \ref{Gap extraction} for more details of the fitting procedure).
These measurement will serve as a reference for study of main island poisoning at finite magnetic field in Section~\ref{efficiency}.

\section{RF charge stability diagram of the island}
\label{RF_charge_diagram}

Next, voltages of the barrier gates are adjusted to study the efficiency of the quasiparticle filter. The voltage of the left barrier gate is set below $V_L = -1$~V to prevent any tunneling into the island (see appendix \ref{Barriers_appendix}) directly into the 1$e$ region (through the barrier \emph{L} in Fig.~\ref{device}(b)). For comparison, the conductance saturates at maximum value for $V_L = 200$~mV and becomes unmeasurable at $V_L = -300$~mV. Meanwhile, the right barrier gate, neighboring the filter, is operated in the tunneling regime, in range $V_R=-80$ to $-250$~mV. The filter gate voltage $V_F$ is set to $-4$~V to create a hard gap in the filter region\cite{vaitiekenas2018}.

\begin{figure}[tb]
	\centering
	\includegraphics[width=0.48\textwidth]{1vs2e_small_final}
    \caption{Charge diagrams of the main island with the left barrier fully pinched-off at $V_L \approx -1$~V and right in the tunneling regime at $V_R \approx -180$~mV. Filter gate voltage is set to $V_F=-4$~V. Demodulated rf charge sensing signal was measured with (a) a digital multimeter and averaging time of 20~ms; (b) a waveform digitizer synchronized to 1.903 kHz sawtooth waveform applied to $V_L$, with 4 averages per line. Bottom panels of (a,b) present cuts through the data to illustrate the different periodicity of the charge-sensing staircase. (c,d) Schematic explanation of different observed periodicity of the staircase. The curved arrow follows the energy of the lowest charge state and the downward arrow in (c) represents a poisoning event. In (a,c) the poisoning time is faster than the acquisition rate allowing for the relaxation to the charge state with lowest energy, independently of its parity. In (b,d) the sweeping rate is faster than the poisoning rate an thereby the parity of the island is fixed within each horizontal cut. Data for device B.}
    \label{charge_diagrams}
\end{figure}

Figures~\ref{charge_diagrams}(a,b) present two charge diagrams of the main device as a function of two barrier gate voltages, swept in the same range but with different acquisition rates. The range within which the barrier gate voltages are changed does not significantly affect tunneling rates between the island or any of the leads. Fig.~\ref{charge_diagrams}(a) presents the rf charge-sensing signal measured with a digital multimeter and an integration time of 20 ms. The panel below the charge diagram shows a cut through the data, revealing a characteristic staircase shape\cite{likharev1999,duncan1999}. Each step indicates a charge degeneracy point at which a single electron is added or removed from the island, while plateaus indicate that the charge is fixed.

Figure~\ref{charge_diagrams}(b) shows the same meaurement taken at a faster rate. We apply a 1.903 kHz sawtooth waveform to $V_L$ and measure the charge sensing signal using synchronized waveform digitizer~\cite{stehlik2015}. Each row in the data is an average over 4 periods of the sawtooth. In this way, every row is acquired within 2~ms and averaging time per point is 22~$\mu$s. An example of a single row (cut through the data) is shown in the bottom panel. With the increased acquisition rate, we observe irregular switching between two staircase shapes offset by half a period relative to each other and with twice the period of the staircase in Fig.~\ref{charge_diagrams}(a) (as illustrated with dashed vertical lines).

The contrast between these two datasets makes evident that the poisoning occurs at the timescale between the acquisition time of the data in panels (a) and (b), i.e., tens of milliseconds (corresponding to switching rate of hundreds of $s^{-1}$). Meanwhile the doubled periodicity of the staircase in Fig.~\ref{charge_diagrams}(b) establishes that the tunneling rate of the electron pairs remains much larger than the sawtooth frequency of 1.903 kHz. We dedicate the remainder of the paper to quantifying 2$e$-switching and 1$e$-switching (poisoning) rates as a function of various control knobs. Large tunability of these rates and orders-of-magnitude difference between them are the key findings of this work.

\section{Quantifying poisoning rate}
\label{method}

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{switching}
    \caption{Example of time traces used in the analysis of the switching rate. The two-dimensional color map shows the time vs gate charge signal corrected from its slope (caused by the slope of the sensor's Coulomb peak) to reveal individual charge steps. The bottom panel shows the gate dependence of time-averaged rf charge sensing signal. The right panel shows selected time traces extracted from the main two-dimensional color plot, for values of $V_L$ indicated with dotted lines and triangular markers. Data for device B.}
    \label{switching}
\end{figure}

To quantify the poisoning rate and 2$e$-switching rate the voltage on the filter gate $V_F$ and right barrier gate $V_R$ was fixed while keeping the left barrier gate $V_L$ at a large negative voltage, ranging between $-1$ and $-5$~V. Next, $V_L$ was varied within a small range over which the occupancy of the main quantum dot changed by only a few electrons, thus using the barrier gate as a plunger in that instance. For each value, we acquired a time trace of the signal from the rf charge sensor\cite{HQN2018} as illustrated in Fig.~\ref{switching}, which shows 6-ms long time traces for $V_F=-2$~V and $V_R=-270$~mV. For most values of $V_F$ the occupancy of the dot was stable, with the exception of the vicinity of charge transitions, which showed 1$e$ switching. Time traces obtained at the charge transition and in the stable region are presented in the right panel of Fig.~\ref{switching}. The corresponding values of $V_L$ are indicated with triangular markers in the bottom panel.

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{analysis}
    \caption{(a) Histograms of rf charge sensing signal for $V_R=-270$~mV, $V_F=-2$~V and $B=0$~mT at two different values of $V_L$ (in blue, before the charge transition and in red, after the charge transition). (b) Probability of finding an island in certain charge state in the vicinity of the charge transition. Solid and dashed lines are fit of the Eq.~\eqref{charge_transition_shape} to the data. (c) Histograms of the waiting times $\Delta t$ between subsequent poisoning events. Triangles pointing up/down indicate electrons tunneling into/out of the island. Solid lines are exponential fits to the data. (d) Switching rates in the vicinity of the charge transition extracted from the exponential fits as in (c). Dotted line indicates $\Gamma=\Gamma_{\rm in}(V_L)=\Gamma_{\rm out}(V_L)$. Colored markers in (b,d) indicate $V_L$ corresponding to data sets in (a,c). Data for device B.}
    \label{analysis}
\end{figure}

We focus on voltages $V_L$ in the vicinity of the charge transition and analyze the corresponding time traces in two ways. First, for each voltage $V_F$ we generate a histogram of the rf charge sensor measurements. The resulting distribution is typically bimodal, as shown in Fig.~\ref{analysis}(a), and well fit by a double gaussian. The two modes correspond to two occupancies of the main island differing by one electron. As demonstrated in Fig.~\ref{analysis}(b) the counts shift between the two modes across a charge transition. We model the probability of detecting charge states $N$ and $N+1$ by a thermal occupation of the island
\begin{align}
	P_{N} &= \frac{e^{-(N - N_g)^2 E_c/k_B T}}{e^{-(N - N_g)^2 E_c/k_B T} + e^{-(N+1 - N_g)^2 E_c/k_B T}}, \nonumber \\
    P_{N+1} &= 1-P_N,
    \label{charge_transition_shape}
\end{align}
where $N_g = \alpha(V_L-V_L^0)$ is a gate-induced charge, with lever arm $\alpha$ and $V_L^0$ voltage offset; $E_c$ is the island charging energy, $k_B$ is the Boltzmann constant and $T$ is the electron temperature. The two parameters fit ($V_L^0 = 5025.509\pm 0.005$~mV and $\alpha E_c/k_B T = 0.486 \pm 0.005$ mV$^{-1}$) results in a very good agreement with the data.

We now study the characteristic poisoning time. Fig.~\ref{analysis}(c) presents the histogram of time differences between consecutive switches. In both cases the distribution of time between switching events is exponential. In this way, statistics of switching for a specific $V_L$ can be fully characterized by a rate of the electron tunneling in ($\Gamma_{\rm in}$) and out ($\Gamma_{\rm out}$).
Figure~\ref{analysis}(d) presents the change of the tunneling rates across the charge transition. To analyze the filter efficiency we need to exclude poisoning protection by charging energy\cite{HQN2018}. As a poisoning measure we choose a switching rate at gate voltage $V_L$ for which $\Gamma_{\rm in} = \Gamma_{\rm out} \equiv \Gamma$, indicated by a dotted line in Fig.~\ref{analysis}(d). The analysis described in this section underlies each of the $\Gamma$ measurements in the following discussion.

\section{Filter efficiency}
\label{efficiency}

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{pincher_final}
    \caption{(a) Differential conductance through the right barrier of the main island, with the left barrier fully opened, as a function of $V_R$ and $V_F$ at $V_{sd}=0$, measured by means of rf reflectometry. (b) Dependence of the poisoning rate on $V_R$ for various filter gate voltages $V_F$ and for fully closed $V_L$. The corresponding regions in gate voltage space are indicated by vertical lines in (a). The inset shows the physical mechanism of quasiparticle filtering. When the filter is off (red-framed inset) an incident electron from the right lead needs only to tunnel through the barrier to poison the island. When the filter is on (blue-framed inset) an electron needs to tunnel through both: barrier and 1~$\mu$m-long superconducting region with gap $\Delta$. The raw data behind the points indicated with circles of respective color was analyzed also with an alternative method, as described in Sec.~\ref{fluctuations}. Data for device B.}
    \label{pincher-plunger}
\end{figure}

Having established a quantitative measure of the poisoning rate, we study its dependence on the filter gate $V_F$ and the right barrier gate voltage $V_R$. One should note that the voltages indicated for the different gates at a given conductance value can vary between measurements due to hysteresis, as explained more thoroughly in figure \ref{hysteresis} in the Appendix. We correlate poisoning rates with conventional zero-bias DC measurements of NIS junction at the position of right barrier gate. Figure ~\ref{pincher-plunger}(a) presents the conductance through the NIS junction as a function of $V_F$ and $V_R$, measured by rf reflectometry. For most negative $V_F$, between $-4$ to $-1.5$~V, there is a weak dependence on $V_F$, aside from a weak cross-talk effect resulting in a small negative slope. For $V_F$ between $-1.5$ and 0~V, we observe a smooth step, lowering the voltage for a complete pinch-off using $V_R$ by approximately 50~mV. For $V_F$ above 0~V, the right barrier voltage must be significantly more negative to fully block conductance through the NIS junction.
The nearly vertical features seen at more positive $V_F \approx 0$ can be attributed to an unintentional quantum dot in the barrier\cite{deng2016,lai2019}.

Our interpretation of the data between $V_F = -4$ and $-1$~V is that the semiconducting part of the wire below the filter gate is maximally depleted, and strongly coupled to the superconductor\cite{chang2015,vaitiekenas2018,mikkelsen2018,antipov2018,winkler2018}. For more positive $V_F$, carriers are accumulated in the semiconductor.

We find that quasiparticle tunneling rates agree with this interpretation. Fig.~\ref{pincher-plunger}(b) presents the tunneling rates $\Gamma$ obtained at the charge degeneracy points for several values of $V_F$ and $V_R$. Colored lines in Figure~\ref{pincher-plunger}(a) indicate corresponding positions in the color map. For all values of $V_F$ tunneling rates decrease with decreasing voltage $V_R$. This dependence can be easily understood considering that the barrier gate voltage $V_R$ changes the transparency of the NIS junction and suppresses quasiparticle poisoning. However, this suppression also reduces the probability of Andreev reflections and does not result in quasiparticle-filtering properties. On the other hand, decreasing the filter gate voltage $V_F$ disproportionately affects 1$e$ tunneling rate. As demonstrated in Fig.~\ref{pincher-plunger}(b), the single electron tunneling rate for $V_F =-2$~V is below 200 s$^{-1}$ in the entire studied range of $V_R$, between $-$180 and $-$120~mV (for more positive $V_R$ the charge sensing signal disappears due to strong 2$e$ quantum fluctuations, see Sec. \ref{fluctuations}). To achieve the same tunneling rate with $V_F = 0$, $V_R$ has to be decreased to $-250$~mV. As illustrated with colored lines in Fig.~\ref{pincher-plunger}(a), this is a disproportional change relative to the 50~mV shift of the pinch-off curve between $V_F=-2$ and 0. At the same time, a decrease of $V_F$ from $-2$ to $-4$~V has virtually no impact on the poisoning rates, consistent with reaching a maximum in the proximity coupling of semiconducting states \cite{mikkelsen2018,antipov2018,winkler2018}.

Our interpretation of these observations is illustrated in the insets of Fig.~\ref{pincher-plunger}(b). When the voltage {$V_F  < -2$~V}, the semiconductor of the gated nanowire segment is depleted sufficiently to have a hard gap and in order to poison the island quasiparticles must tunnel through a 1~$\mu$m long region with gap $\Delta$ (blue-framed inset). On the other hand, when $V_F\geq$ 0 the semiconductor is not depleted and quasiparticles only have to tunnel through the barrier junction (red-framed inset).

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{B_sweep}
    \caption{Field dependence of the poisoning rate for $V_F=-2$~V, $V_R=-360$~mV. The dahsed line is a model fit to the data using the field dependence of the superconducting gap $\Delta(B)\propto 1/\xi(B)$ fitted to the data in Fig.~\ref{gap_closing}(a). For description of the model see the main text. The inset shows the poisoning rates as a function of superconducting gap size $\Delta(B)$. Data for device A.}
     \label{B_sweep}
\end{figure}

Next we study whether applying an external magnetic field influences the poisoning rate. Figure~\ref{B_sweep} shows the magnetic field dependence of the poisoning rate for $V_F=-2$~V and $V_R=-360$~mV in device A (different from the one discussed in Fig. \ref{pincher-plunger}). The poisoning rate increases as the magnetic field that suppresses the gap of the filter.

We model poisoning processes as limited by single-particle tunneling through the filter,
\begin{equation}
	\Gamma = Ae^{-L/\xi(B)},
\end{equation}
where $A$ is the tunneling rate excluding the superconducting filter and $L=1$~$\mu$m is the length of the quasiparticle filter. The magnetic field dependence of the coherence length $\xi(B)$ can be modeled within BCS theory as $\xi(B)=\hbar v_F/\pi\Delta(B)$ where $v_F$ is the Fermi velocity and $\Delta(B)$ is obtained from the DC measurement in Fig.~\ref{gap_closing}(a). Specifically we use the relation $L/\xi(B)=\Delta(B)/b$, where $b$ is a fit parameter (with $b=v_F/\pi L$ for clean case in BCS theory). Using this model and data from Fig.~\ref{gap_closing}(b) we fit the field dependence of $\Gamma$ in Fig. \ref{B_sweep}. We find that $A=66\pm28 \times 10^6$~s$^{-1}$ and $b=26\pm1$~$\mu$eV yields a good matching with the data for poisoning rates ranging two orders of magnitude. The value of $b$ is significantly larger than $k_B T \approx 4$~$\mu$eV, which suggests that the field-dependence of the tunneling rate cannot be explained by thermally activated quasiparticles crossing the filter but rather by quantum tunneling. The corresponding coherence length is $\xi(0) = 90 \pm 10$~nm, taking into account a 50~nm uncertainty in the length of the filter (accounting for the size of the barrier gates). This value of $\xi$ at zero magnetic field is one order of magnitude smaller that that of bulk Al (1600~nm) and a factor of 2-3 smaller than the inferred coherence length in topological regime in Ref. \cite{albrecht2016} and Ref.{albrecht2017} (260~nm), and Ref. \onlinecite{vaitiekenas2018_2} (180~nm).

\section{Quantum charge fluctuations in presence of quasiparticle filtering}
\label{fluctuations}

In this section, we demonstrate that the quasiparticle filter allows maintaining a low poisoning rate while simultaneously having strong coupling to the lead, as indicated by transition broadening due to 2$e$ quantum charge fluctuations.
For that purpose, we reanalyze two of the data sets, adjusted to have comparable poisoning rates but corresponding to different settings of the barrier gate voltage $V_R$. To achieve comparable poisoning rates, the data set in the regime of active filter (filter on) is operated with the right cutter in the open regime while for the other data set, in the filter-off regime, the right cutter is almost closed. The two parameter regimes are indicated by the encircled data points in Fig.~\ref{pincher-plunger}.

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{histograms}
    \caption{Charge steps measured with quasiparticle filter on (a,c) and off (b,d). Panels (a,b) show the averaged time traces, as in Fig.~\ref{switching}, fitted by formula in Eq.~\eqref{q-thermal}. Panels (c,d) show histograms of charge sensing signal, as in Fig.~\ref{analysis}(a), as a function of $V_L$. Data for device B.}
    \label{histograms}
\end{figure}

Time-averaged charge sensing signal for these two data sets is presented in Fig.~\ref{histograms}(a,b) as a function of $V_L$ with green points. In both cases, we observe a characteristic staircase shape. However, the steps are much more pronounced when the filter is ``off'' relative to the filter ``on'' configuration. In both cases the periodicity corresponds to a 1$e$ charging effects. In the following we test the consistency of the data with an exclusively thermal broadening of the charge transitions. Below we demonstrate that this model holds well in the filter ``off'' case but fails in the filter ``on'' case.

For purely thermal broadening the time averaged charge is given by the thermodynamic expectation value,
\begin{equation}
    \langle Q \rangle = e\times\frac{ \sum\limits_{n}
            n \exp \left(-(n-N_g)^2 E_c/k_B T \right)
            }{\sum\limits_{n}
            \exp \left(-(n-N_g)^2 E_c/k_B T \right)}.
    \label{q-thermal}
\end{equation}
Taking the charge sensor sensitivity and direct crosstalk between gate $V_L$ and the sensor into account, a fit of Eq.~\eqref{q-thermal} to the data yields $E_c / k_B T = 6.3\pm1.0$ and $11.7\pm1.0$ for filter ``on'' and ``off'' case, respectively. The result is plotted in Fig.~\ref{histograms}(a,b) with black dotted lines.

Next, we generate histograms of charge sensor measurements separately for each of the time traces taken at different $V_L$, as in Sec.~\ref{method} and Fig.~\ref{analysis}(a). The histograms for various $V_F$ are plotted as a colormap in Fig.~\ref{histograms}(c,d). In the filter off case the distribution is unimodal, except in the vicinity of the charge transition. We attribute this to the stability of a single charge state whenever Coulomb blockade suppresses poisoning. Meanwhile, when the filter is on, the distribution is always bimodal, corresponding to two distinct charge states. From this we conclude that the two lowest charge states must always differ in energy by not much more than $k_B T$, otherwise the probability of finding the system in the excited state would be negligible. This corroborates the factor-of-two difference in $E_c / k_B T$ obtained from the fit in Figs.~\ref{histograms}(a,b).

More intriguingly, the mode corresponding to the excited state never disappears. Instead, the mode corresponding to a charge state $N$ \emph{continuously} shifts to a position corresponding to a charge $N\pm2$. We consider two alternative explanations of these superimposed and shifted 2$e$ steps. First, it is possible that the 2$e$ tunneling rate exceeds significantly the temporal resolution of the charge sensor while 1$e$ tunneling rate is within our temporal resolution. In such case, we detect the time-averaged charge with fixed parity. Alternatively, it is possible that we observe quantum charge fluctuations, that cause the charge of the island to be non-integer\cite{feigelman2002,lutchyn2016,jezouin2016}.

\begin{figure}[tb]
	\includegraphics[width=0.48\textwidth]{hybrydization}
    \caption{Extracted positions and amplitudes of peaks of histograms presented in Fig.~\ref{histograms}(c). The solid line is the model of quantum charge fluctuations  fitted to the data. Superconducting gap $\Delta=0.3$~meV and charging energy $E_c=0.08$~meV used in the model were measured independently. The simultaneous fit of the two presented curves yields a reflection coefficient of $r = 0.10 \pm 0.04$. Dashed and dotted lines present predictions of the thermal model (see text) for $E_c/k_B T=$1.7 and 6.3, respectively. Data for device B.}
    \label{hybridzation}
\end{figure}

To distinguish between those possibilities we process the data in Fig.~\ref{histograms}(c) by fitting double gaussian distributions to each of the histograms to obtain charge sensing signal corresponding to both detected charge states as well as probability of detecting each of them. The result of this procedure is plotted in Fig.~\ref{hybridzation} and tested against the two hypothesis.

To test the hypothesis of thermal broadening, we fit Eq.~\eqref{q-thermal} using only $n$-even or only $n$-odd, simultaneously to the positions of the two modes. Leaving $E_c/k_B T$ free allows for a good fit to the data, presented with the dashed line in Fig.~\ref{hybridzation}. However, the obtained value of $E_c/k_B T = 1.7 \pm 0.2$ is a factor of 4 smaller than the value $E_c/k_B T = 6.3 \pm 0.7$ obtained earlier \emph{for the same data set} from the fit in Fig.~\ref{histograms}(a). Alternatively, a fixed value of $E_c/k_B T = 6.3$ results in a poor agreement with the data, presented with the dotted line in Fig.~\ref{hybridzation}. We conclude that the observed behavior can not be explained in terms of thermal broadening.

For a description of quantum charge fluctuations we employ the model developed in Ref.~\onlinecite{lutchyn2016} to quantify the coupling strength between the island and the normal lead. The main island of our device is treated as a superconductor coupled to a normal lead. The coupling strength is then quantified in terms of the normal reflection coefficient $r$ at the interface. Assuming that the coupling is to a single-channel, for $r \ll 1$ the ground state energy of the island is then given (to the second order in $r$) by:
\begin{equation}
    E_{GS} = -\sqrt{E_c \Delta r} \cos(\pi N_g) - E_c r^2 \ln \left(\frac{E_c}{\Delta} \right) \cos^2 \left(\pi N_g \right)
\end{equation}
where $\Delta_0$ is the superconducting gap of the filter at $B=0$ and $E_c=0.08$~meV is the bare charging energy of the island (not taking into account the renormalization due to quantum fluctuations). $E_c$ is extracted from several Coulomb diamonds measurements in both normal and superconducting state of the Al shell. This model predicts\cite{lutchyn2016} the mean charge of the island to be
\begin{equation}
    Q(N_g) = e N_g - \frac{e}{2 E_c} \frac{\partial E_{GS}}{\partial N_g}.
\end{equation}

As previously, we supplement this formula with the charge sensor sensitivity and direct crosstalk between gate $V_L$ and the sensor. Next, we perform simultaneous fits of $Q(N_g)$ and $Q(N_g+1)$ to the extracted positions of the two modes. The result is plotted in Fig.~\ref{hybridzation} with a solid line. The fit yields a normal reflection coefficient of $r=0.1 \pm 0.04$, corresponding to dimensionless conductance $g = 1- r^2 = 0.99 \pm 0.01$. This value for the conductance indicates that in the filter ``on'' case, the coupling to the lead is very strong while still keeping very low poisoning rates.

We note that the close to perfect transmission obtained from the single-channel fit indicates that while quantum charge fluctuations are strong the single-channel model likely does apply in our experiment. Instead, the island is rather to be coupled to multiple channels in the normal leads. To the best of our knowledge there is no analytical formula for the expected scenario that includes more than the first order approximation in $1-g$. However, we do not expect the charge steps to take significantly different shapes from the one assumed above.

\section{Conclusions}
\label{conclusions}

To summarize, we studied the poisoning rate of gapless states in a nanowire island that are separated from a quasiparticle reservoir (normal lead) by a hard-gap superconducting segment of the island (filter). By means of radio-frequency charge sensing, we directly probe the poisoning events.

Poisoning rates that are consistent with tunneling through a 1~$\mu$m long (length of our quasiparticle filter) barrier of the height of the induced superconducting gap $\Delta(B)$. The efficiency of the filter is highly tunable by electrostatic gating of the filter section. The single electron tunneling rates can be made lower than $\Gamma=200$~s$^{-1}$. In the same configuration, we observe strong 2$e$ quantum charge fluctuations between the island and the lead.
Moreover, according to our interpretation, the quasiparticle poisoning rate could be exponentially suppressed by increasing the length of the quasiparticle filter.

These results demonstrate that a quasiparticle filter based on the tunability of the superconducting gap has been realized.

\section*{ACKNOWLEDGEMENTS}

We thank S. Upadhyay for contributions to device fabrication and F. Kuemmeth for contributions to the experimental setup. We also thank R. Lutchyn for fruitful discussions.

Research was supported by Microsoft, the Danish National Research Foundation, and the European Commission.