A math thought

[benlehman]

The "four color map" problem is unique to two dimensional space. Why?

I was thinking about this years ago, and I forgot it until today.

Edit: Huh. Does it apply in four dimensions or not? I thought I answered that but I didn't actually. My hunch is that for three and higher dimensions the number of mutually adjacent objects is infinite.

Let's look at this:
dimensionality -> maximum mutually adjacent objects
0 -> 1
1 -> 2
2 -> 4
3 -> infinite
4 -> ?

Second Edit: It doesn't seem to matter if the space is open (infinite in all directions) or closed (loops at the edges.) Does it?

Third Edit: So the 1d case is trivial, largely because a 1d object can only be adjacent to two other objects, which clearly limits mutual adjacency. A 2d object can be adjacent to an infinite number of other objects, a fact which I make use of in my infinite mutually adjacent 3d objects construction (see comments). Perhaps mutual adjacency in dimension n depends on adjacency of the dimension n-1? That seems tempting, especially if we're going to view dimension n as dimenion n-1 with a time axis.

Comments

[ornithoptercat.livejournal.com]

I can easily think of a situation in 3-space where you'd have four 3D shapes representing countries (or whatever) all touching one another. Or is the problem nonexistant in that there is no upper limit to the number of colors you can force it to require?

[benlehman.livejournal.com]

Yeah, you can pretty easily imagine an infinite set of mutually adjacent three dimensional objects.

The generalized four color map would be: "What is the maximum size of a set of mutually adjacent n-dimensional objects in an n-dimensional space?"

[benlehman.livejournal.com]

To elaborate on the last post, here's what such a set looks like:

Picture a stack of boxes. Stack as many as you like.

Now, nail a plank to the top box so long it stretches down to touch the bottom box (and thus, naturally, touchs all the other boxes.) Nail a plank to the next box such that it, too stretches to the bottom. Etc, etc.

Picture it with ten or so and you see how you can stack as many boxes as you like this way.

yrs--
--Ben

[clockwise.livejournal.com]

Your 0 and 1 dimensional examples counter your assertion that the "four color map" problem is unique to two dimensional space. In zero dimensions it is the "one color map" and in one dimension it is the "two color map", both of which are exceptionally boring.

If as you assert 3 dimensions is infinite, then 4 is infinite too (duh).

A space that loops around the edges requires additional colors. Consider this example which have classes 3 & 4 wrapping around the edges thus requiring a fifth color.

      A
      |
    |   |            ?
    |   +-------+
    |   |       |
    |   +---+   |
    | 4 |   |   |
  --+---+ 1 |   +------
        |   |   |   
<-    3 +---+ 5 | 3     ->
        |   |   |
  --+---+ 2 |   +------
    | 4 |   |   |
    |   +---+   |
    |   |       |
    |   +-------+   ?
    |   |
      |
      v

In an infinite plane the right hand case of 3 could reuse either color 1 or color 2 since the had already been enclosed, but by allowing wrapping a class that touches these can go take an alternate way around to their neighbor (5) without having to also enclose the fourth color.

[benlehman.livejournal.com]

But, as I said, in 0-1 dimensions, it's trivial that mutual adjacentness is limited, because the number of possible objects adjacent to an object is also limited. 2d space is unique because one object can be adjacent to any number of other objects, but mutual adjacentness is nonetheless limited.

Your five-color-map-on-a-torus is awesome. So how many mutually adjacent objects can we have on a torus? It doesn't look like the number is infinite, just higher than four, what is it (hunch: 5)? Does it matter that it wraps in both directions (hunch: yes)? Is it different for an infinite tube (hunch: the infinite tube is limited to 4)?

I got caught up that we're arranging 4d objects in 4d space, but of course since a 3d object is also a 4d object, you're right. Infinite mutual adjacentness for 3+d.

yrs--
--Ben

[clockwise.livejournal.com]

It took some thought, but you can force 5 colors within the tube.

The basic two dimensional 4 color scenario looks something like this:

          |      3
          |
          +---+
        1 | 2 +-----
          +---+
          |
          |      4

Within the unbound plane there is no region that you can add that touches all 4 of these regions without breaking one of the existing borders. Color 2 is thus free to be used elsewhere within the cube and you can not connect regions 1, 3, and 4 with a new color and not enclose one of them in doing so (thus creating a new "open" color).

However, if we are allowed to wrap then it becomes possible to connect the classes without forming enclosures.

Observe:

5 color with 1 dimension of wrapping:

          |      3
          |
---+      +---+------
 5 |    1 | 2 |  5   ->
---+      +---+------
          |
          |      4

6 color with 2 dimensions of wrapping:

   A    A
   | |  |   |
   6 |  1   |
     +------+      3
            |
  +--+---+  +---+------
<- 5 |   |  |   |  5   ->
  ---+   +--+ 2 |  +---
   6 |      |   |  | 6 ->
     |      +---+--+---
     |  1   |
     |      |      4
   |    |
   v    v

Note that 3 and 4 share a boarder someplace around the wrap.

Is that clear? It's getting complicated enough that the notation is a little odd. I'm pretty sure I didn't cheat...

I don't /think/ you can get more than 5 colors with the tube, or 6 colors on the surface of a sphere.

[clockwise.livejournal.com]

hmm, actually my 5 color 1 dim wrapping doesn't work since 3 & 4 are no longer adjacent. Oh well, it was a nice thought.

[clockwise.livejournal.com]

Can you tell that I find this problem more interesting than my work today? :P