Let $n$ be a positive integer and consider $\{0,1\}^n$. We define the *Hamming distance* $d\_H(x,y)$ of members $x,y\in\{0,1\}^n$ by $$d\_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$


For integers $n>1$ and $k$ with $1<k<n$ let $G\_{n,k}$ be the graph defined on the vertex set $\{0,1\}^n$ such that two vertices $x,y$ are connected by an edge if and only if $d\_H(x,y) =k$.


**Question.** What is the value of the clique number $\omega(G\_{n,k})$ and of the chromatic number $\chi(G\_{n,k})$ in terms of $n,k$?



Graphs on $\{0,1\}^n$ based on fixed Hamming distance
In general, this is an open problem. In the special case where $n$ is divisible by $4$ and $k=n/2$, the clique number is believed to be $n$ but this is equivalent to the [Hadamard matrix conjecture](https://en.wikipedia.org/wiki/Hadamard_matrix#Hadamard_conjecture). I think that the chromatic number is also unknown in this special case.


