# The chromatic number of a Hamming-related graph

For integer $1\le k\le n$, let ${\overline H}_n^k$ denote the complement of the $k$-th power of the Hamming graph on the vertex set ${\mathbb F}_2^n$; that is, two vectors from ${\mathbb F}_2^n$ are adjacent in ${\overline H}_n^k$ whenever they differ in $k+1$ coordinates at least. What is the chromatic number of this graph?

Assuming for simplicity that $k$ is even, the Kneser graph $G_{n,k/2+1}$ is a subgraph of ${\overline H}_n^k$. As a result, $$\chi({\overline H}_n^k) \ge \chi(G_{n,k/2+1})=n-k.$$ Improving upon this estimate (for $k$ close to $n$) would yield an improved bound for the number of Hamming spheres, needed to cover the whole space ${\mathbb F}_2^n$ (see this MO post).

-
By your definition, I think you mean this notation: $\overline{H_{n}^{k}}$. Is it true? –  Zahra Jul 7 '12 at 12:28
@Zahra: correct. –  Seva Jul 7 '12 at 13:32

(Edited after it was pointed out that the original answer made no sense).

In coding theory one is interested in upper bounds on the clique number $\omega$ of $\Gamma:=\overline{H}_n^k$, as such cliques are exactly binary codes of minimal distance $k$. There is huge amount of literature on this. The Delsarte bound, also known as Schrijver's $\theta'$ (see his paper called "Comparison of Delsarte and Lovasz bounds" from 1979), is particularly interesting, as it is known to be "sandwiched" between $\omega$ and $\chi:=\chi(\Gamma)$, i.e. $\omega\leq\theta'\leq\theta\leq\chi$, where $\theta$ is Lovasz's $\theta$ function of the graph. (More precisely, $\theta$ and $\theta'$ are usually defined for the complement of the graph, but that's a minor notational issue).

And so $\theta$ and $\theta'$ are lower bounds on $\chi(\Gamma)$.

By the way, both $\theta$ and $\theta'$ can be computed by linear programming in this case.

In a nutshell, $\theta$ and $\theta'$ can be described for this case as follows. Let $A_m$ denote the adjacency matrix of the graph on the $n$-binary words, vertices adjacent iff the corr. words are at Hamming distance $m$. E.g. the adjacency matrix of $\Gamma$ equals $\sum_{m\geq k} A_m$
Let $v$ be the $0-1$ indicator vector of a clique in $\Gamma$. Then one can computed the Frobenius scalar product of $vv^\top$ and each $A_k$, and it stays the same if we replace $vv^\top$ by its average $V$ over the group of automorphisms of the Hamming space. Now, $V$ can also be written as a linear combination of $A_m$'s. Thinking of $V$ as an unknown positive semidefinite matrix, one thinks of the latter expression with unknown coefficients $x_m$, and the clique size is an linear function $f(x)$ in $x_m$. The matrices $A_m$ commute with each other, so we can simultaneously diagonalize them. As a result we get a system of inequalities (and thus a linear program with the objective function $f(x)$) with $x_m$'s variables, from the fact that the eigenvalues of $V$ are nonnegative.
There are variations as to whether to demand $x_m\geq 0$ or not, this gives one $\theta'$, resp. $\theta$, as the optimum of the linear program I just mentioned.
Thanks for your remark but I think that, in fact, any lower bound for the clique number of ${\overline H}_n^k$ is a lower bound for $\chi({\overline H}_n^k)$, and it seems unlikely that good bounds can be obtained in this way. Say, if $k>2n/3$, then the clique number of ${\overline H}_n^k$ is $2$, while we actually have the much stronger bound $\chi({\overline H}_n^k)\ge n-k$. –  Seva Jul 7 '12 at 14:24
you are right, I didn't think straight here :) What I meant to say was that if you know the size of a code of minimal distance $k$ then this gives you a lower bound on $\chi$. Or you might look at the Lovasz $\theta$ of your graph (which can be computed by linear programming, in fact), and it will give you a lower bound on $\chi$. –  Dima Pasechnik Jul 7 '12 at 14:54
I've added above a explanation about Delsarte / Lovasz bounds. If I see this right, the number of variables in the underlying linear program is something like $n-k+1$, so for $k$ very close to $n$ one might have a fighting chance to get something out of this. –  Dima Pasechnik Jul 7 '12 at 16:53