18
$\begingroup$

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus, for instance, $G_2=K_4$, and $G_3$ has $25$ edges. What is the chromatic number of $G_n$?

There is a simple, but not quite obvious construction showing that $\chi(G_n)\le n(n+1)/2+1$, and I am interested in a matching lower bound. Computations give $$ \chi(G_1)=2,\ \chi(G_2)=4,\ \chi(G_3)=5,\ \chi(G_4)=9, $$ $$ \chi(G_5)=12,\ \chi(G_6)=16,\ \text{and}\ \chi(G_7)\le 17. $$ (The first five values are easy to compute, the last two are reported by Gordon Royle in the comments.)


An update. The colorings I am interesting in are of a special nature: if the strings $s$ and $t$ are same-colored, then (identifying strings with sets) also $s\setminus t$ and $t\setminus s$ are same-colored. Let $\chi^*(G)$ denote the smallest number of colors needed to properly color the graph $G$ in this special way. Is it true that $\chi^*(G_n)=(1/2+o(1))n^2$? That, say, $\chi^*(G_n)>(1/4+o(1))n^2$?

$\endgroup$
15
  • 3
    $\begingroup$ @JoshuaZ: sure; color each vertex with the scalar product of the corresponding string and the vector $(1,2,\dotsc,n)$. $\endgroup$
    – Seva
    Nov 20 at 16:36
  • 3
    $\begingroup$ what do you mean by lying below? $\endgroup$ Nov 21 at 8:48
  • 2
    $\begingroup$ @FedorPetrov: one of the corresponding subsets of the $n$-element set being contained in another one. $\endgroup$
    – Seva
    Nov 21 at 9:03
  • 6
    $\begingroup$ Here is a nice $17$-colouring of $G_7$ where I am using subsets of $\{0,1,\ldots,6\}$ to represent the vertices. Let $\sigma = (0,1,2,3,4,5,6)$ be a cyclic permutation and let $\tau$ be the complement map on the subsets. Let $F= \{013, 124, 235, 346, 450, 561, 602\}$ be the Fano plane and set $C = F \cup F^\tau$. Then take $D = \{0, 16, 25, 34, 124, 135, 236, 456\}$ and its seven rotations under powers of $\sigma$, and $D^\tau$ and its seven rotations under powers of $\sigma$. Then one colour class for each of $\emptyset$ and the entire set, making a total of 17 classes. $\endgroup$ Nov 22 at 7:04
  • 2
    $\begingroup$ So $G_6$ has chromatic number $16$ - this took quite a long time to compute, almost all of which was spent searching in vain for a $15$-colouring. I think it will be hard to get close to an exact answer. $\endgroup$ Nov 23 at 2:29
7
$\begingroup$

This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$.

Observation 1. $\chi(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$.

This is because $G_n$ contains a clique of that size, namely,
$\varnothing,\{1\},\{2\},\{1,2\},\{1,2,3\},\{1,2,4\},\{1,2,3,4,\},\{1,2,3,4,5\},\dots$.

Observation 2. The OP noted that $\chi(G_n)\le\binom{n+1}2+1=\frac{n^2+n+2}2$. For odd $n$ this bound can be improved to $\chi(G_n)\le\frac{n^2+3}2$.

The vertices $\varnothing$ and $[n]$ get their own colors. If $1\le|X|\le n-1$, color $X$ with the ordered pair $$\left(\sum_{x\in X}x\mod(n+1),\ \left\lceil\frac{|X|}2\right\rceil\right).$$ This is a proper coloring, so (assuming $n$ is odd) $$\chi(G_n)\le2+(n+1)\cdot\frac{n-1}2=\frac{n^2+3}2.$$

Observation 3. The clique number $\omega(G_n)$ is exactly $\left\lfloor\frac{3n}2\right\rfloor+1$.

We showed in Observation 1 that $\omega(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$. Let us prove by induction that $\omega(G_n)\le\left\lfloor\frac{3n}2\right\rfloor+1$.

We may assume $n\ge2$. Let $\mathcal C$ be a maximal clique in $G_n$. Let $\mathcal C_h=\{X\in\mathcal C:|X|=h\}$. Choose $h$ so that $0\lt h\lt n$ and $\mathcal C_h\ne\varnothing$.

If $\bigcup\mathcal C_h=[n]$ and $\bigcap\mathcal C_h=\varnothing$, then $|\mathcal C|=|\mathcal C_h|+2\le n+2\le\left\lfloor\frac{3n}2\right\rfloor+1$. Otherwise, choose $X\in\{\bigcup\mathcal C_h,\ \bigcap\mathcal C_h\}$ so that $0\lt|X|\lt n$, and let $k=|X|$. Then every element of $\mathcal C$ is a subset or superset of $X$. Since $0\lt k\lt n$, by induction we have $$|\mathcal C|\le\omega(G_k)+\omega(G_{n-k})-1\le\left\lfloor\frac{3k}2\right\rfloor+\left\lfloor\frac{3(n-k)}2\right\rfloor+1\le\left\lfloor\frac{3n}2\right\rfloor+1.$$

$\endgroup$
2
  • 1
    $\begingroup$ Some more computational snippets: the cliques you found are the unique maximum clique (up to equivalence under the automorphism group) for $G_4$, $G_6$ and $G_8$. For $G_5$, $G_7$ and $G_9$ there are other classes of equally-large cliques, but none larger. $\endgroup$ Nov 25 at 2:56
  • $\begingroup$ So I liked your original proof that if $|\mathcal{C}_h| = 1$ for some $h$, then the result follows. Did you decide that it was not so obvious to prove that there must be a layer containing just one vertex of the clique? $\endgroup$ Nov 26 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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