Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Could you kindly remind us what are the known bounds on the chromatic number? –  Joel David Hamkins Jan 3 '11 at 14:38
2  
3  
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. –  Qiaochu Yuan Jan 3 '11 at 15:51

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
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). –  GH from MO Jan 3 '11 at 21:06
    
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. –  Christoph-Simon Senjak Jan 4 '11 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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