4
$\begingroup$

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$?

$\endgroup$
4
  • 1
    $\begingroup$ Not 3. This is the famous result of Payan that cubelike graphs never have chromatic number 3 (or clique number). Your graphs, called “distance graphs” by Payan are special cases of cubelike graphs. Start here core.ac.uk/download/pdf/82733314.pdf for more including a reference to a paper by Dvorak et al. $\endgroup$ Oct 20, 2020 at 11:14
  • 1
    $\begingroup$ Note that for odd $k$ the graph is bipartite (color by parity of the number of $1$'s). For even $k$ quantity $\omega(G_{n,k})-1$ corresponds to the maximal number of $k$-subsets of $[n]$ with pairwise intersections of size $k/2$ (clique containing $(0,0,...)$ looks in such a way). $\endgroup$ Oct 20, 2020 at 12:50
  • $\begingroup$ That's right, thanks @JosephGordon, I should have restricted the question to even $k$ $\endgroup$ Oct 20, 2020 at 12:52
  • $\begingroup$ The upper bound, I think, is given by Fisher's inequality (which is stated in a various number of ways, see e.g. this for relevant statement) $\endgroup$ Oct 20, 2020 at 19:20

2 Answers 2

5
$\begingroup$

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. I think that the chromatic number is also unknown in this special case.

$\endgroup$
8
  • $\begingroup$ $n$, not $n+1$? $\endgroup$ Oct 20, 2020 at 13:19
  • $\begingroup$ Why would it be $n+1$? $\endgroup$ Oct 20, 2020 at 13:27
  • $\begingroup$ Thanks Antoine for making the connection to the Hadamard matrix conjecture! - It would also be nice to know whether at least the clique number and the chromatic number agree, but this may be open as well $\endgroup$ Oct 20, 2020 at 14:24
  • $\begingroup$ @DominicvanderZypen I found some additionnal information for the chromatic number in this special case. It is known that the chromatic number is $\ge n$ with equality if and only if $n$ is a power of $2$: arxiv.org/pdf/math/0509151.pdf $\endgroup$ Oct 20, 2020 at 18:19
  • $\begingroup$ @AntoineLabelle well, I expect the equivalence to Hadamard conjecture you mean is the one I described in this comment. Then we need to add $1$ to account for all-zeros vector, don't we? $\endgroup$ Oct 20, 2020 at 19:03
2
$\begingroup$

Not quite what you're looking for, but appears to be the closest thing in the literature: the clique number for the related case $d_H \le k$ is addressed in Sharifiyazdi's dissertation The Clique Number of Generalized Hamming Graphs; references therein also discuss the chromatic number.

$\endgroup$
1
  • $\begingroup$ I will wait before accepting the answer for a moment in case somebody finds an exact answer to my question - but your post is already very helpful, thanks a lot! It definitely deserves an upvote $\endgroup$ Oct 20, 2020 at 12:54

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.