Skip to main content
2 of 6
explained more
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

Such graphs are studied a lot in coding theory and in the theory of association schemes. In paricular the eigenvalues can be explicitly written down in terms of Krawchuk polynomials $K_k(u)$.

You can find this e.g. in Bannai & Ito "Association Schemes I": https://www.amazon.com/Algebraic-Combinatorics-Association-Schemes-Mathematics/dp/0805304908

I never saw inertia of these graphs mentioned anywhere, but it looks easy to figure out.

To give you an idea, the eigenvalues of the relations of the Hamming scheme $H(n,2)$ (that is, the $n+1$ adjacency matrices $A_j$ of graphs $\Gamma_j$ ($0\leq j\leq n$) partitioning $K_{2^n}$, so that two vertices of $\Gamma_j$ are adjacent if the Hamming distance between them is $j$, may be compactly presented (discounting multiplicities) as an $(n+1)\times (n+1)$ matrix $P$, with $j$-column containing the eigenvalues of $A_j$, and $j$-th row containing the eigenvalues corresponding to the $j$-th common eigenspace of $A_j$'s (the latter works as $A_j$'s pairwise commute).

In general, the entries of $P$ are given by $$ \newcommand{\kk}{k} \newcommand{\uu}{u} P_{ku}=K_{\kk}(\uu)=\binom{n}{\kk}\sum_{j=0}^k \frac{(-\kk)_j(-\uu)_j 2^j}{(-n)_j j!}=\binom{n}{\kk}\sum_{j=0}^k (-1)^j 2^j \frac{\binom{u}{j}\binom{k}{j}}{\binom{n}{j}} $$

To get the eigenvalues of $H_2^n(d)$ you just need to sum up the last $n-d+1$ columns of $P$.

Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70