The chromatic number of a Hamming-related graph

Question

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

Answer 1

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

Answer 2

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

ADDED:

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.