If we look at the exclusion zone of a vertex in a euclidean unit distance graph we find that it has a clearly defined measure, and as shown in the first entry on the exclusion zone, the dimensionality of this measure is (n-1)-dimensional. For where m>1 the measure is n-dimensional.
will be a n-sphere with radius 1, and will be a n-ball with radius m.
Now let’s take a look at how color has to behave in this system. One of the first things to notice is that, from a point of intuiton, since has a clearly defined measure, using a finite amount of colors to fill these colors should have a clearly defined measure as well, but a proof remains elusive.
If we do take a color and concentrate it in a continuous segment of we get a measurable line. We can disperse a color finer but there are problems with doing that:
Same colored points can have their exclusion zone overlap in 2 points only if they are close enough. Note that any point between v1 and v2 will have its exclusion zone overlap with . As we concentrate more points denser their exclusion zones overlap more. This is also what we found with areas bounded by Jordan curves, any point inside of such a single colored boundary will have it’s exclusion zone be only a subset of the exclusion already generated by the boundary.
An efficient tessellation of space has both the exclusion zones of
Conversely if we take some infinite amount of colors and disperse them finer across their combined exclusion zone within becomes bigger.
I would like to say that I have some more concrete math of what’s happening, but I don’t and I don’t have any solid ideas for how to get there either as of now.
Just as a graph defined on a space can be contracted using the exclusion zone, it is possible to take a locally finite unit distance graph and expand the nodes to cover some space.
In order to analyze this subspace properly we will ignore the rest of the space, or consider it 0 colored.
If we embed the graph in and expand the nodes into n-balls, so that the exclusion zones of the resulting areas do not touch other areas associated with nodes that were previously unconnected, it is clear that the chromatic color stays unchanged.
Let’s take a look at this process and it’s results with the simplest possible case, a graph consisting of only 2 vertices and 1 edge.
As we can see this expanded graph is still 2-colorable. But this instance has a much more important property related to exclusion zones and dimensionality. Assume for a moment it is possible to color this area using less than 2-dimensional areas, or non-measurable sets.
We start by placing a single vertex with color 1, and already we run into a problem.
We know there is a valid 2-coloring of this subspace, so all points excluded by v need to have color 2. however is a 1-dimensional line in the second area. is a 2-dimensional area inside of our first area which needs to have color 1. Repeating these steps we clearly get right back to our initial coloring, even though we will never reach the far points.
This process also generalizes well to higher dimensions and unit distance graphs with more nodes. As long as the original graph is sufficiently restrictive the resulting subspace will still have areas that have to be single colored.
It would seem as if the most efficient coloring depends on areas, likely manifolds, which are homeomorphic to their containing space.
Using the exclusion zone one can contract a tessellation into a graph with a locally finite number of nodes, and the same chromatic number as the tessellation. I’ve been unable to find anything like this thoroughly explained in papers on graph coloring or general math sites yet, though I would reckon someone probably has done this already. For now I’ll simply call this a contracted graph as would be the case for generally finite examples.
Every continuous color area is a node in the contracted graph, and all areas that touch each other with their exclusion zones have their respective nodes connected with edges.
If we take the well known hexagonal tilling of the plane scaled to its maximum diameter and apply this process we find a 18-regular graph. For a single area/node the result looks like this:
In this instance we can see that any node will form a complete subgraph with the 6 nodes in the inner ring around it, but there certainly isn’t always such a complete subgraph. So far I’ve observed that certain colorings only have critical subgraphs with the according chromatic number, but no complete subgraph. These colorings have areas in the inner ring around a central area that do not touch each other with their exclusion zones, such as a 8-chromatic square tiling of the plane, or a 7-chromatic pentagonal tiling I’ve first seen mentioned by Aubrey de Grey, though I’m not sure if this generally holds true.
When looking into unit distance graphs (and also many other graphs) defined on a space then we typically find this fundamental premise described only in a few sentences. I felt that some generalizations on these definitions could be useful, so I came up with the exclusion zone, and applied it to the Hadwiger-Nelson problem. First we generalize for any dimensionality, and then add the ability to look at not just single vertices and what they are connected to, but whole sets.
Let be the unit distance graph of a euclidean space with dimensionality n, then our exclusion zone is:
The shape of an exclusion zone for a single vertex is always a hypersphere, and other continuous inputs maintain a somewhat similar shape.
Let’s consider 4 different monochromatic sets (denoted by v) and their respective exclusion zones, a point, a line, a 2-ball and a 2-sphere.
So far what we find in the plane is that if v is 0-dimensional, is 1-dimensional, otherwise it is 2-dimensional.
In the general case we find that for any 0-dimensional input the zone will be (n-1)-dimensional and any input with a dimensionality higher than 0 will yield an n-dimensional zone.
We also find that only the boundary of the input set matters, for example once we admit a Jordan curve with color 1, we must also color its interior the same way, otherwise we will clearly lose efficiency while gaining nothing.
The exclusion zone can also be used to determine if the containing graph space of a vertex is equal to the containing topological space.
If the graph space isn’t the same as the containing topological space we’re dealing with multiple disconnected subgraphs, such as , where for instance there is no path between 0.5 and 1, and these two vertices have no color effect on each other whatsoever.
To keep it simple, in this blog I’ll share my ideas and experiences with math, mostly regarding the Hadwiger-Nelson problem in particular. Comments and any sort of critique are welcome.