https://en.wikipedia.org/wiki/Matchstick_graph "Harborth graph"

On May 10, 2016, at 5: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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

See the article "Matchstick graph" on Wikipedia. The 104-vertex example is due to Heiko Harborth. There is a picture of it in the article. Note that its minimality has not been proven. You left out the requirement that the line segments not cross; without this constraint, there is an orthographic projection of the edges of a 4-cube that works with 16 vertices. I have an idea that computer search might settle the minimality question. On Tue, May 10, 2016 at 5: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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

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.