Welcome to MathOverflow

Question

4

The 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.

flag	asked Jan 3 2011 at 14:31 Christoph-Simon Senjak 302●2●7

Could you kindly remind us what are the known bounds on the chromatic number? – Joel David Hamkins Jan 3 2011 at 14:38

2

@Joel: en.wikipedia.org/wiki/… – Qiaochu Yuan Jan 3 2011 at 14:41

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 2011 at 15:51

Anthony Quas · Accepted Answer · 2011-01-03 19:58:19Z UTC

10

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.

answered Jan 3 2011 at 19:58

Anthony Quas
6,260●1●12●28

	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 Jan 3 2011 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 2011 at 21:37

Is the chromatic number of the real plane invariant under the norm?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.