One of the more curious things I’ve discovered in HAKMEM:
Although not new (cf Coxeter, Introduction to Geometry, 1st ed. p393), the following coloring number (chromatic number) may be useful to have around:
N = [[(7 + sqrt(48 H + 1))/2]]
where N is the number of colors required to color any map on an object which has H holes (note: proof not valid for H = 0)
(Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972)
[Note: “color” here means “colour so that no two regions that share a length of border have the same colour”. “Map” means map in the intuitive sense; a partition into sensible sorts of bits of the surface. Think countries on a map of the world. The outermost square brackets mean the floor function (the greatest integer less than the function’s argument).]
Isn’t that cool? HAKMEM is obviously not all that mathemathically sophisticated; it doesn’t tell you what kind of object. I guess in this case it’s just bounded and connected and stuff, in R^3. There’s probably also some nuance to do with the concept of “hole”. But to think that this can be found in a book called Introduction to Geometry! Further evidence that all math books have “introduction”, “elementary”, “approach” or something similar in the title just to make everyone feel small.
If you’re having difficulties picturing this, think about a torus. The hole is one extra way for each region to “come around” to meet each other (in contrast to regions in the plane), but one is “stuck in the middle” so the chromatic number is 7.
Another way of thinking about the torus: start by drawing a band of colour around the entire outer rim of the torus. The rest is now split into two “colourable planes” that can conflict through the hole, so you need 4 + 4 – 1 colours (the outer rim gets counted twice, once for each plane, so we subtract it once).
If this kind of thing is totally new to you, get some paper and try to find out how many colours you need (at most) for a map in two dimensions, ie. a plane.
Question: how would this work in R^n?
