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

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

2 Answers 2


This is pretty late, but there is a result by Frankl and Rodl (Theorem 1.11 from http://www.renyi.hu/~pfrankl/1987-3.pdf) that shows that the graph on $\mathbb{F}_2^n$ (for $n$ a multiple of four) with vertices being adjacent if they differ in exactly $n/2$ positions has independence number at most $(2-\epsilon)^n$ for some fixed $\epsilon > 0$. Note that they describe the graph with $\pm 1$ vectors with adjacency being orthogonality, but this is equivalent. This gives an exponential lower bound for the chromatic number of this graph, and thus for the graph where adjacency is given by being different in at leat $n/2$ positions. Unfortunately this is for $k$ very far from $n$, but there may be some other useful results in that paper.

There was also a recent paper by Briet and Zuiddam (http://arxiv.org/pdf/1608.06113v1.pdf) that proves that the orthogonal rank (smallest dimension in which vectors can be assigned such that adjacent vertices are orthogonal) of the graph on $\mathbb{F}_2^n$ with adjacency corresponding to differing in at least $n/2$ positions is exponential in $n$. The orthogonal rank lower bounds the chromatic number and their techniques could possibly be adapted for $k$ closer to $n$.

It might also be worth noting that for $k + 1 = n-1$, the chromatic number is known to be 4.

Edit: I just looked a little more closely at the paper of Briet and Zuiddam mentioned above, and they say the best lower bound on the orthogonal rank of your $\overline{H}_n^k$ is $$2^{[1-h((k+1)/n)]n - o(n)},$$ where $h(p) = -p\log_2(p) - (1-p)\log_2(1-p)$ is the entropy of the probability distribution $(p,1-p)$. This gives an exponential lower bound on chromatic number for a fixed value of $(k+1)/n$. I think that they say that this lower bound is actually given by an unpublished paper of Samorodnitsky (http://www.cs.huji.ac.il/~salex/papers/old_sq_measure.ps).


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

  • $\begingroup$ 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$. $\endgroup$
    – Seva
    Commented Jul 7, 2012 at 14:24
  • $\begingroup$ 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$. $\endgroup$ Commented Jul 7, 2012 at 14:54
  • $\begingroup$ I rewrote my answer so that it makes sense (hopefully). $\endgroup$ Commented Jul 7, 2012 at 15:39
  • $\begingroup$ 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. $\endgroup$
    – Seva
    Commented Jul 7, 2012 at 15:45
  • $\begingroup$ 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. $\endgroup$ Commented Jul 7, 2012 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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