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.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ To add context, the following is related: mathoverflow.net/questions/294675/… $\endgroup$– Peter HeinigCommented Mar 18, 2018 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 PasechnikCommented Mar 18, 2018 at 23:07
-
$\begingroup$ Do you mean "at least $d$" or "at most $d$"? $\endgroup$– David G. StorkCommented Mar 19, 2018 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 elphickCommented Mar 20, 2018 at 9:00
-
$\begingroup$ see my edited answer for a conjecture for this case; it's kind of pretty :-) $\endgroup$– Dima PasechnikCommented Mar 20, 2018 at 17:23
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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} $$
answered Mar 18, 2018 at 10:51