On equitable 2-partitions of Johnson graphs with the second eigenvalue

The vertices of a Johnson graph $J(n,w)$, $n\ge 2w$, are all $w$-subsets of a fixed $n$-set. Two vertices are adjacent if and only if they have $w-1$ joint elements. This graph is distance-regular with $w+1$ distinct eigenvalues $\lambda_i (n,w)=(w-i)(n-w-i)-i$, $i=0,1,\ldots w$.

Given a graph $G$, a partition $(C_1, \ldots, C_r)$ of its vertex set into $r$ cells is called an equitable partition with a quotient matrix $A=(a_{ij})$ if for any $i,j \in \{1, \ldots, r \}$ every vertex from $C_i$ has exactly $a_{ij}$ neighbors in $C_j$. An eigenvalue of the quotient matrix $A$ is called an eigenvalue of the partition.

We consider equitable $2$-partitions of a Johnson graph $J(n,w)$ with a quotient matrix having eigenvalue $\lambda_2 (n,w)$. The problem of existence of equitable $2$-partitions of Johnson graphs with given quotient matrix is far from solving. In particular, it includes a famous Delsarte's conjecture about non-existence of $1$-perfect codes in the Johnson scheme.

One of possible ways is to characterise partitions with certain eigenvalues. Equitable $2$-partitions of the graph $J(n,w)$ with the eigenvalue $\lambda_1 (n,w)$ were characterized by Meyerowitz [1]. Later, Gavrilyuk and Goryainov [2] found all realizable quotient matrices (i.e. quotient matrices of some existing partitions) of equitable $2$-partitions of $J(n,3)$ for odd $n$.

In these work we consider equitable $2$-partitions of $J(n,w)$ with the second eigenvalue $\lambda_2(n,w)$ for $w\ge 4$. As the main result, we find all such realizable quotient matrices. Moreover, we characterize all equitable $2$-partitions with these matrices up to equivalence in cases $n>2w$ and $n=2w$, $w \ge 7$. Particularly, we find new infinite series of partitions of $J(2w,w)$ for $w \ge 4$.

[1] A. Meyerowitz, Cycle-balanced Conditions for Distance-regular Graphs, Discrete Mathematics 264 (2003), N3, 149—166.

[2] A. L. Gavrilyuk, S. V. Goryainov, On perfect 2-colorings of Johnson graphs J(v,3), Journal of Combinatorial Designs 21, (2013), N6, 232—252.