4
$\begingroup$

Recall that chromatic number of $\mathbb{R}^2$ is the least $n$ such that there exists a function $f$ from $\mathbb{R}^2$ into a set of colors ${C_1,\ldots,C_n}$ with $f(x)\neq f(y)$ for $||x-y||_2=1$.

As far as I know, the problem which number this exactly is is still open. I was wondering whether this number is invariant under the norm $||\cdot||$ that is chosen.

Improve this question
$\endgroup$
3
  • $\begingroup$ Could you kindly remind us what are the known bounds on the chromatic number? $\endgroup$
    – Joel David Hamkins
    Commented Jan 3, 2011 at 14:38
  • 2
    $\begingroup$ @Joel: en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem $\endgroup$
    – Qiaochu Yuan
    Commented Jan 3, 2011 at 14:41
  • 3
    $\begingroup$ In any case, I don't see any good reason for this to be true. The corresponding graphs are certainly not isomorphic: the clique number of the graph with the Euclidean norm is 3 but the clique number of the graph with the sup norm is at least 4. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 3, 2011 at 15:51

1 Answer 1

Reset to default
11
$\begingroup$

For the $L^\infty$ norm (or equivalently the $L^1$ norm rotating by 45 degrees) the chromatic number is easy to calculate: 4. Just colour translates of $[0,1)\times[0,1)$ by $\mathbb Z^2$ in a $2\times 2$ repeating pattern. It must be at least 4 because ${0,1}\times{0,1}$ are all distance 1 apart.

There's certainly no simple periodic colouring with 4 colours that will work for the $L^2$ norm.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a good response, but it should be remarked that as far as we know the chromatic number in the $L^2$ norm could be $4$. I think it is also a worthwhile question if on more general spaces are there any monotonicity/convexity properties of the chromatic number in the $L^p$ norm (as $p$ varies). $\endgroup$
    – GH from MO
    Commented Jan 3, 2011 at 21:06
  • $\begingroup$ Yes, its not quite an answer because it could still be equal. But since a proof of the equality would prove that the chromatic number of $\mathbb{R}$ equals 4, I assume that nothing of that kind can be said yet. Thus, I accept it as an answer, thank you. $\endgroup$
    – Christoph-Simon Senjak
    Commented Jan 4, 2011 at 21:37
  • $\begingroup$ By the recent work of Aubry de Grey, it now is known that the chromatic number of the $L^2$ graph on $\R^2$ is at least 5. $\endgroup$
    – Anthony Quas
    Commented Apr 20, 2018 at 19:29

You must log in to answer this question.

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