With crossings, some graph equivalent to the 5-cube (32 vertices) certainly works. Take an n-regular unit graph, and displace it by one unit in some direction that doesn't cause a point collision, and then connect each point to its displaced partner: this produces an (n+1)-regular unit graph. A single point, which is a 0-regular unit graph, gets the recursion started. Of course there could be examples with fewer vertices. On Tue, May 10, 2016 at 8:36 PM, Warren D Smith <warren.wds@gmail.com> wrote:
--this theorem implicitly demands the graph be planar, i.e. 5-regular unit distance graphs with edge crossings were not ruled out.
Apparently you are correct. http://www2.math.technion.ac.il/~room/ps_files/matchstick.pdf has Theorem 1. Finite 5-regular matchstick graphs do not exist.
From: Veit Elser <ve10@cornell.edu> https://en.wikipedia.org/wiki/Matchstick_graph "Harborth graph"
--in order for a K-regular matchstick graph to exist with N vertices, we need 2N coordinates to satisfy K*N/2 equations.
And actually the first two vertices can wlog be located at (0,0) and (1,0) in which case 2N-4 coordinates must satisfy K*N/2-1 equations.
The #equations is arbitrarily greater than the #unknowns if K>=5 when N=large, therefore perhaps K>=5 is impossible? If K=4 it also is greater, but only by 3, so a few miracles like Harborth's could be hoped for.
On 5/10/16, math-fun-request@mailman.xmission.com <math-fun-request@mailman.xmission.com> wrote:
Send math-fun mailing list submissions to math-fun@mailman.xmission.com
To subscribe or unsubscribe via the World Wide Web, visit https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun or, via email, send a message with subject or body 'help' to math-fun-request@mailman.xmission.com
You can reach the person managing the list at math-fun-owner@mailman.xmission.com
When replying, please edit your Subject line so it is more specific than "Re: Contents of math-fun digest..."
Today's Topics:
1. Re: Something special about 104 (Allan Wechsler) 2. Re: Something special about 104 (Paul Palmer) 3. Re: Something special about 104 (Paul Palmer) 4. regular matchstick graph (Warren D Smith) 5. Re: regular matchstick graph (Paul Palmer)
----------------------------------------------------------------------
Message: 1 Date: Tue, 10 May 2016 18:34:11 -0400 From: Allan Wechsler <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Something special about 104 Message-ID: < CADy-sGHWvNyfFV7juWfZiKSjH-v0Gah1KO18pUagoWoHiw8rPA@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
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
------------------------------
Message: 2 Date: Tue, 10 May 2016 17:36:27 -0500 From: Paul Palmer <paul.allan.palmer@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Something special about 104 Message-ID: <CAM6ucknBkzQJ8oVWei=Hd8_E_01Y=1_7Vta-hsC6gV= tn4JwBA@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
Ack. I knew I'd seen this, but wasn't using the right term. Thank you.
On Tue, May 10, 2016 at 5:26 PM, Veit Elser <ve10@cornell.edu> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Message: 3 Date: Tue, 10 May 2016 17:48:28 -0500 From: Paul Palmer <paul.allan.palmer@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Something special about 104 Message-ID: <CAM6uckkZoQofJiHXy99O21u30Ufu1_sQ2-nR4B7r8VYodAq= TQ@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
I thought about the 4-cube, but read "exist in the plane" as meaning it must be a planar graph.
On Tue, May 10, 2016 at 5:34 PM, Allan Wechsler <acwacw@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Message: 4 Date: Tue, 10 May 2016 19:53:47 -0400 From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Subject: [math-fun] regular matchstick graph Message-ID: <CAAJP7Y18qRLRhugd4gskrS4bdY=hWY7-X=kAqr= Vhy03wNZoKQ@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
From: Veit Elser <ve10@cornell.edu> https://en.wikipedia.org/wiki/Matchstick_graph "Harborth graph"
--in order for a K-regular matchstick graph to exist with N vertices, we need 2N coordinates to satisfy K*N/2 equations.
And actually the first two vertices can wlog be located at (0,0) and (1,0) in which case 2N-4 coordinates must satisfy K*N/2-1 equations.
The #equations is arbitrarily greater than the #unknowns if K>=5 when N=large, therefore perhaps K>=5 is impossible? If K=4 it also is greater, but only by 3, so a few miracles like Harborth's could be hoped for.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
------------------------------
Message: 5 Date: Tue, 10 May 2016 19:07:46 -0500 From: Paul Palmer <paul.allan.palmer@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] regular matchstick graph Message-ID: <CAM6uckmOxXNfLD_ypZDh=FAu4wxUPiX= WihGQJKJ+KHiDjztZg@mail.gmail.com> Content-Type: text/plain; charset=UTF-8
Apparently you are correct.
http://www2.math.technion.ac.il/~room/ps_files/matchstick.pdf has Theorem 1. Finite 5-regular matchstick graphs do not exist.
I thought it was funny that the wikipedia article had a link to a paper https://arxiv.org/abs/math/0609360 whose abstract says "The Harborth graph is the smallest known example of a 4-regular planar unit-distance graph."
where "4-regular planar unit-distance graph" is exactly the search term I was using.
On Tue, May 10, 2016 at 6:53 PM, Warren D Smith <warren.wds@gmail.com> wrote:
From: Veit Elser <ve10@cornell.edu> https://en.wikipedia.org/wiki/Matchstick_graph "Harborth graph"
--in order for a K-regular matchstick graph to exist with N vertices, we need 2N coordinates to satisfy K*N/2 equations.
And actually the first two vertices can wlog be located at (0,0) and (1,0) in which case 2N-4 coordinates must satisfy K*N/2-1 equations.
The #equations is arbitrarily greater than the #unknowns if K>=5 when N=large, therefore perhaps K>=5 is impossible? If K=4 it also is greater, but only by 3, so a few miracles like Harborth's could be hoped for.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
Subject: Digest Footer
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
------------------------------
End of math-fun Digest, Vol 159, Issue 31 *****************************************
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun