5
$\begingroup$

Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of positive, negative and zero eigenvalues? Thank you.

$\endgroup$
  • $\begingroup$ To add context, the following is related: mathoverflow.net/questions/294675/… $\endgroup$ – Peter Heinig Mar 18 '18 at 12:15
  • $\begingroup$ yes, indeed, this is very much related - different graph built from the same Hamming association scheme H(n,2) $\endgroup$ – Dima Pasechnik Mar 18 '18 at 23:07
  • $\begingroup$ Do you mean "at least $d$" or "at most $d$"? $\endgroup$ – David G. Stork Mar 19 '18 at 19:02
  • 1
    $\begingroup$ I do mean "at least" and I am specifically interested when d = n/2. I am building on the paper "On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination" by Briet and Zuiddam. $\endgroup$ – Clive elphick Mar 20 '18 at 9:00
  • $\begingroup$ see my edited answer for a conjecture for this case; it's kind of pretty :-) $\endgroup$ – Dima Pasechnik Mar 20 '18 at 17:23
5
$\begingroup$

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$. The multiplicities are given by the binomial coefficients $\binom{n}{j}$, $0\leq j\leq n$, also this is what you get in the 1st row of $P$.


Here are the experimental results; I coded up this in Sagemath and computed the number $p(d)$ of positive eigenvalues of $H_2^{2d}(d)$ for $1\leq d\leq 18$. Here is what I got

[1,6,36,136,496,2016,8256,32896,130816,523776,2098176, 8390656,33550336,134209536,536887296,2147516416,8589869056,34359607296]

While the usual interface does not produce a match, Superseeker does tell me a lot, e.g. it says that

Guesss (a program by Harm Derksen) suggests that the generating function $F(x)$ may satisfy the following algebraic or differential equation:

$$x^2+1/8 x+1/16+(x^3-1/4 x^2+1/4 x-1/16)F(x) = 0$$

as well as that the exponential generating function for this sequence is $$2 \exp(4 x) - \sin(2 x) - \cos(2 x).$$

Thus, conjecturally, this is the answer for the number $p(d)$ of positive eigenvalues; there are no 0 eigenvalues, and the number of the negative ones is just $2^{2d}-p(d).$


But in fact it's much easier to state, namely, conjecturally $$ \frac{2^{2d}-2p(d)}{2^d}= \begin{cases} 1 &\text{if $d\mod 4\in\{1,2\}$ and}\\ -1 &\text{otherwise.} \end{cases} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.