19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

# On Equitable Partitions of the Johnson Graph

Presented by Prof. Vladislav KABANOV

Type: Oral presentation

Track: Representations of Graphs

## Content

\documentclass[twoside]{article}
\begin{document}
\title{On Equitable Partitions of the Johnson Graph}
\author{A.\,L.~Gavrilyuk, S.\,V.\,Goryainov, and V.\,V.\,Kabanov}
\maketitle
The {\it Johnson graph} $J(n,m)$ is the graph whose vertices are all binary vectors of length~$n$ and weight~$m$ and in which any two vectors are adjacent if and only if they differ by exactly two coordinates.
A $t-(n,k,\lambda)$-scheme is a set of $k$-element subsets ({\it blocks}) of an $n$-element set such that each of its $t$-element subsets is contained in exactly~$\lambda$ blocks.
A {\it perfect coloring} (an {\it equitable partition}) of a graph~$\Gamma$ into~$t$ colors (in what follows, a $t$-coloring) is a partition of the vertex set of~$\Gamma$ into~$t$ classes (colors) $C_1,\dots,C_t$ such that, for any $i,j\in \{1,\dots,t\}$, any vertex from the class~$C_i$ is adjacent to the same number of vertices, namely,~$c_{ij}$ vertices, from the class~$C_j$. The matrix $C=(c_{ij})_{i,j=1,\dots,t}$ is called the parameter matrix of the $t$-coloring. We do not distinguish between colorings obtained by renaming the colors (i.e., by equal permutations of rows and columns of the matrix~$C$).
The investigation of perfect colorings of Johnson graphs (and other graphs~\cite{ggk1}) is related to generalizations of some problems from coding theory~\cite{ggk2} and is of independent interest for the theory of distance-regular graphs~\cite{ggk3}, in particular, for the theory of graphs from finite geometries~\cite{ggk4}. Further definitions and the history of the problem can be found in~\cite{ggk4,ggk5}, where the study of 2-colorings of Johnson graphs with small parameters was started. In particular, the question on the existence of a 2-coloring of the graph $J(9,3)$ with matrix
$\left ( \begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$
was posed in~\cite{ggk5}. In the present research, we answer this question in the negative.
{\bf Theorem 1.} {\em The Johnson graph $J(9,3)$ has no $2$-colorings with matrix
$\left (\begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$.}
Let us consider some 2-coloring of the graph $J(n,m)$ (without loss of generality, $2m\le n$) with matrix~$C$. It is known \cite[Assertion~2]{ggk5} that, in this case, the number $c_{11}-c_{21}$ is one of the~$m$ nonprincipal eigenvalues $\theta_k=(m-k)(n-m-k)-k$ of the graph, where~$k=1,\dots,m$.
Let $m=3$. If $c_{11}-c_{21}=\theta_1$, then \cite[Theorem~4]{ggk5} there exists a unique coloring; its scheme was given in~\cite[Sect.~2]{ggk5}.
If $c_{11}-c_{21}=\theta_3=-3$, then, in view of~\cite[Assertion~3]{ggk5}, the existence of a coloring with this property is equivalent to the existence of a scheme with parameters $2-(n,3,c_{21}(n-2)/(c_{12}+c_{21}))$, and there are known criteria for the existence of such a scheme, see~\cite[Theorem~2]{ggk5}. Finally, in the case $c_{11}-c_{21}=\theta_2$, the authors do not know strong necessary conditions for the existence of a coloring with matrix~$C$. For $n=9$, the following two parameter matrices satisfy the known necessary conditions:
$\left (\begin{array}{cc} 10 & 8 \\ 8 & 10 \end{array} \right )$
and
$\left (\begin{array}{cc} 6 & 12 \\ 4 & 14 \end{array} \right )$.
The nonexistence of the latter was established in~\cite{ggk6}, and the nonexistence of the former is proved in the present study. Thus, the obtained result completes the description (the list of admissible matrices) of 2-colorings of the Johnson graph $J(9,3)$.
Note that the methods used in the proof of Theorem~1 allow us to proof a more general result.
{\bf Theorem 2.} {\em
If $n$ is odd, then the Johnson graph $J(n,3)$ has no $2$-colorings with a symmetric matrix~$C$ such that $c_{11}-c_{21}=\theta_2$.}
It is interesting that the analog of Theorem~2 for the case of even~$n$ is not true in the general case: for $n=6$, there exists a coloring with matrix
$\left(\begin{array}{cc} 6 & 3 \\ 3 & 6 \end{array}\right)$,
which was found in~\cite{ggk7} based on the antipodality of the Johnson graph $J(2m,m)$. For even $n>6$, the problem has not been solved yet. Let us note, however, that~$n$ must be congruent to~2 modulo~4. Therefore, a coloring of the graph $J(10,3)$ with matrix
$\left (\begin{array}{cc} 12 & 9 \\ 9 & 12 \end{array} \right )$
is an open case with the smallest number of vertices.
\smallskip
The first author was supported by the Russian President's grant for young scientist no.~MK-938.2011.1.
\begin{thebibliography}{999}
\bibitem{ggk1}
D. G. Fon-der-Flaass, Perfect 2-colorings of a hypercube. Siberian Math. J. {\bf 48} (2007), no.~4, 740--745.
\bibitem{ggk2}
I. Yu. Mogil'nykh, On the regularity of perfect 2-colorings of the Johnson graph. Probl. Inf. Transm. {\bf 43} (2007), no.~4, 303--309.
\bibitem{ggk3}
A. E. Brouwer, A. M.Cohen, and A. Neumaier, {\it Distance-Regular Graphs} (Springer-Verlag, Berlin, 1989).
\bibitem{ggk4}
B. De Bruyn and H. Suzuki, Intriguing sets of vertices of regular graphs, Graphs Combin. {\bf 26} (2010), no.~5, 629--646.
\bibitem{ggk5}
S. V. Avgustinovich and I. Yu. Mogil'nykh, Perfect 2-colorings of the Johnson graphs $J(8,3)$ and $J(8,4)$. Diskretn. Anal. Issled. Oper. {\bf 17} (2010), no.~2, 3--19.
\bibitem{ggk6}
I. Yu. Mogil'nykh, On the nonexistence of some perfect 2-colorings of Johnson graphs. Diskretn. Anal. Issled. Oper. {\bf 16} (2009), no.~5, 52--68.
\bibitem{ggk7}
I. Yu. Mogil'nykh and S. V. Avgustinovich, Perfect 2-colorings of Johnson graphs $J(6,3)$ and $J(7,3)$. Lect. Notes Comp. Sci. {\bf 5228} (2008), 11--19.
\end{thebibliography}
\end{document}

## Place

Location: Bled, Slovenia

Address: Best Western Hotel Kompas Bled

## Primary authors

- Dr. Alexander GAVRILYUK Institute mathematics and mechanics of Ural Branch of Russian Academy of Sciences

## Co-authors

- Mr. Sergej GORYAINOV Cheljabinsk State University
- Prof. Vladislav KABANOV Institute mathematics and mechanics of Ural Branch of Russian Academy of Sciences