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

Improve this question
$\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$
    – Gordon Royle
    Commented 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$
    – Joseph Gordon
    Commented Oct 20, 2020 at 12:50
  • $\begingroup$ That's right, thanks @JosephGordon, I should have restricted the question to even $k$ $\endgroup$
    – Dominic van der Zypen
    Commented 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$
    – Joseph Gordon
    Commented Oct 20, 2020 at 19:20

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ $n$, not $n+1$? $\endgroup$
    – Joseph Gordon
    Commented Oct 20, 2020 at 13:19
  • $\begingroup$ Why would it be $n+1$? $\endgroup$
    – Antoine Labelle
    Commented 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$
    – Dominic van der Zypen
    Commented 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$
    – Antoine Labelle
    Commented 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$
    – Joseph Gordon
    Commented 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.

Improve this answer
$\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$
    – Dominic van der Zypen
    Commented Oct 20, 2020 at 12:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .