# Symmetric Perfect $2$-colorings on $J(10,3)$

Paul Tricot  School of Information Science, Tohoku University, Japan

##  1\. Introduction

A perfect $2$-coloring of a Johnson graph can be associated to one of the non-
principal eigenvalue of the graph $\theta_{1}>\dots>\theta_{k}$. The perfect
$2$-colorings of the Johnson graphs $J(n,3)$ associated with $\theta_{1}$ have
been characterized by Meyerowitz [7], and those associated with $\theta_{3}$
by Martin [6]. Those associated with $\theta_{2}$ have been studied by several
mathematicians. Evans, Gavrilyuk, Goryainov and Vorob’ev [1, 3] classified
them for $n$ odd and for $n>10$. Avgustinovich and Mogilnykh also studied
these perfect $2$-colorings [2, 5], in particular for $n=6$, 7 and 8.

In [1], Gavrilyuk and Goryainov proved that a perfect $2$-coloring of $J(n,3)$
associated with $\theta_{2}$ and symmetric quotient matrix is possible only
when $n\in\\{6,10\\}$. In this paper, we survey the known constructions in the
case $n=6$, we give a new construction for the two known perfect $2$-colorings
in the case $n=10$, and prove that these are the only possible ones.

##  2\. Preliminaries

A perfect $m$-coloring of a regular graph $\Gamma$ is a partition
$P_{1},\dots,P_{m}$ of the vertices such that there exist fixed numbers
$p_{i,j}$ ($i,j\in[m]$) that verify

$\forall x\in P_{i},|\Gamma(x)\cap P_{j}|=p_{i,j},$

where $\Gamma(x)$ is the neighborhood of $x$ in $\Gamma$, which is the set of
all its neighbors. The matrix $P=[p_{i,j}]_{1\leq i,j\leq m}$ is called the
quotient matrix of the coloring. This means that for every vertex $x\in
P_{i}$, $x$ has exactly $p_{i,j}$ neighbors in $P_{j}$. We will say that the
perfect coloring is symmetric when the quotient matrix is.

$P$ has $m$ eigenvalues that are among the eigenvalues of $\Gamma$, by that we
mean eigenvalues of its adjacency matrix. In particular the valency of the
graph is always an eigenvalue of $P$ (see [1]).

The Johnson graph $J(n,k)$ with parameters $n,k\in\mathbb{N}$ has as vertices
the subsets of $[n]:=\\{1,\dots,n\\}$ of size $k$. The vertices $x$ and $y$
are connected when $|x\cap y|=k-1$. The distance between two elements is given
by $d(x,y)=k-|x\cap y|$. The graph $J(n,k)$ is regular, with valency $k(n-k)$.

The eigenvalues of the Johnson graph $J(n,k)$ are the eigenvalues of its
adjacency matrix, and are well known to be $\theta_{i}:=(k-i)(n-k-i)-i$,
$i\in\\{0,\dots,k\\}$. The quotient matrix $P$ of a perfect $2$-coloring of
$J(n,k)$ always has as eigenvalue $\theta_{0}$ which is the valency of the
graph, and $\theta_{i}$ for some $i\in\\{1,\dots,k\\}$. In this paper we focus
on perfect $2$-colorings with eigenvalues $\theta_{0}$ and $\theta_{2}$.

Under certain conditions on the quotient matrix $P$, it is possible to join
the parts of an $m$-coloring to form a coloring with less parts (see [2, Lemma
1]). For instance, consider a perfect coloring with three parts
$P_{1},P_{2},P_{3}$ and quotient matrix $P$ that we want to merge into a
perfect $2$-coloring with parts $P_{1}\cup P_{2}$ and $P_{3}$. Then we need to
make sure that for $x\in P_{1}$ and $y\in P_{2}$, $|\Gamma(x)\cap(P_{1}\cup
P_{2})|=|\Gamma(y)\cap(P_{1}\cup P_{2})|$, and also $|\Gamma(x)\cap
P_{3}|=|\Gamma(y)\cap P_{3}|$. This is equivalent to
$p_{1,1}+p_{1,2}=p_{2,1}+p_{2,2}$ and $p_{1,3}=p_{2,3}$. But since the row sum
of $P$ is fixed, only one of these equality is necessary.

In the general case, consider a perfect $m$-coloring with parts
$P_{1},\dots,P_{m}$, and $C_{1},\dots,C_{l}$ a partition of $[m]$. Then

$\bigcup_{i\in C_{1}}P_{i},\dots,\bigcup_{i\in C_{l}}P_{i}$

is a perfect $l$-coloring if and only if each of the submatrices
$[p_{x,y}]_{x\in C_{i},y\in C_{j}}$ for $i\in[l]$, $j\in[l-1]$ have constant
row sum.

One way of finding perfect colorings on the Johnson graph $J(n,k)$ is by the
orbit construction method (see [2, Section 3]). Consider a graph $G$ on $n$
vertices. If there are $m$ orbits of $\operatorname{Aut}(G)$ acting on the set
of vertices of $J(n,k)$, then the orbits form a $m$-coloring. Depending on the
graph $G$ on $n$ vertices that was chosen for the construction, the
$m$-coloring obtained can be merged into a 2 or $3$-coloring. Most of the
perfect colorings in the literature are constructed using this method [2, 3].

##  3\. Symmetric Perfect $2$-colorings on $J(6,3)$

In [1], Gavrilyuk and Goryainov proved that a symmetric perfect $2$-coloring
with eigenvalues $\theta_{0}$, $\theta_{2}$ on $J(n,3)$ is possible only when
$n\in\\{6,10\\}$, and in this case the quotient matrix can only be
$\begin{bmatrix}2n-8&n-1\\\ n-1&2n-8\end{bmatrix}$. In [5], Avgustinovich and
Mogilnykh showed the following construction for the case $n=6$.

The graph $J(6,3)$ is antipodal of diameter 3, which means that for any vertex
$v$ there is a unique vertex at distance 3 from $v$. Two such vertices are
called antipodal vertices. $J(6,3)$ can be partitioned into 10 pairs of
antipodal vertices, which forms a perfect $10$-coloring with quotient matrix
$J-I$ (where $J$ is the all 1 matrix and $I$ the identity matrix). This
perfect $10$-coloring can be merged into a perfect $2$-coloring with quotient
matrix $\begin{bmatrix}4&5\\\ 5&4\end{bmatrix}$ by taking any two groups of
five pairs each.

$J(6,3)$ is small enough that a computer search can be used to list all
possible symmetric perfect $2$-colorings. It turns out that the only possible
ones are those mentioned above, and that they are all isomorphic to one of the
two perfect $2$-colorings $\\{X_{1},X_{2}\\}$ and
$\\{X^{\prime}_{1},X^{\prime}_{2}\\}$ which induced subgraphs are represented
below.

$X_{1}$$1,5,6$$1,4,5$$1,4,6$$1,3,4$$3,4,6$$2,3,4$$2,3,6$$2,3,5$$2,5,6$$1,2,5$$X_{2}$$1,2,3$$1,3,6$$1,3,5$$3,5,6$$3,4,5$$4,5,6$$2,4,5$$2,4,6$$1,2,4$$1,2,6$

$X^{\prime}_{1}$$1,2,5$$2,5,6$$1,5,6$$4,5,6$$3,5,6$$3,4,6$$1,3,4$$2,3,4$$1,2,3$$1,2,4$$X^{\prime}_{2}$$3,4,5$$2,4,5$$2,3,5$$2,3,6$$2,4,6$$1,2,6$$1,3,6$$1,4,6$$1,4,5$$1,3,5$

Figure 1. Induced subgraphs of symmetric perfect $2$-colorings of $J(6,3)$

It is interesting to consider the stabilizers of those perfect colorings in
the automorphism group of $J(6,3)$, which is known to be induced by the
symmetric group on $\\{1,\dots,6\\}$ and the complementation map (which maps
$3$-subsets to their complement in $\\{1,\dots,6\\}$) (see [8]). Since the
perfect $2$-colorings above are constructed from pairs of antipodal vertices,
they are invariant by the complementation map. Let $G$ be the group of
automorphisms of $J(6,3)$ induced by the symmetric group, $S$ be the
stabilizer of $\\{X_{1},X_{2}\\}$ in $G$, and $S^{\prime}$ the stabilizer of
$\\{X^{\prime}_{1},X^{\prime}_{2}\\}$.

The subgraph induced by $X_{1}$ contains 10 triangles that can be separated
into two types:

  * •

$\\{\\{a,b,c\\},\\{a,b,d\\},\\{a,b,e\\}\\}$, where $a,b,c,d,e$ are distinct
elements of $\\{1,\dots,6\\}$,

  * •

$\\{\\{a,b,c\\},\\{a,b,d\\},\\{a,c,d\\}\\}$, where $a,b,c,d$ are distinct
elements of $\\{1,\dots,6\\}$.

Every element $f\in S$ must induce an automorphism of $X_{1}$, and thus map
each triangle to a triangle of the same type. There are 5 triangles of the
first type, which are connected by a common vertex in the shape of a 5-cycle.
It follows that $S$ is isomorphic to the automorphism group of a 5-cycle,
which is the dihedral group with 10 elements.

The subgraph induced by $X^{\prime}_{1}$ contains two cliques (complete
subgraph) of size 4, of two different types:

  * •

$C_{1}:=\\{\\{a,b,c\\}\in\\{1,2,3,4\\}\mid a,b,c\text{ distinct}\\}$,

  * •

$C_{2}:=\\{\\{x,5,6\\}\mid x\in\\{1,2,3,4\\}\\}$.

Every element $f\in S^{\prime}$ must induce an automorphism of
$X^{\prime}_{1}$, and thus map each clique to itself. Thus

$\displaystyle S^{\prime}=$ $\displaystyle\Bigl{\\{}f\in G\mid
f(C_{1})=C_{1},f(C_{2})=C_{2},f(\\{\\{1,2,5\\},\\{3,4,6\\}\\})=\\{\\{1,2,5\\},\\{3,4,6\\}\\}\Bigr{\\}}$
$\displaystyle=$ $\displaystyle\Bigl{\\{}f\in G\mid
f(\\{1,2,3,4\\})=\\{1,2,3,4\\},f(\\{5,6\\})=\\{5,6\\},$ $\displaystyle
f(\\{\\{1,2,5\\},\\{3,4,6\\}\\})=\\{\\{1,2,5\\},\\{3,4,6\\}\\}\Bigr{\\}}$
$\displaystyle=$ $\displaystyle\Bigl{\\{}f\in G\mid
f(\\{1,2,3,4\\})=\\{1,2,3,4\\},f(\\{5,6\\})=\\{5,6\\},$ $\displaystyle
f(\\{1,2,5\\})=\\{1,2,5\\},f(\\{3,4,6\\})=\\{3,4,6\\}\Bigr{\\}}$
$\displaystyle\cup\Bigl{\\{}f\in G\mid
f(\\{1,2,3,4\\})=\\{1,2,3,4\\},f(\\{5,6\\})=\\{5,6\\},f(\\{1,2,5\\})=\\{3,4,6\\},$
$\displaystyle f(\\{3,4,6\\})=\\{1,2,5\\}\Bigr{\\}}$ $\displaystyle=$
$\displaystyle\Bigl{\\{}f\in G\mid
f(\\{1,2\\})=\\{1,2\\},f(\\{3,4\\})=\\{3,4\\},f(5)=5,f(6)=6\Bigr{\\}}$
$\displaystyle\cup\Bigl{\\{}f\in G\mid
f(\\{1,2\\})=\\{3,4\\},f(\\{3,4\\})=\\{1,2\\},f(5)=6,f(6)=5\Bigr{\\}}$
$\displaystyle=$
$\displaystyle\\{Id,(1,2),(3,4),(1,2)(3,4),(1,3)(2,4)(5,6),(1,4)(2,3)(5,6),(1,3,2,4)(5,6),$
$\displaystyle(1,4,2,3)(5,6)\\}$ $\displaystyle=$
$\displaystyle\langle(1,2),(1,3,2,4)(5,6)\rangle.$

This is isomorphic to the dihedral group with 8 elements.

##  4\. Symmetric Perfect $2$-colorings on $J(10,3)$

It is mentioned in [1] that for $J(10,3)$ there are only two non-isomorphic
perfect $2$-colorings with the symmetric quotient matrix
$\begin{bmatrix}12&9\\\ 9&12\end{bmatrix}$. But since a formal proof has never
been written, we will attempt to do it here by extending the method used in
[3] by R.J. Evans, A.L. Gavrilyuk, S. Goryainov and K. Vorob’ev.

There are two known non-isomorphic constructions of perfect $2$-colorings of
$J(10,3)$ with the above mentioned symmetric quotient matrix. One of the
construction was found by Gavrilyuk and Goryainov (but to our knowledge does
not appear in any publication), by using the orbit construction method from
two 5-cycles. The second construction can be found in [2, Construction 3],
using the same method from a complete bipartite graph with parts of size 5,
from which we remove a perfect matching.

What follows is a different construction for those two $2$-colorings.

Let $\mathcal{G}$ be the cycle graph on 10 vertices, and consider the action
of $\operatorname{Aut}(\mathcal{G})$ on $J(10,3)$. The group
$\operatorname{Aut}(\mathcal{G})$ is known as the dihedral group of order 20
consisting of 10 rotations (powers of the cycle permutation $(1,2,\dots,10)$ )
and 10 reflections. For instance it is generated by the two permutations
$(1,2,\dots,10)$ and $(2,10)(3,9)(4,8)(5,7)$. Thus the eight orbits of
$\operatorname{Aut}(G)$ acting on $J(10,3)$ are:

  * •

$A:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=1,d(b,c)=1,d(a,c)=2\\}$,

  * •

$B:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=1,d(b,c)=2,d(a,c)=3\\}$,

  * •

$C:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=1,d(b,c)=3,d(a,c)=4\\}$,

  * •

$D:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=1,d(b,c)=4,d(a,c)=5\\}$,

  * •

$E:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=2,d(b,c)=2,d(a,c)=4\\}$,

  * •

$F:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=2,d(b,c)=3,d(a,c)=5\\}$,

  * •

$G:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=2,d(b,c)=4,d(a,c)=4\\}$,

  * •

$H:=\\{\\{a,b,c\\}\in J(10,3)\mid d(a,b)=3,d(b,c)=3,d(a,c)=4\\}$.

These orbits corresponds to the 3 “types” of triple of points in the 10-cycle:

Figure 2. Visualisation of the orbits of $\operatorname{Aut}(\mathcal{G})$
acting on $J(10,3)$

This is a perfect $8$-coloring of $J(10,3)$ with quotient matrix

$\begin{bmatrix}2&6&4&4&2&2&1&0\\\ 3&3&4&2&2&4&1&2\\\ 2&4&3&4&1&2&2&3\\\
2&2&4&5&1&4&2&1\\\ 2&4&2&2&2&4&4&1\\\ 1&4&2&4&2&5&1&2\\\ 1&2&4&4&4&2&2&2\\\
0&4&6&2&1&4&2&2\\\ \end{bmatrix}$

that can be merged in two ways into perfect $2$-colorings. First by
$P_{1}:=A\cup B\cup C\cup H$ and $P_{2}:=D\cup E\cup F\cup G$, and secondly by
$P_{1}^{\prime}:=C\cup D\cup G\cup H$ and $P_{2}^{\prime}:=A\cup B\cup E\cup
F$. Those two perfect $2$-colorings are not isomorphic since it can be
computed that the subgraph of $J(n,3)$ induced by $P_{1}$ have different
eigenvalues than the one induced by $P_{1}^{\prime}$ or $P_{2}^{\prime}$.

##  5\. Classification

We now want to prove that $\\{P_{1},P_{2}\\}$ and
$\\{P^{\prime}_{1},P^{\prime}_{2}\\}$ are the only perfect $2$-colorings (up
to isomorphism). We will use the notations and tools of [1] and [3]. In the
rest of this section, we consider a perfect coloring of $J(10,3)$ into two
parts $X_{1},X_{2}$ such that the quotient matrix is $\begin{bmatrix}12&9\\\
9&12\end{bmatrix}$. A simple counting argument shows that
$|X_{1}|=|X_{2}|=60$.

We will denote $abc:=\\{a,b,c\\}$, $ab*:=\\{a,b,x\mid
x\in[10]\setminus\\{a,b\\}\\}$, and denote the intersection with $X_{1}$ in
this way: $\overline{abc}=1$ if $abc\in X_{1}$ and $0$ otherwise, and for
$S\subseteq J(10,3)$, $\overline{S}:=|S\cap X_{1}|$.

The method consists in looking at how the neighborhood of a point can be
distributed between the two parts. The subgraph of $J(10,3)$ induced by the
neighborhood of a point $abc$ is isomorphic to a 3 by 7 grid, and we can
represent its distribution among $X_{1}$ and $X_{2}$ by the nb-array [3]:

$\begin{matrix}&\overline{abd}&\overline{abe}&\overline{abf}&\dots&\dots&\dots&\dots&\leftarrow
ab\text{-row}\\\
N(abc):&\overline{acd}&\overline{ace}&\overline{acf}&\dots&\dots&\dots&\dots&\leftarrow
ac\text{-row}\\\
&\overline{bcd}&\overline{bce}&\overline{bcf}&\dots&\dots&\dots&\dots&\leftarrow
bc\text{-row}\\\ &\uparrow&\uparrow&\uparrow&\\\ &d&e&f&\cdots\end{matrix}$

The order of the rows and columns is arbitrary.

Most of the proof will rely on the following lemma from [3].

######  Lemma 1 ([3]).

For any five distinct elements $a,b,c,d,e\in[10]$, we have

$\overline{ab*}-\overline{ac*}=3(\overline{abd}+\overline{abe}+\overline{cde}-\overline{acd}-\overline{ace}-\overline{bde}).$

In particular, since $\overline{ab*}-\overline{abc}$ is the row sum of the row
$ab$ in $N(abc)$, we can see that the difference between two row sums in
$N(abc)$ is always a multiple of 3. Moreover each row consists of seven $0$
and $1$, so each row sum is between $0$ and $7$, and the difference between
two row sums is $0$, $3$ or $6$. And since when $\overline{abc}=1$ the total
sum of the nb-array must be 12, we have the following.

######  Lemma 2.

For $abc\in X_{1}$, the multiset of row sums of $N(abc)$ is among

$\\{3,3,6\\},\\{4,4,4\\},\\{2,5,5\\},\\{0,6,6\\},\\{1,4,7\\}.$

We also have as a direct consequence of 1 :

######  Lemma 3.

For any $a,b,c,d\in[10]$ with $a\neq b$ and $c\neq d$,
$\overline{ab*}\equiv\overline{cd*}\pmod{3}$.

Because of this, we can define the type of a part $X_{1}$ of a partition to be
$k\in\\{0,1,2\\}$ if for any distinct $a,b\in[10]$, $\overline{ab*}\equiv
k\pmod{3}$. When $\overline{abc}=1$, a row sum in $N(abc)$ must be
$k-1\pmod{3}$. So we can further restrict the possibilities in 2.

######  Lemma 4.

  1. 1.

If $X_{1}$ is of type 0, for $abc\in X_{1}$ the row sums of $N(abc)$ is
$\\{2,5,5\\}.$

  2. 2.

If $X_{1}$ is of type 1, for $abc\in X_{1}$ the row sums of $N(abc)$ is
$\\{3,3,6\\}$ or $\\{0,6,6\\}.$

  3. 3.

If $X_{1}$ is of type 2, for $abc\in X_{1}$ the row sums of $N(abc)$ is
$\\{4,4,4\\}$ or $\\{1,4,7\\}.$

We can also use 1 to eliminate some 2 by 2 patterns that can not appear in
$N(abc)$. For a row $r$ of $N(abc)$, denote by $\overline{r}$ the sum of the
row $r$. If we fix the order of rows and columns then nb-arrays can be seen as
matrices, so we will use matrices in the next lemma for convenience.

The next lemma is an extension of [3, Lemma 5.4].

######  Lemma 5.

Let $abc\in J(10,3)$ and $r_{1},r_{2}$ be two rows of $N(abc)$ such that
$\overline{r_{1}}\geq\overline{r_{2}}$. Then

  1. 1.

$\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$ is not a submatrix of
$\begin{bmatrix}r_{1}\\\ r_{2}\end{bmatrix}$,

  2. 2.

If $\overline{r_{1}}-\overline{r_{2}}\geq 3$ then $\begin{bmatrix}0&0\\\
0&1\end{bmatrix}$, $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$,
$\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$, $\begin{bmatrix}0&1\\\
1&1\end{bmatrix}$ are not submatrices of $\begin{bmatrix}r_{1}\\\
r_{2}\end{bmatrix}$,

  3. 3.

If $\overline{r_{1}}-\overline{r_{2}}=6$ then $\begin{bmatrix}0&0\\\
0&0\end{bmatrix}$, $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$,
$\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$, $\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$, $\begin{bmatrix}1&0\\\ 1&0\end{bmatrix}$,
$\begin{bmatrix}0&1\\\ 0&1\end{bmatrix}$ are not submatrices of
$\begin{bmatrix}r_{1}\\\ r_{2}\end{bmatrix}$.

From this lemma, the possible forms of $N(abc)$ can be restricted. For
convenience, in the lemmas below let $abc\in X_{1}$ and $N:=N(abc)$.

######  Lemma 6.

  1. 1.

If the row sums of $N$ are $\\{2,5,5\\}$, then $N$ is

(1) $\displaystyle\begin{matrix}&1&1&1&1&1&0&0\\\ &1&1&1&1&1&0&0\\\
&1&1&0&0&0&0&0\\\ \end{matrix}$ (2)
$\displaystyle\begin{matrix}&1&1&1&1&1&0&0\\\ \text{or }&1&1&1&1&0&1&0\\\
&1&1&0&0&0&0&0\\\ \end{matrix}$

  2. 2.

If the row sums of $N$ are $\\{3,3,6\\}$, then $N$ is

(3) $\displaystyle\begin{matrix}&1&1&1&1&1&1&0\\\ &1&1&1&0&0&0&0\\\
&1&1&0&1&0&0&0\\\ \end{matrix}$ (4)
$\displaystyle\begin{matrix}&1&1&1&1&1&1&0\\\ \text{or }&1&1&1&0&0&0&0\\\
&1&1&1&0&0&0&0\\\ \end{matrix}$

  3. 3.

If the row sums of $N$ are $\\{0,6,6\\}$, then $N$ is

(5) $\displaystyle\begin{matrix}&1&1&1&1&1&1&0\\\ &1&1&1&1&1&1&0\\\
&0&0&0&0&0&0&0\\\ \end{matrix}$ (6)
$\displaystyle\begin{matrix}&1&1&1&1&1&1&0\\\ \text{or }&1&1&1&1&1&0&1\\\
&0&0&0&0&0&0&0\\\ \end{matrix}$

  4. 4.

If the row sums of $N$ are $\\{4,4,4\\}$, then $N$ is

(7) $\displaystyle\begin{matrix}&1&1&1&1&0&0&0\\\ &1&1&1&1&0&0&0\\\
&1&1&1&1&0&0&0\\\ \end{matrix}$ (8)
$\displaystyle\begin{matrix}&1&1&1&1&0&0&0\\\ \text{or }&1&1&1&0&1&0&0\\\
&1&1&1&0&1&0&0\\\ \end{matrix}$ (9)
$\displaystyle\begin{matrix}&1&1&1&1&0&0&0\\\ \text{or }&1&1&1&0&1&0&0\\\
&1&1&1&0&0&1&0\\\ \end{matrix}$ (10)
$\displaystyle\begin{matrix}&1&1&1&1&0&0&0\\\ \text{or }&1&1&1&0&1&0&0\\\
&1&1&0&1&1&0&0\\\ \end{matrix}$

  5. 5.

If the row sums of $N$ are $\\{1,4,7\\}$, then $N$ is

(11) $\displaystyle\begin{matrix}&1&1&1&1&1&1&1\\\ &1&1&1&1&0&0&0\\\
&1&0&0&0&0&0&0\\\ \end{matrix}$

Now let us show that for each of the five situations above, all but one form
of $N$ lead to a contradiction when considering other points than $abc$.

######  Lemma 7.

If $N$ has row sums $\\{2,5,5\\}$, then $N$ is of the form (2).

###### Proof.

Suppose that $N$ has the form (1):

$\begin{matrix}&1&1&1&1&1&0&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&1&1&0&0&\leftarrow ac\text{-row}\\\ &1&1&0&0&0&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

From 1 we have
$1=\frac{1}{3}(\overline{ac*}-\overline{bc*})=\overline{bdi}-\overline{adi}$,
so $\overline{bdi}=1$. Similarly $\overline{bdj}=1$.

Thus

$\begin{matrix}&1&1&1&1&1&0&0&\leftarrow ab\text{-row}\\\
N(abd):&*&*&*&*&*&*&*&\leftarrow ad\text{-row}\\\ &*&*&*&*&*&1&1&\leftarrow
bd\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&c&e&f&g&h&i&j\end{matrix}$

where $*$ is either 0 or 1. But $abd\in X_{1}$ and this does not fit any nb-
array from 6, so we have a contradiction. (5 also gives a contradiction.) ∎

######  Lemma 8.

If $N$ has row sums $\\{3,3,6\\}$, then $N$ is of the form (3).

###### Proof.

Suppose that $N$ has the form (4):

$\begin{matrix}&1&1&1&1&1&1&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&0&0&0&0&\leftarrow ac\text{-row}\\\ &1&1&1&0&0&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Then from 1 we have
$1=\frac{1}{3}(\overline{ab*}-\overline{ac*})=\overline{cde}-\overline{bde}$
so $\overline{cde}=1$ and $\overline{bde}=0$. Also
$0=\frac{1}{3}(\overline{ac*}-\overline{bc*})=\overline{bde}-\overline{ade}$,
so $\overline{ade}=0$. For a similar reason $\overline{adf}=0$.

Thus

$\begin{matrix}&1&1&1&0&0&0&0&\leftarrow ac\text{-row}\\\
N(acd):&1&0&0&*&*&*&*&\leftarrow ad\text{-row}\\\ &*&*&*&*&*&*&*&\leftarrow
cd\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&b&e&f&g&h&i&j\end{matrix}$

But $acd\in X_{1}$ and this does not fit any nb-array from 6, so we have a
contradiction. (5 also gives a contradiction.) ∎

######  Lemma 9.

If $N$ has row sums $\\{0,6,6\\}$, then $N$ is of the form (6).

###### Proof.

Suppose that $N$ has the form (5):

$\begin{matrix}&1&1&1&1&1&1&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&1&1&1&0&\leftarrow ac\text{-row}\\\ &0&0&0&0&0&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Then from 1,
$2=\frac{1}{3}(\overline{ac*}-\overline{bc*})=1+\overline{bdj}-\overline{adj}$,
so $\overline{adj}=0$ and $\overline{bdj}=1$.

Thus

$\begin{matrix}&1&1&1&1&1&1&0&\leftarrow ab\text{-row}\\\
N(abd):&1&*&*&*&*&*&0&\leftarrow ad\text{-row}\\\ &0&*&*&*&*&*&1&\leftarrow
bd\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&c&e&f&g&h&i&j\end{matrix}$

Which does not fit any nb-array from 6 so we have a contradiction. ∎

######  Lemma 10.

If $N$ has row sums $\\{4,4,4\\}$, then $N$ is of the form (10).

###### Proof.

First we eliminate (8). Suppose that $N$ has the form (8):

$\begin{matrix}&1&1&1&1&0&0&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&0&1&0&0&\leftarrow ac\text{-row}\\\ &1&1&1&0&1&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Then from 1 we have
$0=\frac{1}{3}(\overline{ab*}-\overline{ac*})=1+\overline{cdg}-\overline{bdg}$
so $\overline{bdg}=1$ and $\overline{cdg}=0$. Also
$0=\frac{1}{3}(\overline{ac*}-\overline{bc*})=\overline{bdg}-\overline{adg}$,
so $\overline{adg}=1$. Furthermore
$0=\frac{1}{3}(\overline{ab*}-\overline{ac*})=-1+\overline{cdh}-\overline{bdh}$
so $\overline{cdh}=1$ and $\overline{bdh}=0$. And
$0=\frac{1}{3}(\overline{ac*}-\overline{bc*})=\overline{bdh}-\overline{adh}$
so $\overline{adh}=0$. Lastly
$0=\frac{1}{3}(\overline{ab*}-\overline{bc*})=\overline{cde}-\overline{ade}=\overline{cdf}-\overline{adf}$
so $\overline{cde}=\overline{ade}$ and $\overline{cdf}=\overline{adf}$

Thus

$\begin{matrix}&1&1&1&0&1&0&0&\leftarrow ac\text{-row}\\\
N(acd):&*&\alpha_{1}&\alpha_{2}&1&1&*&*&\leftarrow ad\text{-row}\\\
&*&\alpha_{1}&\alpha_{2}&0&0&*&*&\leftarrow cd\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&b&e&f&g&h&i&j\end{matrix}$

for some $\alpha_{1},\alpha_{2}\in\\{0,1\\}$. And since $acd\in X_{1}$ and
this does not match any pattern from 6, we have a contradiction.

Now we eliminate the case (7). Suppose that $N$ has the form (7):

$\begin{matrix}&1&1&1&1&0&0&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&1&0&0&0&\leftarrow ac\text{-row}\\\ &1&1&1&1&0&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Then from 1 it follows that for distinct $x,y\in\\{d,e,f,g,h,i,j\\}$,
$\overline{axy}=\overline{bxy}=\overline{cxy}$.

Thus

$\begin{matrix}&1&1&1&1&1&0&0&\leftarrow ab\text{-row}\\\
N(abh):&0&\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}&\alpha_{5}&\alpha_{6}&\leftarrow
ah\text{-row}\\\
&0&\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4}&\alpha_{5}&\alpha_{6}&\leftarrow
bh\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&c&d&e&f&g&i&j\end{matrix}$

for some $\alpha_{1},\dots,\alpha_{6}\in\\{0,1\\}$. Since $abh\in X_{2}$ the
sum of $N(abh)$ must be 9, and from 1 the difference between two row sums must
be a multiple of 3. Thus the row sums of $N(abh)$ are $\\{2,2,5\\}$, and from
5 we must have $\alpha_{5}=0$ and $\alpha_{6}=0$. Also, two of
$\alpha_{1},\dots,\alpha_{4}$ must be 1. Without loss of generality say
$\alpha_{1}=1$, so $\overline{adh}=\overline{bdh}=1$.

Then

$\begin{matrix}&1&1&1&1&0&0&0&\leftarrow ab\text{-row}\\\
N(abd):&1&\beta_{1}&\beta_{2}&\beta_{3}&1&\beta_{4}&\beta_{5}&\leftarrow
ah\text{-row}\\\
&1&\beta_{1}&\beta_{2}&\beta_{3}&1&\beta_{4}&\beta_{5}&\leftarrow
bh\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&c&e&f&g&h&i&j\end{matrix}$

where $\beta_{1},\dots,\beta_{5}\in\\{0,1\\}$. But since $abd\in X_{1}$,
$N(abd)$ must have the form (8) that we eliminated before. So we have a
contradiction.

Finally, we eliminate the case (9). Suppose that $N$ has the form (9):

$\begin{matrix}&1&1&1&1&0&0&0&\leftarrow ab\text{-row}\\\
N:&1&1&1&0&1&0&0&\leftarrow ac\text{-row}\\\ &1&1&1&0&0&1&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Then from 1 we have
$0=\frac{1}{3}(\overline{ab*}-\overline{bc*})=1+\overline{cgh}-\overline{agh}=1+\overline{cgj}-\overline{agj}$,
so $\overline{agh}=1$ and $\overline{agj}=1$. Also
$0=\frac{1}{3}(\overline{ab*}-\overline{ac*})=1+\overline{cdg}-\overline{bdg}$,
so $\overline{bdg}=1$.

Thus

$\begin{matrix}&1&1&1&1&0&0&0&\leftarrow ab\text{-row}\\\
N(abg):&1&*&*&*&1&*&1&\leftarrow ag\text{-row}\\\ &1&1&*&*&*&*&*&\leftarrow
bg\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&c&d&e&f&h&i&j\end{matrix}$

which, since $abg\in X_{1}$, gives a contradiction. ∎

Now only five cases remain from 6.

######  Proposition 11.

We have the following.

  1. 1.

If $X_{1}$ is of type 0, then for any $abc\in X_{1}$, $N(abc)$ has the form
(2).

  2. 2.

If $X_{1}$ is of type 1, then for any $abc\in X_{1}$, $N(abc)$ has the form
(3) or (6).

  3. 3.

If $X_{1}$ is of type 2, then for any $abc\in X_{1}$, $N(abc)$ has the form
(10) or (11).

These cases occur in the construction depicted at the beginning of the
section.

For the first perfect $2$-coloring $\\{P_{1},P_{2}\\}$, $P_{1}$ is of type 0
and $P_{2}$ is of type 2. When taking $X_{1}=P_{1}$, all of its vertices have
an nb-array of the form (2). When taking $X_{1}=P_{2}$, vertices from $E$ and
$G$ have an nb-array of the form (10), while vertices from $D$ and $F$ have an
nb-array of the form (11).

For the second perfect $2$-coloring $\\{P_{1}^{\prime},P_{2}^{\prime}\\}$,
$P_{1}^{\prime}$ and $P_{2}^{\prime}$ are both of type 1. When taking
$X_{1}=P_{1}^{\prime}$, vertices from $C$, $D$ and $H$ have an nb-array of the
form (3) and those from $G$ have the form (6). When taking
$X_{1}=P_{2}^{\prime}$, vertices from $A$, $B$ and $F$ have an nb-array of the
form (3) and those from $E$ have the form (6).

######  Theorem 12.

There is only one perfect $2$-coloring with a part of type 0, which is also
the only perfect $2$-coloring with a part of type 2, up to isomorphism.

###### Proof.

Denote $t_{1}$ the type of $X_{1}$ and $t_{2}$ the type of $X_{2}$. Since
$|ab*\cap X_{1}|+|ab*\cap X_{2}|=|ab*|=8$, we have $t_{1}+t_{2}\equiv
2\pmod{3}$. So if $X_{1}$ is of type 0 then $X_{2}$ is of type 2, and vice
versa. Therefore, it is enough to show that the perfect $2$-coloring with a
part of type 0 is unique.

Suppose that $X_{1}$ is of type 0, and fix $abc\in X_{1}$. Then from
Proposition 11

$\begin{matrix}&1&1&1&1&1&0&0&\leftarrow ab\text{-row}\\\
N(abc):&1&1&1&1&0&1&0&\leftarrow ac\text{-row}\\\ &1&1&0&0&0&0&0&\leftarrow
bc\text{-row}\\\
&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\uparrow&\\\
&d&e&f&g&h&i&j\end{matrix}$

Since the rest of the proof relies on many applications of 1 and is quite
fastidious, we will leave the verification to a computer.

We consider the 120 values $\overline{xyz}$ ($xyz\in J(10,3)$) as variables
for multivariate polynomials. The variables having $\\{0,1\\}$ values
translates to $\overline{xyz}^{2}-\overline{xyz}=0$. 1 and the values fixed in
$N(abc)$ also give some multivariate polynomials that must have value 0. The
ideal generated by these polynomials can be computed by magma.

We can then check if $\overline{xyz}=\epsilon$ ($\epsilon\in\\{0,1\\}$) can be
deduced by checking if $\overline{xyz}-\epsilon$ belongs to the ideal.
Moreover, we can check if
$\overline{xyz}=\overline{x^{\prime}y^{\prime}z^{\prime}}$ or
$\overline{xyz}\neq\overline{x^{\prime}y^{\prime}z^{\prime}}$ ($xyz$,
$x^{\prime}y^{\prime}z^{\prime}\in J(10,3)$) can be deduced by checking if
$\overline{xyz}-\overline{x^{\prime}y^{\prime}z^{\prime}}$ or
$\overline{xyz}+\overline{x^{\prime}y^{\prime}z^{\prime}}-1$ belongs to the
ideal.

In this way, 48 of the $\overline{xyz}$ values are deduced to be 1, and 48 of
them are 0. The remaining ones are separated into two groups $U_{1}$ and
$U_{2}$ of size 12, with identical value within a group. Since
$|X_{1}|=|X_{2}|=60$, there are two possibilities for the coloring
$(X_{1},X_{2})$, either the values in the group $U_{1}$ are 0 and those in the
group $U_{2}$ are 1, or the opposite. But it is computed in the magma code
that the transposition $(f,g)$ is an isomorphism between those two possible
colorings.

    J103:=Setseq(Subsets({1..10},3));
    R:=PolynomialRing(Rationals(),#J103);
    zo:={ R.i^2-R.i : i in {1..#J103} };
    pos:=func< a,b,c | R.Position(J103,{a,b,c}) >;
    abstar:=func< a,b | &+[ pos(a,b,x) : x in {1..10} | not x in {a,b} ] >;
    lem1:=func< a,b,c,d,e | abstar(a,b)-abstar(a,c)-3*(
     pos(a,b,d)+pos(a,b,e)+pos(c,d,e)-pos(a,c,d)-pos(a,c,e)-pos(b,d,e) ) >;
    lem1s:={ lem1(a,b,c,d,e) : a,b,c,d,e in {1..10} | #{a,b,c,d,e} eq 5 };
    prop12:={ pos(xyz[1],xyz[2],xyz[3])-1 : xyz in
      { [1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],
       [1,3,4],[1,3,5],[1,3,6],[1,3,7],[1,3,9],
       [2,3,4],[2,3,5] } } join
     { pos(xyz[1],xyz[2],xyz[3]) : xyz in
      { [1,2,9],[1,2,10],[1,3,8],[1,3,10],[2,3,6],[2,3,7],[2,3,8],[2,3,9],
       [2,3,10] } };
    I:=ideal< R | zo join lem1s join prop12 >;

    known1:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and pos(a,b,c)-1 in I };
    #known1 eq 48;
    known0:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and pos(a,b,c) in I };
    #known0 eq 48;

    pos(1,4,6)+pos(1,4,7)-1 in I;

    unknown1:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and
     pos(a,b,c)-pos(1,4,6) in I};
    unknown2:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and
     pos(a,b,c)-pos(1,4,7) in I};
    #unknown1 eq 12;
    #unknown2 eq 12;
    #(known0 join known1 join unknown1 join unknown2) eq 120;

    t:=Sym(10)!(6,7);
    G:=GSet(Sym(10),Subsets({1..10},3));
    {Image(t,G,X) : X in known0} eq known0;
    {Image(t,G,X) : X in known1} eq known1;
    {Image(t,G,X) : X in unknown1} eq unknown2;

∎

######  Theorem 13.

There is only one perfect $2$-coloring with a part of type 1 up to
isomorphism.

###### Proof.

Suppose that $X_{1}$ is of type 1 and fix $abc\in X_{1}$. Then from
Proposition 11, $N(abc)$ has the form (3) or (6). If $N(abc)$ has the form
(6), then the second part of the magma code shows that there exists an element
of $X_{1}$ which has an nb-array of the form (3). The case (3) is very similar
to the proof of Proposition 11 so we will give an almost identical magma code.

    // Case (3)

    prop14:={ pos(xyz[1],xyz[2],xyz[3])-1 : xyz in
      { [1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],
       [1,3,4],[1,3,5],[1,3,6],
       [2,3,4],[2,3,5],[2,3,7] } } join
     { pos(xyz[1],xyz[2],xyz[3]) : xyz in
      { [1,2,10],
       [1,3,7],[1,3,8],[1,3,9],[1,3,10],
       [2,3,6],[2,3,8],[2,3,9],[2,3,10] } };
    I:=ideal< R | zo join lem1s join prop14 >;

    known1:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and pos(a,b,c)-1 in I };
    #known1 eq 48;
    known0:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and pos(a,b,c) in I };
    #known0 eq 48;

    pos(1,5,8)+pos(1,5,9)-1 in I;

    unknown1:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and
     pos(a,b,c)-pos(1,5,8) in I};
    unknown2:={ {a,b,c} : a,b,c in {1..10} | #{a,b,c} eq 3 and
     pos(a,b,c)-pos(1,5,9) in I};
    #unknown1 eq 12;
    #unknown2 eq 12;
    #(known0 join known1 join unknown1 join unknown2) eq 120;

    t:=Sym(10)!(8,9);
    G:=GSet(Sym(10),Subsets({1..10},3));
    {Image(t,G,X) : X in known0} eq known0;
    {Image(t,G,X) : X in known1} eq known1;
    {Image(t,G,X) : X in unknown1} eq unknown2;

    // Case (6)

    prop14prime:={ pos(xyz[1],xyz[2],xyz[3])-1 : xyz in
      { [1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],
       [1,3,4],[1,3,5],[1,3,6],[1,3,7],[1,3,8],[1,3,10] } } join
     { pos(xyz[1],xyz[2],xyz[3]) : xyz in
      { [1,2,10],
       [1,3,9],
       [2,3,4],[2,3,5],[2,3,6],[2,3,7],[2,3,8],[2,3,9],[2,3,10] } };
    Iprime:=ideal< R | zo join lem1s join prop14prime >;

    abstar(3,4)-4 in Iprime;
    abstar(4,10)-4 in Iprime;
    abstar(3,10)-7 in Iprime;

∎

##  6\. Conclusion

By a proof similar to Theorem 12, we can see that a perfect $2$-coloring with
a part of type 1 must have the other part also of type 1. Thus, these last two
theorems show that there are only two symmetric perfect $2$-colorings of
$J(10,3)$ associated to $\theta_{2}$. One of them has parts of type 0 and 2,
and the other one has both parts of type 1. Theorem 13 also implies that the
two parts of the perfect $2$-coloring with parts of type 1 are isomorphic to
each other.

##  7\. Acknowledgement

I am grateful to Prof. Akihiro Munemasa for his continuous guidance through
this study, and his idea to consider an ideal membership problem for the
resolutions by computer.

I am also thankful to Prof. Alexander Gavrilyuk and Prof. Sergey Goryainov for
their insight on the known constructions of symmetric perfect $2$-colorings of
$J(10,3)$, and for indicating me that the problem resolved in this paper was
still open.

This work was supported by JST SPRING (Grant Number JPMJSP2114).

## References

  * [1] Alexander L. Gavrilyuk, Sergey V. Goryainov. On perfect $2$-colorings of Johnson graphs $J(v,3)$. 2012. J. Combin. Designs 21: 232–252, 2013.
  * [2] S. V. Avgustinovich, I. Yu. Mogil’nykh. Perfect colorings of the Johnson graphs $J(8,3)$ and $J(8,4)$ with two Colors. J. Appl. Ind. Math. 5, 19–30 (2011).
  * [3] R.J. Evans, A.L. Gavrilyuk, S. Goryainov, K. Vorob’ev. Equitable 2-partitions of the Johnson graphs $J(v,3)$ . 2022. arXiv:2206.15341v2 [math.CO].
  * [4] Konstantin Vorob’ev. Equitable 2-partitions of Johnson graphs with the second eigenvalue. 2020. arXiv:2003.10956v1 [math.CO].
  * [5] Avgustinovich, S., Mogilnykh, I. (2008). Perfect $2$-Colorings of Johnson Graphs $J(6,3)$ and $J(7,3)$. In: Barbero, Á. (eds) Coding Theory and Applications. Lecture Notes in Computer Science, vol 5228. Springer, Berlin, Heidelberg.
  * [6] William J. Martin. Completely regular designs of strength one. Journal of Algebraic Combinatorics, 3(2):170–185, 1994.
  * [7] Aaron D. Meyerowitz. Cycle-balanced partitions in distance-regular graphs. Discrete Mathematics, 264:149–165, 2003.
  * [8] S. Morteza Mirafzal. A note on the automorphism groups of Johnson graphs. 2017. arXiv:1702.02568v4 [math.CO].