This is very interesting! Even more interesting that 104 has not yet been proved lowest. A closely related problem is to find the "chromatic number of the plane". The unit-distance graph of the plane is defined as having as vertices all the points of the plane, and for edges every pair of vertices that are 1 unit apart. It's the chromatic number X(R^2) of this graph that is the question. It's known that 4 <= X(R^2) <= 7 . The same question can be asked about any Euclidean space, and as far as I know the latest bounds for X(R^3) are 6 <= X(R^3) <= 15 . The upper bounds 7 and 15 are obtained by carefully* tiling R^2 with translated rosettes of hexagons (resp. translated clusters of truncated octahedra), thereby 7-coloring (resp. 15-coloring) all vertices of R^2 (resp. R^3) so that no two vertices at unit distance are the same color. The lower bound for X(R^2) comes from a finite graph that requires 4 colors. I don't know but suspect the lower bound of 6 for X(R^3) is obtained likewise. —Dan —————————————————————————— * "Carefully" applies to how the boundaries are assigned so that no two boundary points are the same color.
On May 10, 2016, at 2:29 PM, Paul Palmer <paul.allan.palmer@gmail.com> wrote:
(Delurking for my first post.)
A while back I saw a fact posted (on Pat's Blog, if anyone reads it) that said:
104 is the lowest known number of unit line segments that can exist in the plane, 4 touching at every vertex.
I can find this repeated all over the internet, but nothing more about it.
I read it as saying that the smallest 4-valent (quartic) unit distance graph has 104 vertices.
Does that sound correct? Does anyone know where this might have come from?
Thanks. I have enjoyed following the discussions on this list.