eklhad@ihnet.UUCP (K. A. Dahlke) (08/20/84)
Thanks for the many responses to the 3-D map coloring problem. Everyone responded correctly, I guess it was easy. Some people were more formal than others, ranging from "globs can grow tenticles that reach around touching all other globs" to "the general point-line graph is isomorphic to 3-dimensional regional maps" Above quotes are not exact. Here is my solution. There is no limit to the number of colors that might be required by a 3-dimensional map. I mentioned n dimensions just to confuse you. I shall construct a map which requires an infinite number of colors. Note: i mean countably infinite, since n-dimensional space cannot be partitioned into an uncountably infinite number of disjoint non-zero volume regions. Each glob consists of two connected rectangular solids. These rectangular bars are one square unit in cross-section, and infinitely long. Thinking in an x-y-z coordinant system, piece J (J=-inf,+inf) is: 0<=z<=1,J-1<=x<=J,-inf<y<+inf union 1<=z<=2,J-1<=y<=J,-inf<x<+inf The thing resembles an infinite crossbar switch. The Jth glob is the Jth horizontal bar welded to the Jth vertical bar. Each glob touches all others, and infinite colors are required. Let me pose a philosophical question, and then a more interesting mathematical question. What is so special about 3 dimensions. Can anyone put into words why region flexibility jumps from 4 to +infinity. Does this imply that life (with the interconnections of neurons, arteries, capillaries, alvioli, etc) would be improbable in 2 dimensions? Back to the real world, my next question: What if we force all globs to be convex? How many colors for convex globs in n dimensions. This has no affect on 2 dimensions, since i can put 3 trapazoids around a triangle, making a map requiring 4 colors. This concept can be extended by placing 4 trapazoidal solids around a tetrahedren, etc. Thus colors(n) >= n+2. Certainly for 3 dimensions we can go much higher than 5 colors. I believe i have created a 12 color map. Can anyone beat this, or prove 12 is maximum. I will be on vacation for a while, but send responses, I will get to them. enjoy!! -- Karl Dahlke ihnp4!ihnet!eklhad