The spectral properties of Johnson graphs are known. However I also like to know more about their eigenvectors. Are there any results on the eigenvectors of the graph Laplacians of these Johnson graphs?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Since the Johnson graphs are regular, the Laplacian eigenvectors are the eigenvectors of the adjacency matrix. The Johnson graphs belong to an association scheme, the Johnson scheme, and explicit expressions for the matrices that represent projections onto the eigenspaces are known, and thus we have explicit expressions for spanning sets of eigenvectors. The obvious source for me to cite is my book with Meagher "Erdos-Ko-Rado Theorems", but expressions for the idempotents are given in many places, going back to Delsarte's Ph.D. thesis (which you can find online).
answered Sep 21, 2017 at 12:24
-
1$\begingroup$ Experimentally, $J(n,k)$, which has $\binom nk$ vertices, has $\min(k,n-k)+1$ distinct eigenvalues that are all integers. The smallest is $-\min(k,n-k)$, and of course the largest is the degree. I tested all cases to $n=12$. $\endgroup$ Commented Sep 22, 2017 at 5:56
$\begingroup$
$\endgroup$
These questions are all answered in the Wikipedia article Johnson graph. As Chris noted, it doesn't matter if you consider the adjacency matrix or the Laplacian matrix. The eigenvectors stay the same and the eigenvalues also stay the same except that the simple eigenvalue equal to the degree becomes 0 for the Laplacian.
answered Sep 22, 2017 at 6:00
$\begingroup$
$\endgroup$
With Chris' and Brendan's feedback, I found Delsarte's and Levenstein's paper on Association schemes and coding theory which explicitly gives the solution for this. The idempotents of the Johnson scheme are the eigenprojectors, and can be written as linear combinations of the generalized adjacency matrices, where the coefficients are given by Hahn polynomials.