Chromatic number of the plane roundup

I’ve had fun writing about the Hadwiger-Nelson problem to determine the chromatic number of the plane, but I think this will be my last post on the topic for now!

More 7-colorings

Of course, the original point of the hexagonal 7-coloring in my last two posts is that it establishes an upper bound of CNP \leq 7 (although it turns out it’s also just a really cool pattern). Again, there is a balancing act here: we have to give each hexagon a diameter of < 1, so no two points in the same hexagon will be 1 unit apart; but we also have to make the hexagons big enough that same-colored hexagons are more than 1 unit from each other. This is indeed possible, since same-colored hexagons always have two “layers” of other hexagons in between them. Denis Moskowitz made a really nice graphic illustrating this:

In a comment on my previous post, Will Orrick pointed out that if you tile 3-dimensional space with cubes and color them with seven colors so that each cube is touching six others with all different colors, then take a diagonal slice through that space, you get this!

This is the same as the 7-colored hexagonal tiling I showed before, but with extra triangles in between the hexagons (and the colors of the triangles follow a pattern similar to the hexagons). I could stare at this all day! Here’s a version with numbers if you find it helpful. (If you support me on Patreon you can get automatic access to bigger versions of all the images I post—though to be honest if there’s a particular image you want a bigger version of, you can just ask nicely!)

What is CNP?

So, we know CNP is either 5, 6, or 7. So which is it? No one is really sure. With some unsolved problems, there is widespread agreement in the mathematical community on what the right answer “should be”, it’s just that no one has managed to prove it. That isn’t the case here at all. If you ask different mathematicians you will probably get different opinions on which number is correct. Some mathematicians even think the “right” answer might depend on which axioms we choose as a foundation of mathematics!—in particular that the answer might change depending on whether you allow the axiom of choice (a topic for another post, perhaps).

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in geometry and tagged , , , , , , , , . Bookmark the permalink.

7 Responses to Chromatic number of the plane roundup

  1. Denis says:

    Oh, I’m glad you liked the graphic enough to use it as-is. It occurred to me afterwards that using your coloring for the hexes and changing the hue of the highlighted hexes to red or green would be clearer than using the rainbow coloring and changing the saturation, but oh well.

    It’s difficult to imagine what a valid chromatic coloring of the plane might look like if CNP is 5 or 6, since it couldn’t be symmetrical in the same way as this pattern. Maybe something semiperiodic based on Penrose Tiles? Perhaps someday someone will discover it and it will take over the world like the Mandelbrot Set did. 🙂 (Admittedly it might be unvisualizeable like the Banach-Tarski division.)

    • Brent says:

      Yeah, a semiperiodic 6-coloring of the plane would be super cool, although there has been so much work on semiperiodic tilings that I guess I find it implausible that no one has found one if it exists. Personally I am going to go out on a limb and conjecture that CNP = 7, unless you allow the axiom of choice, in which case CNP = 6, as witnessed by some infinitely detailed Banach-Tarski monstrosity that you cannot hope to visualize.

  2. Denis says:

    The WP article about this has an oversight that I’m sure I can’t be the first to notice, but you would know better than I.

    Discussing higher dimensions, it says: “For n>1, a lower bound of n+2 is available using a generalization of the Moser spindle: a pair of the objects (each 2 simplexes glued together on a facet) which are joined on 1 side by a point and the other side by a line.”

    The line at the other end of the spindle can instead be a simplex of n-1, which gives a lower bound of 2n.

    • Brent says:

      I don’t think I understand. How would you connect two points with an n-1 simplex?

      • Denis says:

        The full rephrase would be “For n>1, a lower bound of 2n is available using a generalization of the Moser spindle: n of the objects (each 2 simplexes glued together on a facet) which are joined on 1 side by a point and the other side by an n-1 simplex.”

        • Denis says:

          Oh, never mind – there’s nothing forcing you to use the same set of N colors for the glued facet, so the argument doesn’t work.

          • Brent says:

            Oh, I see now. I almost believed you. =) But I agree, this ends up only being a more complicated proof that n+2 is a lower bound. Your construction is not n+1 colorable but it is always n+2 colorable.

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.