3
$\begingroup$

I have stumbled upon the problem of diagonalizing the matrix of a Johnson graph $(N,k)$ with $k=2$. From Wikipedia and several other references I found the explicit form for the eigenvalues https://en.wikipedia.org/wiki/Johnson_graph or C,Godsil, Erdos-Ko-Rado theorems: algebraic approaches, theorem $6.3.2$. The provided explicit representation of the eigenvectors is not so easy to handle in my context.

Yet I have the intuition that the adjacency matrix of $\operatorname J(N,2)$ could be brought into a circulant (symmetric) form. If so, the explicit form of the eigenvectors would be very easy.

Am I right to think about the circulant structure of the Johnson Graph $(N,2)$?

Intuitively it comes from the idea that the graph is a regular graph on a ring, and also the picture of a specific case in the wiki page adds to the idea. Any proof of this conjecture would be very appreciated.

$\endgroup$
1
  • 3
    $\begingroup$ You should not trust intuition that a regular graph drawn in a circle is a circulant graph. Circulant graphs are very rare, and Hamiltonian regular graphs are very common (in fact, almost all regular graphs are Hamiltonian). $\endgroup$ Commented Apr 10 at 14:37

2 Answers 2

6
$\begingroup$

No, the Johnson graph $J(n,2)$ is not a circulant graph, at least not for $n>4$. (Since $J(3,2)$ is a complete graph and $J(4,2)$ is the octahedral graph, they are both circulant graphs.)

We can characterize circulant graphs in terms of their automorphisms: it must have an automorphism which is a cyclic permutation of its vertices. (In the picture of circulant graphs arranged in a circle, this is the automorphism that rotates all the vertices one space around the circle.)

The symmetry group of the Johnson graph $J(n,k)$ is known, and except when $n=2k$, it is the symmetric group $S_n$. Moreover, we know the way $S_n$ acts on $J(n,k)$: if $\sigma \in S_n$ and $\{a_1, a_2, \dots, a_k\} \in V(J(n,k))$, then $\sigma$ sends this vertex to $\{\sigma(a_1), \sigma(a_2), \dots, \sigma(a_k)\}$. (Here, we take the usual interpretation of the vertices of the Johnson graph as $k$-element subsets of $\{1,2,\dots,n\}$, with edges between subsets that share $k-1$ elements.)

In the $k=2$ case, can we find an element $\rho$ of $S_n$ which has order $\binom n2$ and will act on the vertices by a cyclic permutation? We look at the cycle decomposition of $\rho$ for that. The order of $\rho$ is too big for $\rho$ to be a single cycle, so it factors as multiple disjoint cycles $\rho_1 \rho_2 \cdots \rho_m$, which we assume all have length at least $2$. Let $I \subseteq \{1,2,\dots,n\}$ be the elements permuted by $\rho_1$. Then for any vertex $v$ which is a $2$-element subset of $I$, $\rho(v) = \rho_1(v)$ is another $2$-element subset of $I$, and so $\rho$ does not act transitively on $V(J(n,2))$. This shows that the Johnson graph cannot be a circulant graph.

$\endgroup$
6
$\begingroup$

sage is my weapon of choice. It comes with an implementation of the Johnson graph, and so using graph tools in general, delivers further useful information. It may be of interest. The appended code delivers then the following information:

N is_circulant eigenvalues
$1$ True $[]$
$2$ True $[0]$
$3$ True $[2, -1, -1]$
$4$ True $[4, -2, -2, 0, 0, 0]$
$5$ False $[6, 1, 1, 1, 1, -2, -2, -2, -2, -2]$
$6$ False $[8, 2, 2, 2, 2, 2, -2, -2, -2, -2, -2, -2, -2, -2, -2]$
$7$ False $[10, 3, 3, 3, 3, 3, 3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2]$
$8$ False $[12, 4, 4, 4, 4, 4, 4, 4, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2]$
$9$ False $[14, 5, 5, 5, 5, 5, 5, 5, 5, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2]$
$10$ False $[16, 6, 6, 6, 6, 6, 6, 6, 6, 6, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2]$

sage code:

for N in [1..10]:
    G = graphs.JohnsonGraph(N, 2)
    A = G.adjacency_matrix()
    print(f"| ${N}$ | {G.is_circulant()} | ${A.eigenvalues()}$ |")
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .