§ GRAPH ISOMORPHISM GAME

In this section, we show the collapse of communication complexity for some perfect strategies for the graph isomorphism game.
In the coming subsections, after presenting the definition of the game in [Subsection]subsec:definition-of-graph-isom-game,
we prove a key preliminary result in [Subsection]subsec:preliminary-result-for-graph-isom-game,
then we introduce the new family of symmetric strategies in [Subsection]subsec:symmetric-strategies,
and finally we state and prove our main theorems of this section in [Subsections]subsec:link-with-communication-complexity and <ref>.

§.§ Definition of the Game

The graph isomorphism game was introduced by Atserias, Mančinska, Roberson, Šámal, Severini, and Varvitsiotis in <cit.>.
This is a nonlocal game based on two graphs, namely $\G$ and $\H$, in which the players Alice and Bob try to pretend to a referee that the two graphs are isomorphic in the classical sense. Recall that $$ is said \emph{isomorphic} to $$̋, denoted $\G\cong\H$, if there exists a bijection $φ$ from the vertex set $V()$ to the vertex set $V()̋$ such that adjacency is preserved in both ways:
\begin{equation}  \label{eq:def-of-a-graph-isomorphism}
\forall g,g'\in\G, \quad\quad
g \sim g'
\quad\Longleftrightarrow\quad
\varphi(g)\sim\varphi(g')\,,
\end{equation}
where the symbol ``$∼$'' denotes the adjacency relation.

The game consists in the following. The referee provides the players Alice and Bob with respective questions $x_A,x_B∈V=V()∪V()̋$, where $V()$ and $V()̋$ are assumed to be disjoint. In return, Alice and Bob use a predetermined strategy $$ in order to produce some vertices $y_A,y_B∈V$, and they send $y_A,y_B$ to the referee, who finally verifies if the players won the game.
The first condition they need to satisfy is that $x_A$ and $y_A$ have to be in different vertex sets, and similarly for $x_B$ and $y_B$, meaning that
\begin{equation} \label{eq:rule-1-of-graph-isom-game}
x_A\in V(\G) \Leftrightarrow y_A\in V(\H)
\quad\quad\text{and}\quad\quad
x_B\in V(\G) \Leftrightarrow y_B\in V(\H)\,,
\end{equation}
otherwise they lose the game. Now, assuming that this condition holds, only one vertex among $x_A$ and $y_A$ is in $V()$, let us call it $g_A∈V()$, and the other $h_A∈V()̋$, and similarly for $g_B∈V()$ and $h_B∈V()̋$.
The second condition for Alice and Bob to win the game is that $g_A$ has the same relation to $g_B$ as $h_A$ has to $h_B$, that is the three following equivalences are satisfied:
\begin{equation}
g_A = g_B \Leftrightarrow h_A = h_B\,,
\quad\quad
g_A \sim g_B \Leftrightarrow h_A \sim h_B\,,
\quad\quad
g_A \not\simeq g_B \Leftrightarrow h_A \not\simeq h_B\,,
\end{equation}
where the symbol ``$≄$'' means neither equal nor adjacent.\footnote{\label{footnote:the-inputs-are-not-necessarily-in-G}In this work, we use the original definition from~\cite{AMRSSV19}. There exists a simpler variant of the graph isomorphism game, in which $x_A$ and $x_B$ are always given in $V(\G)$. As explained in \cite[Remark~2.3]{Roberson-Schmidt-21}, in the classical and quantum settings, if the graphs $\G$ and $\H$ are assumed to have the same number of vertices, then this simpler version is equivalent to the original version, but they differ in the non-signalling setting. Notably, we will need throughout this manuscript a characterization of perfect non-signalling strategies in terms of common equitable partition and fractional isomorphism, which holds only in the original setting.} The game is described in terms of the types of strategies that the players are allowed to use. For instance, in the \emph{quantum graph isomorphism game}, Alice and Bob can use quantum strategies to produce $y_A,y_B$ out of $x_A,x_B$, and similarly for the other types of strategies described in \refprop[Figure]{fig:famous-types-of-strategies}. It is possible to prove that if there exists a perfect strategy for this game, then the graphs $\G$ and $\H$ have to have the same number of vertices, see~\cite[page~302]{AMRSSV19}.

If the graphs $\G$ and $\H$ are actually isomorphic, with bijection $\varphi$, Alice and Bob can perfectly win the game by simply answering $h_A=\varphi(g_A)$ and $h_B=\varphi(g_B)$. Conversely, assume that this game admits a perfect deterministic strategy, in the sense of the definition in \refprop[Figure]{fig:famous-types-of-strategies}, then the deterministic behavior of Alice to produce $h_A$ out of $g_A$ defines an isomorphism between the graphs $\G$ and $\H$. As a result, the isomorphism $\G\cong\H$ holds if and only if Alice and Bob can perfectly win the deterministic isomorphism game. More generally, we can extend this result by convexity to the set of classical strategies $\L$, and we have again that $\G\cong\H$ if and only if Alice and Bob can perfectly win the classical isomorphism game.

Now, even if $\G$ and $\H$ are not isomorphic, Alice and Bob can try to mimic it to the referee, using their nonlocal box to correlate the answer. We say that $\G$ and $\H$ are quantum isomorphic, denoted $\G\cong_q\H$, if Alice and Bob can perfectly win the game using quantum strategies; and similarly $\G$ and $\H$ are non-signalling isomorphic, denoted $\G\cong_{ns}\H$, using non-signalling strategies, in the sense as described in \refprop[Figure]{fig:characterizations-of-the-different-types-of-isomorphism}, see also~\cite{AMRSSV19} for details. These equivalence relations are a relaxed version of the usual isomorphism $\cong$ in the sense that:
\G\cong\H
\quad\Longrightarrow\quad
\G\cong_q\H
\quad\Longrightarrow\quad
\G\cong_{ns}\H \,.
Man\v{c}inska and Roberson proved that, surprisingly, quantum isomorphism is characterized in terms of counting homomorphisms from planar graphs~\cite{MR20}, and with a larger team they showed that non-signalling is equivalent to fractional isomorphism~\cite{AMRSSV19}. These two results, in addition to many others, are summarized in \refprop[Figure]{fig:characterizations-of-the-different-types-of-isomorphism}.
For the sake of completeness, we recall that the adjacency matrix $A_\G$ of a graph $\G$ with $n$ vertices $g_1,\dots,g_n$ is an $n\times n$ matrix defined using the set of edges of $\G$, where the coefficient $a_{ij}$ of the matrix is set to $1$ if $g_i\sim g_j$, and to $0$ otherwise. The notion of graph homomorphism will be recalled in \refprop[Section]{section:graph-homomorphism-game}.
Note also that Reference~\cite{AMRSSV19} gives examples of graphs $\G,\H$ such that $\G\cong_q\H$ but $\G\not\cong\H$, and others such that $\G\cong_{ns}\H$ but $\G\not\cong_q\H$, and they prove that the problem of determining whether $\G\cong_q\H$ is undecidable.
Other related results may be found in~\cite{CY23,FWM23}.

\begin{figure}[h]
\footnotesize
\centering
$\begin{array}{| c | c | c |}
\hline
\rowcolor{gray1}
\textbf{\small \vspace{0.5cm}Isom.\vspace{0.5cm}} & \textbf{\small Adjacency matrices} & \textbf{\small Homomorphism countings} \\
\hline
\hline
\G \cong \H &
\begin{matrix}
\exists \text{ permutation matrix $u$}\\
\text{s.t. $A_\G u = u A_\H$~\cite[Lem~3.1]{AMRSSV19}} \\
(\text{equiv.: } \exists \text{ quantum permutation matrix $u$} \\ \text{with commuting entries}\\
\text{s.t. $A_\G u = u A_\H$ \text{ \cite[Thm~II.1]{MR20}} })
\end{matrix}
\begin{matrix}
\bullet~\forall \text{ graph } \K,\\
\# \Hom(\K, \G) \!=\! \# \Hom(\K, \H)
\text{ \cite[Eq~(5)]{Lovasz67}}\\
\bullet~\forall \text{ graph }\K,\\
\# \Hom(\G, \K) = \# \Hom(\H, \K)
\text{ \cite{CV93}}
\end{matrix}\\
\hline
\G \cong_{q} \H &
\begin{matrix}
\exists \text{ quantum permutation matrix $u$}\\ \text{s.t. $A_\G u = u A_\H$ \cite[Thm~4.4]{LMR20} }
\end{matrix}
\begin{matrix}
\forall \text{ planar graph }\K,
\\
\# \Hom(\K, \G) = \# \Hom(\K, \H)
\\
\text{ \cite[Main~Thm]{MR20}}
\end{matrix}
\\
\hline
\begin{matrix}
\G \cong^{D}_{ns} \H \\
\text{[new, \refprop[Sec.]{section:vertex-distance-game}]}
\end{matrix}
\begin{matrix}
\exists \text{ bistochastic matrix $u$}\\
\text{s.t. $A^{(t)}_\G u = u A^{(t)}_\H$ $\forall t\leq D$~[new, \refprop[Thm.]{thm:Characterization-of-perfect-NS-strategies}]}\\
\text{(i.e. $D$-fractionally isomorphic)}
\end{matrix}
\text{\large?}
\\
\hline
\G \cong_{ns} \H
\begin{matrix}
\exists \text{ bistochastic matrix $u$}\\
\text{s.t. $A_\G u = u A_\H$ \cite[Thm~4.5]{AMRSSV19}}\\
\text{(i.e. fractionally isomorphic)}
\end{matrix}
\begin{matrix}
\forall \text{ tree }\K,
\\
\# \Hom(\K, \G) \!=\! \# \Hom(\K, \H) \text{ \cite[Thm 1]{DGR18}}
\end{matrix}
\\
\hline
\end{array}$
\caption{Characterization of different types of isomorphism.}
\label{fig:characterizations-of-the-different-types-of-isomorphism}
\end{figure}

\subsection{Key Ideas}
\label{subsec:preliminary-result-for-graph-isom-game}

In this subsection, we work on a simple case to present the key ideas that will be generalized in the theorem of \refprop[Subsection]{subsec:link-with-communication-complexity}. The assumption here is that $\H$ admits exactly two connected components that are both complete.

\begin{definition}   \label{def:graph-and-diameter}
We denote by $\C_n$ the \emph{cycle} of size $n\geq1$, \ie the finite undirected graph with vertices $v_1,\dots,v_n$ and edges $v_i\sim v_{i+1}$ for $1\leq i\leq n-1$ and $v_n\sim v_1$.
We denote by $\K_n$ the \emph{complete graph} of size $n\geq1$, \ie the finite undirected graph with vertices $v_1,\dots,v_n$ and edges $v_i\sim v_{j}$ for any $i\neq j$.
We also define the \emph{path graph}, denoted $\L_n$, as the cycle $\C_n$ from which we remove one edge.
The distance $d$ between two vertices $v_1, v_2$ in a graph $\G$ is defined as the smallest number of edges of a path connecting $v_1$ to $v_2$ over all possible paths. By convention, it is taken to be $\infty$ when there is no path connecting the vertices. Here, we call \emph{diameter} of a graph $\G$, denoted $\diam(\G)$, the largest distance between two connected vertices $g_1, g_2$ of $\G$ (in this definition, the diameter of a finite graph is finite, even if it is not connected).
\end{definition}

\begin{theorem}[Collapse of CC]  \label{theo:toy-example-thm}
Let $\G$ and $\H$ be two graphs such that
$\diam(\G)\geq2$, and that $\H$ admits exactly two connected components $\H_0$ and $\H_1$, which are both complete. Then any perfect strategy $\S$ for the graph isomorphism game $\G\cong_{ns} \H$ collapses communication complexity.
\end{theorem}

\begin{proof}
The proof simply consists in simulating the $\PR$ box from the strategy $\S$, in the sense that from inputs $x,y\in\{0,1\}$, we want to produce outputs $a,b\in\{0,1\}$ with the same behavior as the $\PR$ would do, \ie to obtain $a\oplus b = xy$ in a non-signalling way. It is enough to simulate $\PR$ since this nonlocal box is known to collapse communication complexity~\cite{vD99}.
As the diameter is $\diam(\G)\geq2$, the graph $\G$ admits the path graph with three vertices $\G_0=\L_3$ as a subgraph.
We will use the protocol described in \refprop[Figure]{fig:simulating-PR-from-isom-game}.
In this protocol, bits $x$ and $y$ are given to Alice and Bob respectively. They apply the respective processes $A_1$ and $B_1$ as described in item~(b) and obtain vertices $g_A$ and $g_B$ in $V(\G_0)$. They use these two vertices in the graph isomorphism game of $(\G,\H)$ and receive outputs $h_A,h_B\in V(\H)$. Finally, they process these vertices with $A_2$ and $B_2$ as described in item~(c) to obtain their output $a,b\in\{0,1\}$.
\begin{figure}[h]
\centering
\subfile{Figures/Simulation-of-PR/Simulation-of-PR}
\subfile{Figures/A1-B1/A1-B1}\!
\subfile{Figures/A2-B2/A2-B2}
\caption{
Illustration of the proof of \refprop[Theorem]{theo:toy-example-thm}.
In item~(a), we simulate a $\PR$ box from a perfect $\NS$-strategy for the graph isomorphism game, called ``Isom. Game'' in the figure, together with the local processes $A_1,A_2,B_1,B_2$ that are described in items~(b) and~(c).
In item~(b), the graph $\G_0$ is a subgraph of $\G$, in which Alice and Bob choose some input vertices $g_A$ and $g_B$.
In item~(c), the graphs $\H_1$ and $\H_2$ are the two connected components of $\H$, from which Alice and Bob receive some output vertices $h_A$ and $h_B$.
\label{fig:simulating-PR-from-isom-game}
\end{figure}
Let us prove that this protocol indeed simulates the $\PR$ box.
On the one hand, if $xy=1$, then $x=1=y$, which gives $g_A\not\simeq g_B$ and therefore $h_A\not\simeq h_B$. It yields that the vertices $h_A$ and $h_B$ are in different components $\H_i$ and $\H_{i\oplus1}$, so $a\oplus b = i \oplus i \oplus 1 = 1 = xy$ as wanted.
On the other hand, if $xy=0$, we have $x=0$ or $y=0$, so necessarily $g_A=g_B$ or $g_A\sim g_B$, and therefore $h_A=h_B$ or $h_A\sim h_B$. It follows that the vertices $h_A$ and $h_B$ are both in the same component $\H_i$, and $a\oplus b = i\oplus i=0 = xy$ as expected as well. In addition, note that this protocol does \emph{not} signal between Alice and Bob. Hence the $\PR$ is perfectly simulated, and there is a collapse of communication complexity.
\end{proof}

\newpage
\begin{example}
Any perfect strategy for the isomorphism game $\C_6 \cong_{ns} \K_3\sqcup\K_3$ allows to perfectly simulate the $\PR$ box and to collapse CC.
\footnote{\label{footnote:ns-isom-is-like-common-equitable-partition}
% Recall that two finite undirected graphs $\G$ and $\H$ with the same number of vertices are $\NS$-isomorphic \iff they are fractionally isomorphic~\cite{AMRSSV19}, \iff they admit a common equitable partition~\cite{RSU94} (see \refprop[Definition]{def:common-equitable-partition}).
As later detailed in \refprop[Subsection]{subsec:symmetric-strategies}, two finite undirected graphs $\G$ and $\H$ with the same number of vertices are $\NS$-isomorphic \iff they admit a common equitable partition.
A sufficient condition for the latter condition is that the graphs %have the same finite number of vertices and
are regular with the same degree, that is each vertex has a fixed constant number of neighbors. In particular, it holds $\C_6 \cong_{ns} \K_3\sqcup\K_3$.}
\begin{center}
\subfile{Figures/C6-K3-K3/C6-K3-K3}
\end{center}
\end{example}

This result can be generalized to non-perfect strategies $\S$ as follows:

\begin{corollary}[Collapse With Non-Perfect Strategies]
\label{coro:toy-example-thm}
With the same assumptions as in \hyperref[theo:toy-example-thm]{\normalfont Theorem~\ref{theo:toy-example-thm}}, any  strategy $\S$ that succeeds with probability $\pp>\frac{3+\sqrt{6}}{6}\approx0.91$ at the graph isomorphism game $\G\cong_{ns} \H$ collapses communication complexity.
\end{corollary}

\begin{proof}
We use the same protocol as in \refprop[Theorem]{theo:toy-example-thm}. It simulates a $\PR$ box with probability $\pp$, which is known to collapse communication complexity from Brassard, Buhrman, Linden, Méthot, Tapp, and Unger~\cite{BBLMTU06}.
\end{proof}

These results can be generalized to more than two connected components in $\H$, based on the assumption that Alice and Bob are given access to a perfect $\NS$-strategy for the 2-coloring game of $\K_N$, which is always granted when $N=2$, see \refprop[Theorem]{thm:combining-isomorphism-game-and-coloring-game}.

\subsection{Symmetric Strategies}
\label{subsec:symmetric-strategies}

We define a new type of perfect strategy for the graph isomorphism game, that we call \emph{symmetric strategies}, for which we show a collapse of communication complexity in the next subsection.

\begin{definition}
An $\NS$-strategy $\S$ for the graph isomorphism game $(\G, \H)$ is said \emph{symmetric} from $\G$ to the components of $\H$ if it is perfect (\ie the winning probability is $1$) and if there exist a disjoint decomposition $\H=\mathcal \H_1\sqcup \mathcal \H_2$ and some constants $\eta, \nu_{g_A,g_B}\in[0,1]$ such that:
\[
\forall g_A,g_B\in \G,\quad
\left\{
\begin{array}{l}
{\PP}_\S\big(h_A\in \H_1,\,h_B\in \H_2\,\big|\, g_A,\,g_B\big)
\,=\,
{\PP}_\S\big(h_A\in \H_2,\, h_B\in \H_1\,\big|\, g_A,\,g_B\big)
=: \nu_{g_A,g_B}
\\
{\PP}_\S\big(h_A\in \H_1,\,h_B\in \H_1\,\big|\, g_A,\,g_B\big)
\,=\,
\eta - \nu_{g_A,g_B}\,.
\end{array}
\right.
\]
\end{definition}

Examples of graphs admitting symmetric strategies can be found in \refprop[Example]{ex: decomposition of cycles}.
For the sake of the next proposition, we recall that two finite undirected graphs $\G$ and $\H$ are $\NS$-isomorphic \iff they are fractionally isomorphic~\cite{AMRSSV19}, \iff they admit a common equitable partition~\cite{RSU94}, whose definition is recalled below.

\paragraph*{Common Equitable Partition~\cite{RSU94}.} \label{para:defition-of-common-equitable-partition}
Given a graph $\G$,
define a partition $\Cpartition=\{C_1, \dots, C_k\}$ of its vertices, that is subsets $C_i\subseteq V(\G)$ such that every vertex $g$ of $\G$ belongs to exactly one set $C_{i_g}$, which may be viewed as assigning a (unique) color $C_{i_g}$ to each vertex.
We say that this partition is \emph{equitable} if, for all $i,j\in[k]$, any vertex of color $C_i$ admits precisely a fixed number, denoted $c_{ij}$, of neighbors colored with $C_j$.
Note that $c_{ij}$ and $c_{ji}$ may differ, but the equality $c_{ij} |C_i| = c_{ji} |C_j|$ always holds (see \refprop[Lemma]{lem:relation-betwenn-ct_ij-and-ct_ji} for a proof of a generalized result).
A trivial example of an equitable partition is the minimal partition $\Cpartition=\{\{g\}\,:\,g\in V(\G)\}$, where to each vertex a different color is assigned and where the matrix $[c_{ij}]_{i,j}$ is the adjacency matrix.
Another example is the maximal partition $\Cpartition=\{V(\G)\}$, which is equitable \iff the graph $\G$ is regular of degree $c_{11}$.
Now, we say that two graphs $\G$ and $\H$ admit a \emph{common equitable partition} if they admit equitable partitions of same length $\Cpartition=\{C_1, \dots, C_k\}$ and $\Dpartition=\{D_1, \dots, D_k\}$ such that the cells have same size $|C_i|=|D_i|=:n_i$ and the partition parameters coincide $c_{ij}=d_{ij}$ for all $i,j\in[k]$.
When such partitions exist, we may concisely describe them in terms of the parameters $\big(k, (n_i), (c_{ij})\big)$ and, when the context is clear, we may consider $\Cpartition$ as an equitable partition of both $\G$ and $\H$.
As mentioned above, we will use the fact that $\G\cong_{ns}\H$ \iff the graphs admit a common equitable partition~\cite{RSU94}. For instance the graphs $\G=\C_6$ and $\H=\C_3\sqcup\C_3$ are both $2$-regular, so they admit admit a common equitable partition $\big(k=1, (n_1=6), (c_{11}=2) \big)$, which is why they are $\NS$-isomorphic.

\begin{proposition}[Existence of Symmetric Strategies]   \label{prop: sufficient condition}
Let $\G\cong_{ns} \H$ such that $\H$ is not connected: $\H=\H_1\sqcup \H_2$. Denote the partitions $\Cpartition=\{C_1, \dots, C_k\}$ and $\Dpartition=\{D_1, \dots, D_k\}$ forming a common equitable partition for $\G$ and $\H$, and assume that the proportion of vertices of $\H_1$ assigned to $D_i$ is independent of $i$:
\begin{equation}   \label{eq: assumption sufficient condition proposition}
\tag*{(H)}
\forall i,j\in[k],\quad\quad
\frac{|D_i\cap \H_1|}{|D_i|}
\,=\,
\frac{|D_j\cap \H_1|}{|D_j|}\,.
\end{equation}
Then the isomorphism game of $(\G,\H)$ admits a symmetric strategy.
\end{proposition}

\begin{proof}
Let $\big(k,\, [n_1, \dots, n_k],\, [c_{ij}]_{1\leq i,j\leq k} \big)$ be the parameters of a common equitable partition for $\G$ and $\H$, and consider $\overline{c_{ij}}:= n_j - c_{ij} - \delta_{ij}$ the number of non-neighbours a vertex of $C_i$ has in $C_j$ for all $i,j$, where $\delta_{ij}$ is the Kronecker delta function.
We define the following strategy $\S$ as in~\cite[Lemma 4.4]{AMRSSV19} for which the authors prove it is perfect for the isomorphism game of $(\G,\H)$:
\begin{equation}  \label{eq:expression-of-P_S}
\PP_\S(h_A,h_B\,|\, g_A,g_B)
\,:=\,
\left\{
\begin{array}{c l}
1/n_i & \text{if $g_A=g_B$ and $h_A=h_B$ and $(\star)$},\\
1/n_i c_{ij} & \text{if $g_A\sim g_B$ and $h_A\sim h_B$ and $(\star)$},\\
1/n_i \overline{c_{ij}} & \text{if $g_A\not\simeq g_B$ and $h_A\not\simeq h_B$ and $(\star)$},\\
0 & \text{otherwise},
\end{array}
\right.
\end{equation}
where $(\star)$ denotes the condition ``$g_A\in C_i,\, g_B\in C_j,\, h_A\in D_i,\, h_B\in D_j$".
Note that $\PP_\S$ is well defined because in each case the division by zero is prevented using the condition of occurrence. Let us show that $\S$ is symmetric in two steps.
\\
$\bullet$ First, we compute the constants $\nu_{g_A,g_B}:={\PP}_\S\big(h_A\in \H_1,\,h_B\in \H_2\,\big|\, g_A,\,g_B\big)$. Notice that $\nu_{g_A,g_B}=0$ when $g_A=g_B$ or $g_A\sim g_B$
by disconnectedness of $\H_1$ and $\H_2$. Now if $g_A\not\simeq g_B$ for some $g_A\in C_i$ and $g_B\in C_j$, then:
\begin{align*}
\PP_\S\big( h_A\in\H_1, h_B\in\H_2 \,\big|\, g_A\not\simeq g_B\big)\hspace{0.2cm}
\hspace{-0.2cm}\sum_{(h_A,h_B)\in\H_1\times\H_2} \PP_\S(h_A, h_B\,|\, g_A\not\simeq g_B)
\\
\sum_{\tiny\begin{array}{c} (h_A,h_B)\in\H_1\times\H_2 \\ \text{s.t. } h_A\in D_i, h_B\in D_j
\end{array}}
\frac{1}{n_i\, \overline{c_{ij}}} \\
\quad
\frac{|D_i\cap \H_1| \times |D_j\cap \H_2|}{n_i\, \overline{c_{ij}}}\,.
\end{align*}
But as $|D_i|=|D_i\cap \H_1| + |D_i\cap \H_2|$ for all $i$, we see that the assumption~\ref{eq: assumption sufficient condition proposition} is equivalent to saying $|D_i\cap \H_1| \times |D_j\cap \H_2| = |D_i\cap \H_2| \times |D_j\cap \H_1|$.
Therefore, the above quantity also equals $\PP_\S\big( h_A\in\H_2, h_B\in\H_1 \,\big|\, g_A, g_B)$, and we obtain:
\[
\quad\quad
\nu_{g_A,g_B}
\,=\,
\left\{
\begin{array}{cl}
\displaystyle{|D_i\cap \H_1| \times |D_j\cap \H_2|}/{n_i\, \overline{c_{ij}}} & \text{if $g_A\not\simeq g_B$ and $g_A\in C_i$ and $g_B\in C_j$},\\
0 & \text{otherwise}.
\end{array}
\right.
\]
$\bullet$ Second, we compute $\eta := {\PP}_\S\big(h_A\in \H_1,\,h_B\in \H_1\,\big|\, g_A,\,g_B\big) + \nu_{g_A,g_B}$, which should be independent of $g_A,g_B$. Let $g_A\in C_i$ and $g_B\in C_j$. We split the study into three cases.\\
$(i)$~If $g_A=g_B$, then:
\begin{align*}
\PP_\S\big( (h_A,h_B)\in{\H_1}^2 \,\big|\, g_A=g_B\big)\hspace{0.2cm}
\hspace{-0.2cm}\sum_{(h_A,h_B)\in{\H_1}^2} \PP_\S(h_A, h_B\,|\, g_A= g_B)
\\
\sum_{\tiny\begin{array}{c} h\in\H_1 \\ \text{s.t. } h\in D_i \end{array}}
\underbrace{\PP_\S(h, h\,|\, g_B=g_B)}_{=1/n_i}
\\
\quad
\frac{|D_i\cap \H_1|}{n_i}
\quad=\quad
\eta - \nu_{g_A,g_B}\,,
\end{align*}
where we fixed $\eta:=\frac{|D_i\cap \H_1|}{n_i }$, and where we have $n_i\neq0$ because $g_A\in C_i$.
Let us verify that this $\eta$ is appropriate in the other cases as well.\\
$(ii)$~If $g_A\sim g_B$, then:
\begin{align*}
\PP_\S\big( (h_A,h_B)\in{\H_1}^2 \,\big|\, g_A\sim g_B\big)\hspace{0.2cm}
\hspace{-0.2cm}\sum_{(h_A,h_B)\in{\H_1}^2} \PP_\S(h_A, h_B\,|\, g_A\sim g_B)
\\
\hspace{-0.3cm}\sum_{\tiny\begin{array}{c} (h_A,h_B)\in{\H_1}^2 \\ \text{s.t. } h_A\in D_i, \\ h_B\in D_j \cap N(h_A) \end{array}}
\underbrace{\PP_\S(h_A, h_B\,|\, g_A\sim g_B)}_{=1/n_i c_{ij}}\,,
\intertext{where $N(h_A)$ is the set of adjacent vertices to $h_A$ and where $c_{ij}\neq 0$ because $g_A\sim g_B$, so:}
\hspace{-0.1cm}\sum_{h_A\in D_i\cap \H_1}  \frac{\big|D_j\cap N(h_A)\cap \H_1\big|}{n_i\,c_{ij}} \,.
\intertext{But by disconnectedness of $\H_1$ and $\H_2$ we have $|D_j\cap N(h_A)\cap \H_1| = |D_j\cap N(h_A)|$
, which is equal to $c_{ij}$ by definition. Hence, it simplifies with the coefficient in the denominator, so we obtain:}
\hspace{-0.1cm}\sum_{h_A\in D_i\cap \H_1}\frac{1}{n_i}
\quad= \quad
\frac{|D_i\cap \H_1|}{n_i}\
\quad=\quad
\eta - \nu_{g_A,g_B}\,.
\end{align*}
$(iii)$~If $g_A\not\simeq g_B$:
\begin{align*}
\PP_\S\big( (h_A,h_B)\in{\H_1}^2 \,\big|\, g_A\not\simeq g_B\big)\hspace{0.2cm}
\sum_{(h_A,h_B)\in{\H_1}^2} \PP_\S(h_A, h_B\,|\, g_A\not\simeq g_B)
\\
\hspace{-0.6cm}\sum_{\tiny\begin{array}{c} (h_A,h_B)\in{\H_1}^2 \\ \text{s.t. } h_A\in D_i, \\ h_B\in D_j \backslash(N(h_A)\cup\{h_A\}) \end{array}}
\hspace{-0.5cm}
\underbrace{\PP_\S(h_A, h_B\,|\, g_A\not\simeq g_B)}_{=1/n_i \overline{c_{ij}}}\,,
\intertext{where $\overline{c_{ij}}\neq 0$ because $g_A\not\simeq g_B$, so:}
\sum_{h_A\in D_i\cap \H_1} \frac{\big|D_j\cap \H_1\backslash(N(h_A)\cup\{h_A\})\big|}{n_i \,\overline{c_{ij}}}\,.
\intertext{But by definition $n_j := |D_j| = |D_j\cap \H_2| + |D_j\cap \H_1\backslash(N(h_A)\cup\{h_A\})| + |D_j\cap \H_1\cap(N(h_A)\cup\{h_A\})|$, where the last term is $c_{ij} + \delta_{ij}$. After reordering the terms, it yields that the second term is $|D_j\cap \H_1\backslash(N(h_A)\cup\{h_A\})| = \overline{c_{ij}} - |D_j\cap \H_2|$, therefore:
\sum_{h_A\in D_i\cap \H_1} \frac{\overline{c_{ij}} - |D_j\cap \H_2|}{n_i \,\overline{c_{ij}}}
\\
\frac{|D_i\cap \H_1|}{n_i} - \frac{|D_i\cap \H_1| \times |D_j\cap \H_2|}{n_i \,\overline{c_{ij}}}
\\
\eta - \nu_{g_A,g_B}\,.
\end{align*}
Hence, the coefficient $\eta$ is the same in the three cases and independent of $g_A,g_B$, so we proved that $\S$ is indeed symmetric.
\end{proof}

\begin{corollary}
Let $\G, \H$ be two graphs of degree $d$ such that
$\H$ is not connected.
Then $\G\cong_{ns} \H$ and this isomorphism game admits a symmetric strategy.
\end{corollary}

\begin{proof}
Consider the common equitable partition given by the parameters $\big(k=1,\, n_1=|V(\G)|,\, c_{11} = d\big)$. Deduce that $\G\cong_{ns} \H$ by \cite{AMRSSV19}, and then conclude using \refprop[Proposition]{prop: sufficient condition}, because the above hypothesis~\ref{eq: assumption sufficient condition proposition} is obviously satisfied when $k=1$.
\end{proof}

\begin{example}  \label{ex: decomposition of cycles}
For any integer decomposition $M = m_1+ \dots + m_K$ with $m_i\geq3$ and $K\geq 2$, the previous corollary tells us that the following isomorphism of cycles holds:
\[
\C_M
\quad\cong_{ns}\quad
\C_{m_1} \sqcup \dots \sqcup \C_{m_K}\,,
\]
and that the associated isomorphism game admits a symmetric strategy.
\end{example}

\subsection{Existence of Perfect Non-Signalling Strategies that Collapse CC}
\label{subsec:link-with-communication-complexity}

In this subsection, under some conditions, we prove that the graph isomorphism game $(\G,\H)$ admits a perfect non-signalling strategy that collapses communication complexity. In the next subsection, we will add conditions on $\H$ to obtain that all perfect non-signalling strategies are collapsing.

\begin{theorem}[Collapse of CC]  \label{theo: collapse of CC}
Let $\G\cong_{ns} \H$
such that $\diam(\G)\geq2$
and such that $\H$ is not connected: $\H=\H_1\sqcup \H_2$, where each of $\H_1$ and $\H_2$ may possibly be decomposed in several connected components.
Denote the partitions $\Cpartition=\{C_1, \dots, C_k\}$ and $\Dpartition=\{D_1, \dots, D_k\}$ forming a common equitable partition for $\G$ and $\H$, and assume the hypothesis~\ref{eq: assumption sufficient condition proposition} as in \refprop[Proposition]{prop: sufficient condition}\,.
Then the isomorphism game of $(\G,\H)$ admits a perfect strategy that collapses communication complexity.
\end{theorem}

To prove the theorem, we define a noisy version of the $\PR$ box, that we denote $\PR_{\alpha, \beta} := \alpha\,\PR + \beta\,\P_0 + (1-\alpha-\beta)\,\P_1$, which is the convex combination with coefficients $\alpha,\beta\geq0$ of the boxes $\PR$, $\P_0$ and $\P_1$ defined in \refprop[Figure]{fig:famous-types-of-strategies}\,. This noisy box is known to collapse communication complexity as long as $\alpha>0$~\cite{BMRC19, BBCNP23}, so the idea is to first prove that $\PR_{\alpha,\beta}$ can be generated from a perfect strategy $\S$ for the isomorphism game:

\begin{lemma}  \label{theo: simulate P alpha beta}
Let $\G,\H$ two graphs such that $\diam(\G)\geq2$ and such that $\H$ is not connected: $\H=\H_1\sqcup \H_2$. Assume $\G\cong_{ns}\H$ for some strategy $\S$ that is symmetric from $\G_0$ to the components of $\H$, and suppose that:
\begin{equation} \label{eq: assumption Thm}
\nu_{g_1, g_3} >0\,.
\end{equation}
Then the box $\PR_{\alpha,\beta}$  is perfectly simulated with  $\alpha=2\,\nu_{g_1, g_3}>0$ and some $\beta\geq0$.
\end{lemma}

\begin{proof}
The protocol in this proof is inspired by the one of \refprop[Theorem]{theo:toy-example-thm}.
As the diameter is $\diam(\G)\geq2$, the graph $\G$ admits the path graph with three vertices $\G_0=\L_3$ as a subgraph, whose vertices are called $g_1,g_2,g_3$ each one being connected to the next one.
We proceed with the same protocol as described in \refprop[Figure]{fig:simulating-PR-from-isom-game}, the only difference being that $\H_1$ and $\H_2$ are not necessarily complete and not even connected.
Denote $\P(a,b\,|\,x,y)$ the nonlocal box induced by this protocol. Let us prove that $\P=\PR_{\alpha,\beta}$ for some $\alpha,\beta\in[0,1]$. To this end, we compare the correlation tables of $\P$ and $\PR_{\alpha,\beta}$, defined as follows:
\begin{align*}
:= &
\footnotesize
\begin{bmatrix}
\P(0,0\,|\,0,0) & \P(0,1\,|\,0,0) & \P(1,0\,|\,0,0) & \P(1,1\,|\,0,0) \\
\P(0,0\,|\,0,1) & \P(0,1\,|\,0,1) & \P(1,0\,|\,0,1) & \P(1,1\,|\,0,1) \\
\P(0,0\,|\,1,0) & \P(0,1\,|\,1,0) & \P(1,0\,|\,1,0) & \P(1,1\,|\,1,0) \\
\P(0,0\,|\,1,1) & \P(0,1\,|\,1,1) & \P(1,0\,|\,1,1) & \P(1,1\,|\,1,1)
\end{bmatrix}\,,
\\
\intertext{and similarly defined for $\PR_{\alpha,\beta}$. On the one hand, by symmetry of the strategy $\S$, the correlation table of $\P$ can be computed explicitely:}
= &
\begin{bmatrix}
\eta - \nu_{g_2,g_2} & \nu_{g_2,g_2} & \nu_{g_2,g_2} & 1 - \eta - \nu_{g_2,g_2} \\
\eta - \nu_{g_2,g_3} & \nu_{g_2,g_3} & \nu_{g_2,g_3} & 1 - \eta - \nu_{g_2,g_3} \\
\eta - \nu_{g_1,g_2} & \nu_{g_1,g_2} & \nu_{g_1,g_2} & 1 - \eta - \nu_{g_1,g_2} \\
\eta - \nu_{g_1,g_3} & \nu_{g_1,g_3} & \nu_{g_1,g_3} & 1 - \eta - \nu_{g_1,g_3} \\
\end{bmatrix} \,.
\intertext{
But, we see that if $x=0$ or $y=0$, then the inputs $g_A,g_B\in V(\G)$ of Alice and Bob in $\S$ are either equal or adjacent. It turns out that the outputs $h_A, h_B\in V(\H)$ of $\S$ are in the same connected component, therefore $a=b$ almost surely and $\P(a\neq b \,|\, x=0 \text{ or } y=0)=0$.
Hence, in the first three lines of the matrix, we have $\nu_{g_2,g_2} = \nu_{g_2,g_3} = \nu_{g_1,g_2} = 0$, which gives:}
M_\P= &
\begin{bmatrix}
\eta  & 0 & 0 & 1 - \eta \\
\eta  & 0 & 0 & 1 - \eta \\
\eta  & 0 & 0 & 1 - \eta \\
\eta - \nu_{g_1,g_3} & \nu_{g_1,g_3} & \nu_{g_1,g_3} & 1 - \eta - \nu_{g_1,g_3} \\
\end{bmatrix} \,.
\end{align*}
On the other hand, by linearity, the correlation table of the box $\PR_{\alpha, \beta}$ is the convex combination of the correlation tables of $\PR$, $\P_0$, $\P_1$ with coefficients $\alpha,\beta\in[0,1]$ fixed above, so:
\[
\,=\,
\begin{bmatrix}
\frac{\alpha}{2} + \beta & 0 & 0 & 1 - \frac{\alpha}{2} - \beta\\
\frac{\alpha}{2} + \beta & 0 & 0 & 1 - \frac{\alpha}{2} - \beta\\
\frac{\alpha}{2} + \beta & 0 & 0 & 1 - \frac{\alpha}{2} - \beta\\
\beta & \frac{\alpha}{2} & \frac{\alpha}{2} & 1 - \alpha - \beta
\end{bmatrix} \,.
\]
Now, taking $\alpha := 2\,\nu_{g_1,g_3}$ and $\beta:= \eta - \nu_{g_1,g_3}$, we obtain $\P=\PR_{\alpha,\beta}$ as wanted.
\end{proof}

\begin{proof}[{ Proof (Theorem~\ref{theo: collapse of CC})}]
To invoke the former lemma, we need to prove the existence of a symmetric strategy, which was the purpose of \refprop[Proposition]{prop: sufficient condition}.
We can apply this proposition because all its assumptions are found in the theorem as well. It yields a symmetric strategy from $\G$ to the components of $\H$, and in particular, its restriction to $\G_0$ is also symmetric.
Moreover, assumption~\eqref{eq: assumption Thm} in \refprop[Lemma]{theo: simulate P alpha beta} is also satisfied because,
using the computations in the proof of \refprop[Proposition]{prop: sufficient condition}\,, we have:
\[
\nu_{g_1,g_3}
\,=\,
\frac{|D_i\cap \H_1| \times |D_j\cap \H_2|}{n_i\, \overline{c_{ij}}}
\,>\,
\]
where $i$ and $j$ are such that $g_1\in C_i$ and $g_3\in C_j$.
Thus we can apply \refprop[Lemma]{theo: simulate P alpha beta} and we can simulate $\PR_{\alpha, \beta}$ for some $\alpha>0$. But the box $\PR_{\alpha,\beta}$ with $\alpha>0$ is known to be collapsing~\cite{BMRC19, BBCNP23}. Hence we deduce the existence of a protocol that collapses CC.
\end{proof}

\begin{corollary}[Collapse of CC]
Each of the $\NS$-isomorphisms given in \refprop[Example]{ex: decomposition of cycles} admits a perfect strategy $\S$ that allows to perfectly produce a box $\PR_{\alpha,\beta}$ with $\alpha>0$ and therefore to collapse communication complexity.\qed
\end{corollary}

\subsection{All Perfect Non-Signalling Strategies Collapse CC}
\label{para:All-Perfect-Strategies-Collapse-CC}

In \refprop[Theorem]{theo: collapse of CC} above, the statement was that \emph{some} perfect strategies collapse communication complexity. Now, if we add regularity and transitivity conditions on $\H$, we obtain that \emph{every} perfect strategy collapses communication complexity. First, we recall the definition of the automorphism group of a graph.

\subsubsection{Automorphism Group} The \emph{automorphism group} of $\H$, denoted $\Aut(\H)$, is the set of all bijective maps $\varphi:\H\to\H$ that preserve the adjacency relation, meaning that $h_1\sim h_2$ \iff $\varphi(h_1)\sim\varphi(h_2)$. As a consequence, any automorphism $\varphi\in\Aut(\H)$ also preserves the relation ``$\not\simeq$'', and therefore a graph $\H$ and its complement $\H^c$ have the same automorphism group: $\Aut(\H)=\Aut(\H^c)$.
Moreover, the composition of two automorphisms is again an automorphism, and $\varphi^{-1}\in\Aut(\H)$, which endows the set $\Aut(\H)$ with a group structure.
For instance, the automorphism group of the complete graph $\K_N$ is the symmetric group $\Aut(\K_N)=\Sym_N$ of order $N!$, and the one of the cycle $\C_N$ is the dihedral group $\Aut(\C_N)=D_N$ of order $2N$.
We refer to~\cite{Godsil-Royle-01} for more details on automorphism groups.

\subsubsection{Graph Transitivity} The graph $\H$ is said to be \emph{vertex-transitive} if for all vertices $h,h'\in V(\H)$, there exists a graph automorphism $\varphi\in\Aut(\H)$ such that $\varphi(h)=h'$.
%A stronger version is \emph{quasi-Cayley} graphs~\cite{Gauyacq-97}, which could also be called \emph{uniform vertex-transitive} graphs~\cite{SVW19}. It consists in finding a subset $S\subseteq\Aut(\H)$ such that for all vertices $h,h'\in V(\H)$, there exists a unique (!) automorphism $\varphi\in S$ such that $\varphi(h)=h'$.
Similarly, we say that $\H$ is \emph{edge-transitive} if for all edges $h_1\sim h_2,\,h_1'\sim h_2'\in E(\H)$, there exists a graph automorphism $\varphi\in\Aut(\H)$ such that $\varphi(h_1)=h_1'$ and $\varphi(h_2)=h_2'$.
%And \emph{uniform edge-transitivity} consists in finding a subset $S\subseteq\Aut(\H)$ such that this condition is satisfied for a unique automorphism $\varphi\in S$.
We refer to~\cite{Godsil-Royle-01} for more details on graph transitivity, and to~\cite{Gauyacq-97, SVW19} for related notions.
In the definition below, we strengthen the vertex- and edge- transitivity of a graph $\H$ and its complement $\H^c$ in what we call the \emph{strong transitivity}:

\begin{definition}[Strongly Transitive]   \label{def:strongly-transitive}
We say that a graph $\H$ is \emph{strongly transitive} if there exists a subset of the automorphism group $S\subseteq\Aut(\H)$ such that the three following conditions hold:\vspace{-5pt}
\begin{enumerate}[label=(\roman*),itemsep=-3pt]
\item \label{item:def-strong-transitive-1} There is a constant $d_1\geq1$ such that for all vertices $h,h'\in V(\H)$, there exist exactly $d_1$ automorphisms $\varphi\in S$ such that $\varphi(h)=h'$.
\item \label{item:def-strong-transitive-2} There is a constant $d_2\geq1$ such that for all edges $h_1\sim h_2,\,h_1'\sim h_2'\in E(\H)$, there exist exactly $d_2$ automorphisms $\varphi\in S$ such that $\varphi(h_1)=h_1'$ and $\varphi(h_2)=h_2'$.
\item \label{item:def-strong-transitive-3} There is a constant $d_3\geq1$ such that for all edges in the complement graph $h_1\sim h_2,\,h_1'\sim h_2'\in E(\H^c)$, there exist exactly $d_3$ automorphisms $\varphi\in S$ such that $\varphi(h_1)=h_1'$ and $\varphi(h_2)=h_2'$.
\end{enumerate}
\end{definition}

Notice that strong transitivity implies vertex-transitivity and edge-transitivity of both $\H$ and its complement $\H^c$, since it is possible to pick one among the respective $d_1$, $d_2$, $d_3$ automorphisms $\varphi\in S$ satisfying the wanted condition for each vertices and edges.
Note that if $\H$ is strongly transitive, then its complement $\H^c$ is also strongly transitive.
Note also that $S$ cannot be the empty set $\emptyset$ because of condition~\ref{item:def-strong-transitive-1}, unless the graph $\H$ is itself empty.

Let us prove the following characterization of strong transitivity, and then provide some examples of strongly transitive graphs. First recall that a graph $\H$ is called \emph{distance-transitive} if for any $d\in\NN$ and any two pairs $(h_1,h_2)$ and $(h_1',h_2')$ of vertices $h_1,h_2,h_1',h_2'\in V(\H)$ with distance $d(h_1,h_2)=d(h_1',h_2')=d$, there is an automorphism $\varphi$ of $\H$ such that $\varphi(h_1)=h_1'$ and $\varphi(h_2)=h_2'$.

\begin{lemma}[Characterization of Strong Transitivity]  \label{lem:characterization-of-strong-transitivity}
A graph $\H$ is strongly transitive \iff it is distance-transitive and its diameter satisfies $\diam(\H)\leq 2$. Moreover, we may always choose $S=\Aut(\H)$ in \refprop[Definition]{def:strongly-transitive}\,.
\end{lemma}
\begin{proof}
Assume that $\H$ is strongly transitive in the sense of \refprop[Definition]{def:strongly-transitive}\,.
First, we prove distance-transitivity for three instances of $d\in\NN$:
vertex-transitivity ($d=0$) is a particular case of item~\ref{item:def-strong-transitive-1} of the definition;
edge-transitivity ($d=1$) is a particular case of item~\ref{item:def-strong-transitive-2};
and in any other case ($d\geq2$), vertices at distance $d$ in $\H$ are adjacent in the complement graph $\H^c$, so the existence of automorphism $\varphi$ follows from item~\ref{item:def-strong-transitive-3}; hence the distance-transitivity.
We then prove that all vertices in $\H$ have distance at most $2$. Assume by contradiction that there are two vertices $h_1,h_2\in V(\H)$ with $d(h_1,h_2)>2$. Hence, there is a path from $h_1$ to $h_2$ of length greater than two, which needs to pass through a vertex $h_3\in V(\H)$ with $d(h_1,h_3)=2$. Now, as $h_1\sim h_2$ and $h_1\sim h_3$ are edges of the complement graph $\H^c$, item~\ref{item:def-strong-transitive-3} of \hyperref[{def:strongly-transitive}]{Definition~\ref{def:strongly-transitive}} tells us that we can find an automorphism $\varphi\in S$ with $\varphi(h_1)=h_1$ and $\varphi(h_2)=h_3$, and as automorphisms preserve distances, we have $d(h_1,h_2)=d(\varphi(h_1),\varphi(h_2))=d(h_1,h_3)$. But this contradicts $d(h_1,h_2)> d(h_1,h_3)$, so we have $\diam(\H)\leq 2$ as claimed.

Conversely, assume that $\H$ is distance-transitive with $\diam(\H)\leq 2$, and choose $S=\Aut(\H)$. We prove the three items of \refprop[Definition]{def:strongly-transitive} in the canonical order. Given vertices $h,h'\in V(\H)$ denote by $a_{h,h'}$ the number of automorphisms $\varphi\in \Aut(\H)$ with $\varphi(h)=h'$. It is nonzero since $\H$ is distance-transitive so in particular vertex-transitive. Now, given two further vertices  $k,k'\in V(\H)$, there are automorphisms $\varphi_1,\varphi_2\in \Aut(\H)$ with $\varphi_1(h)=k$ and $\varphi_2(h')=k'$. For any automorphism $\psi$ with $\psi(k)=k'$, the map $\varphi_2^{-1}\circ\psi\circ\varphi_1$ yields an automorphism mapping $h$ to $h'$. This shows $a_{k,k'}\leq a_{h,h'}$. Now, by the symmetry of the argument, this is actually equality, and we may set $d_1:=a_{h,h'}\geq1$, thus proving item~\ref{item:def-strong-transitive-1}.
Then, for item~\ref{item:def-strong-transitive-2}, the proof is very similar, using the edge-transitivity of $\H$.
Finally, for item~\ref{item:def-strong-transitive-3}, note that edges in the complement graph $\H^c$ correspond to pairs of vertices in $\H$ at distance $2$, so once again distance-transitivity allows us to conclude with the same argument as for item~\ref{item:def-strong-transitive-1}.
\end{proof}

\begin{example}
From this characterization, we deduce that the following graphs are examples of strongly transitive graphs, among others:
%the empty graph $\emptyset$ (which has diameter $0$ with our convention),
the complete graphs $\K_N$ and their complement $\K_N^c$ for any $N\geq0$ (note that the empty graph $\K_N^c$ has diameter $0$ with our convention),
the path graphs $\L_N$ for $N\leq3$,
the cycle graphs $\C_N$ for $N\leq 5$,
the complete bipartite graph $\K_{3,3}$,
and the famous Petersen graph.
Moreover, several finite groups may be written as the automorphism group of a distance-transitive graph with diameter $2$, see details in~\cite{Godsil-Royle-01}.
%	\item \label{item:complete-graphs-are-strongly-transitive} The complete graph $\H=\K_N$ is strongly transitive for any $N\geq 1$. Indeed, for $N=1$ the result is obvious.
%		For $N\geq2$, consider $S=\Aut(\K_N)=\Sym_N$ the entire automorphism group. Then the constants $d_1=(N-1)!$ and $d_2=(N-2)!$ satisfy conditions~\ref{item:def-strong-transitive-1} and~\ref{item:def-strong-transitive-2}.
%		Moreover, the edge set of the complement is empty $E(\H^c)=\emptyset$, so any constant $d_3$ satisfies condition~\ref{item:def-strong-transitive-3}.
%		Likewise, its complement graph $\K_N^c$, \ie the disjoint union of $N$ vertices, is also strongly transitive.
%	\item The cycle $\H=\C_N$ is strongly transitive for $N\in\{1, \dots, 5\}$.
%		Cases $N\leq 3$ come from item~\ref{item:complete-graphs-are-strongly-transitive}.
%		For $N\in\{4,5\}$, consider $S=\Aut(\C_N)=D_N$ the dihedral group, whose cardinality is $2N$, generated by symmetries and rotations of the regular $N$-polygon.
%		The vertex and edge sets have cardinalities $|V(\C_N)|=N$ and $|E(\C_N)|=N$, so the constants $d_1=2$ and $d_2=1$ satisfy conditions~\ref{item:def-strong-transitive-1} and~\ref{item:def-strong-transitive-2}.
%		However, the vertex set of the complement is big, the cardinality $|E(\C_N^c)|$ is the difference between the number of edges in the complete graph $\K_N$ and the number of edges in $\C_N$, which gives:
%		\[
%			|E(\C_N^c)|
%			\,=\,
%			\frac{N(N-1)}{2} - N
%			\,=\,
%			\frac{N(N-3)}{2} \,.
%		\]
%		Now, using the necessary condition in \refprop[Lemma]{lem:strong-transitivity-implies-conditions-on-cardinals}, we know that $d_3$ must satisfy $d_3={|S|}/{2|E(\H^c)|}={2}/{(N-3)}$. For this choice of $d_3$, it is easy to check that condition~\ref{item:def-strong-transitive-3} is indeed satisfied. Hence $\C_N$ is strongly transitive for $N\in\{1,\dots, 5\}$, and similarly for its complement $\C_N^c$.
\end{example}

We prove that when $\H$ is strongly transitive, there is a strong connection between cardinalities, which will be useful in the proof of the collapse of CC in \refprop[Theorem]{theo:collapse-for-ALL-strategies}.

\begin{lemma}   \label{lem:strong-transitivity-implies-conditions-on-cardinals}
Let $\H$ be a strongly transitive graph different from the complete graph $\K_N$ and its complement $\K_N^c$, together with its associated subset $S\subseteq \Aut(\H)$ and parameters $(d_1,d_2,d_3)$. Then the size of the set $S$ is necessarily
\,=\,
\,=\,
\,=\,
\end{lemma}

\begin{proof}
We prove the first equality by showing the two inequalities. Let us index $h_1, \dots, h_n$ the vertices of $\H$, where $n=|V(\H)|$.
On the one hand, using condition~\ref{item:def-strong-transitive-1}, we know that there are exactly $d_1$ automorphisms $\varphi\in S$ sending $h_1$ to itself, and again $d_1$ other automorphisms sending $h_1$ to $h_2$, so on and so forth until $h_n$. Note also that a given automorphism $\varphi\in\Aut(\H)$ cannot send $h_1$ to two different vertices. It yields that the set $S$ contains at least $d_1n$ elements.
On the other hand, each element $\varphi$ of $S$ necessarily sends $h_1$ to a vertex $h_i$ of $\H$, so $S$ contains at most $d_1 n$ elements, which gives the first equality.
For the other two equalities, proceed similarly using conditions~\ref{item:def-strong-transitive-2} and~\ref{item:def-strong-transitive-3}, where the factor ``$2$'' comes from the fact that graphs are undirected, so the two relations $h_1\sim h_2$ and $h_2\sim h_1$ are counted as only one edge.
Note also that the condition $\H\neq \K_N$ and $\K\neq\K_N^c$ prevents the sets $E(\H)$ and $E(\H^c)$ to be empty.
Hence the wanted chain of equalities.
\end{proof}

\subsubsection{Collapse of Communication Complexity} In the theorem below, we combine this notion of strong transitivity with $d$-regularity of $\H$ to obtain a collapse of CC. The key idea will be to compute an expectation $\mathbb{E}$ over $\varphi$ uniformly sampled in a subset of the automorphism group $S\subseteq\Aut(\H)$ and to use the strong transitivity to obtain a symmetric strategy that collapses CC. Recall that $\H$ is said to be $d$-regular if every vertex is connected to exactly $d$ other vertices.

\begin{theorem}[All Perfect Strategies Collapse CC]  \label{theo:collapse-for-ALL-strategies}
Let $\G$ and $\H$ be two graphs such that the conditions of \refprop[Theorem]{theo: collapse of CC} hold. Assume moreover that $\H$ is strongly transitive and $d$-regular, and that the players share randomness. Then \emph{every} perfect non-signalling strategy for the isomorphism game associated with $\G\cong_{ns}\H$ collapses communication complexity.
\end{theorem}

\begin{proof}
Denote $\P$ an arbitrary perfect strategy for $\G\cong_{ns}\H$, and denote $S\subseteq\Aut(\H)$ and $(d_1,d_2,d_3)$ as given in the definition of strong transitivity.
We will post-process $\P$ in order to generate a symmetric strategy, which will allow us to generate a collapsing nonlocal box.
The two players Alice and Bob can use their shared randomness to pick uniformly at random an automorphism $\varphi\in S$ that is known by the two of them.
They apply the following protocol: once they receive the outputs $h_A,h_B$ from $\P$, they compute the images $h_A'=\varphi(h_A)$ and $h_B'=\varphi(h_B)$ and they call $\Ptilde(h_A',h_B'\,|\,g_A,g_B)$ the new strategy, in other words this is the following expectation:
\[
\Ptilde(h_A',h_B'\,|\,g_A,g_B)
\,=\,
\underset{\varphi\in S}{\EE}\, \P\big( \varphi^{-1}(h_A'),\varphi^{-1}(h_B')\,\big|\, g_A,g_B \big)\,.
\]
Observe that $\Ptilde$ is non-signalling by the composition of a non-signalling strategy with a non-signalling post-process.
Let us compute the expression of $\Ptilde$.
First, if $g_A=g_B$, then:
\begin{align*}
\Ptilde(h_A',h_B'\,|\,g_A,g_A)
\frac{1}{d_1\,|V(\H)|} \sum_{\varphi\in S}\, \P\big( \varphi^{-1}(h_A'),\varphi^{-1}(h_B')\,\big|\, g_A,g_A \big)
\\
\frac{1}{d_1\,|V(\H)|} \sum_{\varphi\in S}\, \P\big( \varphi^{-1}(h_A'),\varphi^{-1}(h_A')\,\big|\, g_A,g_A \big) \, \delta_{\varphi^{-1}(h_A')=\varphi^{-1}(h_B')}
\\
\frac{1}{d_1\,|V(\H)|} \,\, d_1\underbrace{\sum_{h\in V(\H)}\, \P\big( h, h\,\big|\, g_A,g_A \big)}_{=1} \, \delta_{h_A'=h_B'}
\,=\,
\frac{\delta_{h_A'=h_B'}}{|V(\H)|}\,,
\end{align*}
where the first equality follows from the definition of $\Ptilde$ combined with \refprop[Lemma]{lem:strong-transitivity-implies-conditions-on-cardinals}, the second one from the rules of the isomorphism game, and the third one from condition~\ref{item:def-strong-transitive-1} in the definition of strong transitivity of $\H$; moreover, the Kronecker delta condition is changed using the bijectivity property of an automorphism $\varphi$, and the underbrace equality ``$=1$'' comes from the rules of the isomorphism game.
Second, if $g_A\sim g_B$, then similarly:
\begin{align*}
\Ptilde(h_A',h_B'\,|\,g_A,g_B)
\frac{1}{2\,d_2\,|E(\H)|} \sum_{\varphi\in S}\, \P\big( \varphi^{-1}(h_A'),\varphi^{-1}(h_B')\,\big|\, g_A,g_B \big)
\\
\frac{1}{2\,d_2\,|E(\H)|}\,\, d_2\! \underbrace{\sum_{h_1\sim h_2\in V(\H)}\, \P\big( h_1, h_2\,\big|\, g_A,g_B \big)}_{=1}\,\delta_{h_A'\sim h_B'}
\,=\,
\frac{\delta_{h_A'\sim h_B'}}{2\,|E(\H)|}\,.
\end{align*}
Third, if $g_A\not\simeq g_B$, then we proceed similarly, simply replacing ``$d_2$'' by ``$d_3$'', ``$\H$'' by ``$\H^c$'', and ``$\sim$'' by ``$\not\simeq$'', and we obtain $\Ptilde=\delta_{h_A'\not\simeq h_B'}/2|E(\H^c)|$.
To sum up, we have:
\[
\Ptilde(h_A',h_B'\,|\,g_A,g_B)
\,=\,
\left\{
\begin{array}{ll}
1/|V(\H)| & \text{if $g_A=g_B$ and $h_A'=h_B'$}\,,\\
1/2|E(\H)| & \text{if $g_A\sim g_B$ and $h_A'\sim h_B'$}\,,\\
1/2|E(\H^c)| & \text{if $g_A\not\simeq g_B$ and $h_A'\not\simeq h_B'$}\,,\\
0 & \text{otherwise}\,.
\end{array}
\right.
\]
Now, when comparing this expression of $\Ptilde$ with the expression of $\PP_\S$ in equation~\eqref{eq:expression-of-P_S} of the proof of \refprop[Proposition]{prop: sufficient condition}, we see that they coincide in the case of the maximal partition $\Dpartition'=\{V(\H)\}$ with parameters $(k=1, n_1=|V(\H)|, c_{11}=d)$, where $d$ is the parameter of regularity of $\H$ by assumption.
Then, following the same proof, it turns out that the strategy $\Ptilde$ is perfect for the isomorphism game associated with $\G\cong_{ns}\H$, and that it is symmetric with parameter:
\nu_{g_1,g_3}
\,=\,
\frac{|\H_1|\times|\H_2|}{|V(\H)|\times |E(\H^c)|}>0\,,
where the denominator is not zero because $\H$ contains several connected components, so it is not complete and $|E(\H^c)|>0$.
Therefore, we can apply \refprop[Lemma]{theo: simulate P alpha beta} and we can simulate $\PR_{\alpha, \beta}$ for some $\alpha>0$. Hence, as in the proof of \refprop[Theorem]{theo: collapse of CC} we conclude the existence of a non-signalling protocol that collapses communication complexity.
\end{proof}

Finally, as quantum correlations cannot collapse CC~\cite{CvDNT99}, it yields:

\begin{corollary}[These Strategies are not Quantum]  \label{coro:cannot-be-quantum}
A perfect $\NS$-strategy $\S$ for the graph isomorphism game satisfying the conditions of \refprop[Theorem]{theo:collapse-for-ALL-strategies} cannot be quantum. \qed
\end{corollary}

\bib

\end{document}