MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
By your definition, I think you mean this notation: $\overline{H_{n}^{k}}$. Is it true? – Zahra Taheri 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.

share|cite|improve this answer
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 rewrote my answer so that it makes sense (hopefully). – Dima Pasechnik Jul 7 '12 at 15:39
I know nearly nothing on Delsarte / Lovasz bounds, let alone on how to compute them using linear programming. However, if you could get any non-trivial estimates in this way, I would be very much interesting to know that. – Seva Jul 7 '12 at 15:45
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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