May 2016 - mathfun@mailman.xmission.com

[math-fun] regular matchstick graphs
by Warren D Smith 10 May '16

10 May '16

--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(a)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(a)mailman.xmission.com <math-fun-request(a)mailman.xmission.com> wrote: > Send math-fun mailing list submissions to > math-fun(a)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(a)mailman.xmission.com > > You can reach the person managing the list at > math-fun-owner(a)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(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Something special about 104 > Message-ID: > <CADy-sGHWvNyfFV7juWfZiKSjH-v0Gah1KO18pUagoWoHiw8rPA(a)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(a)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(a)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(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Something special about 104 > Message-ID: > <CAM6ucknBkzQJ8oVWei=Hd8_E_01Y=1_7Vta-hsC6gV=tn4JwBA(a)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(a)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(a)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(a)mailman.xmission.com >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)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(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Something special about 104 > Message-ID: > <CAM6uckkZoQofJiHXy99O21u30Ufu1_sQ2-nR4B7r8VYodAq=TQ(a)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(a)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(a)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(a)mailman.xmission.com >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >> _______________________________________________ >> math-fun mailing list >> math-fun(a)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(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] regular matchstick graph > Message-ID: > <CAAJP7Y18qRLRhugd4gskrS4bdY=hWY7-X=kAqr=Vhy03wNZoKQ(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > >>From: Veit Elser <ve10(a)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(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] regular matchstick graph > Message-ID: > <CAM6uckmOxXNfLD_ypZDh=FAu4wxUPiX=WihGQJKJ+KHiDjztZg(a)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(a)gmail.com> > wrote: > >> >From: Veit Elser <ve10(a)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(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > math-fun mailing list > math-fun(a)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)

2 1

[math-fun] regular matchstick graph
by Warren D Smith 10 May '16

10 May '16

>From: Veit Elser <ve10(a)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)

2 1

[math-fun] No 3 in line (classic problem by H.Dudeney in early 1900s)
by Warren D Smith 10 May '16

10 May '16

Good programming-contest problem: Let F(N) be the max possible number of points you can pick from an NxN grid, such that no 3 lie on a line. Find the best lower bounds you can for F(1), F(2), ..., F(256). I have a program which appears to be capable of showing F(N)>1.57*N for an infinite set of N, although the 1.57 is just a guess based on looking at its results for various N, and might be deluded. (The fact that 1.57 approximates pi/2 is probably just a coincidence?) My program provably exceeds 1.4999*N for an infinite set of N. A trivial upper bound is F(N)<=2*N, because if you pick 2*N+1 points, then 3 must lie on some horizontal gridline. This trivial upper bound has actually been attained for N=52 and also most N below 52. That was done by Achim Flammenkamp. Perhaps 2N is also attainable for some N>52, perhaps even an infinite set of N. That is unknown. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 3

[math-fun] No 3 in line (classic problem by H.Dudeney in early 1900s)
by Warren D Smith 10 May '16

10 May '16

> Good programming-contest problem: > Let F(N) be the max possible number of points you can pick > from an NxN grid, such that no 3 lie on a line. > Find the best lower bounds you can for F(1), F(2), ..., F(256). > > I have a program which appears to be > capable of showing F(N)>1.57*N > for an infinite set of N, although the 1.57 is > just a guess based on looking at its results for various N, > and might be deluded. > (The fact that 1.57 approximates pi/2 is probably just a coincidence?) > My program provably exceeds 1.4999*N for an infinite set of N. > > A trivial upper bound is F(N)<=2*N, because > if you pick 2*N+1 points, then 3 must lie on some horizontal > gridline. This trivial upper bound has actually been attained > for N=52 and also most N below 52. > That was done by Achim Flammenkamp. Perhaps 2N is > also attainable for some N>52, perhaps even an > infinite set of N. That is unknown. > > -- > Warren D. Smith > http://RangeVoting.org <-- add your endorsement (by clicking > "endorse" as 1st step) > From: Zak Seidov <zakseidov(a)mail.ru> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] No 3 in line (classic problem by H.Dudeney in > early 1900s) > There are many related sequences in OEIS: > https://oeis.org/ ? > > try > author:Hardin? (33890 results) > or better > no three in line ? (123 results) --My function F(n) does not appear to be in OEIS. I agree there are some related sequences such as https://oeis.org/A000769 (which appears to grow exponentially) and https://oeis.org/A000938 which incidentally appears to grow like 0.2075 * N^4 * (log2(N)-1.125) accurate to within about 1 percent. Assuming the latter N^4*log(N) behavior is roughly correct, then the following random construction: 1. pick Q points randomly from the NxN grid. 2. the number of collinear triples among them is in expectation about 0.2075 * ( log2(N)-1.125 ) * Q^3 / N^2 3. remove 1 point from each such triple to get a no-3-in-line set. will produce about const*N/sqrt(lnN - 0.78) points, no 3 in line, if you use Q of this same order. This is a poor result, I'm just mentioning it so you know how well repaired-randomness does, and also since this formula is rather more complicated than one might have naively expected. The appearance of square root of logarithm basically means that I do not trust my computer program's output for N<200, as a prediction about behavior for large N.

3 2

Re: [math-fun] Russian Postal Problem
by Henry Baker 10 May '16

10 May '16

Re ordinals: Jan considers Maria (see below) to be a (Russian) doll... Solution: Jan, being a mathematician, wants to send Maria the most elegant ring: a padlocked empty box labelled "Contents: 0 ring(s)". Maria, being a very practical woman, notices that the padlock itself is made of gold, and so she cuts it off & wears it on her finger. At 09:32 AM 5/10/2016, Eugene Salamin via math-fun wrote: >The hypothesis is "anything sent through the mail will be stolen unless it is sent via padlocked box". > >Therefore, the padlocked box will be stolen unless it is sent in a larger padlocked box. > >And so on. > >This problem could serve to segue into the ordinal numbers. > >-- >Gene > >From: Joerg Arndt <arndt(a)jjj.de> >Sent: Tuesday, May 10, 2016 9:17 AM > >* Dan Asimov <asimov(a)msri.org> [May 10. 2016 16:19]: >> This problem, and hundreds of other good ones, are in Peter Winkler's two books of fun problems for mathematicians. > >Peter Winkler: {Mathematical Puzzles: A Connoisseur's Collection}, A K Peters, (2003). > >http://www.maa.org/publications/maa-reviews/mathematical-puzzlesa-connoisse… > >Peter Winkler: > >{Mathematical Mind-Benders}, A K Peters, (2007). > >http://www.maa.org/publications/maa-reviews/mathematical-mind-benders > >In the latter we find our problem on page 9: > >"Love in Kleptopia Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. > >Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is sent via padlocked box. > >Jan and Maria each have plenty of padlocks, but none to which the other has a key. > >How can Jan get the ring safely into Maria's hands?" > >Yes, lots of lovely problems there. > >Best regards, jj

2 2

[math-fun] Russian Postal Problem
by Henry Baker 10 May '16

10 May '16

I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on. The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives. He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy. So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option. How does he safely send the ring to his partner?

15 30

Re: [math-fun] Russian Postal Problem
by Henry Baker 09 May '16

09 May '16

Alternatively, man gets in box with the ring & padlocks himself inside the box from the inside & has a friend mail this box to the lady. At 03:10 PM 5/9/2016, Fred Lunnon wrote: >> On Mon, May 9, 2016 at 2:30 PM, Victor Miller <victorsmiller(a)gmail.com> wrote: >>> Is the following within the rules? >>> >>> 1) Man sends box containing ring, padlocked to the lady. > > Incidentally, does the Russian postal service accept mail items >padlocked to ladies?

1 0

Re: [math-fun] Russian Postal Problem
by Henry Baker 09 May '16

09 May '16

Assuming locks are cheap, 1. B sends *unlocked padlock* in *unlocked box* to A. 2. A places ring in box & *locks with B's lock* & sends back to B. 3. B uses B's key to unlock B's padlock. Problem: Can Postal Service manufacture a key for an unlocked padlock -- perhaps using a quantum computer?

1 0

[math-fun] Russian Postal Problem
by Jim Gillogly 09 May '16

09 May '16

Another possibility I didn't see while skimming through solutions. The original statement said you could send a box with a combination lock. Send the ring in it, then after she phones you that she got the box, tell her the combination. The eavesdroppers get the news too late, and the post office would know there's no point waiting for somebody to send or call the information before the box arrives. -- Jim Gillogly

2 1

[math-fun] Lagarias's reformulation (& others) of RH
by Warren D Smith 09 May '16

09 May '16

http://arxiv.org/abs/math/0008177 Somewhat annoyingly, Lagarias uses the exp(x) and ln(x) functions, so his reformulation of the Riemann hypothesis is not entirely about integer arithmetic; real number arithmetic also is needed. Which kind of makes you wonder why he bothered, since as everybody already knew, the RH is equivalent to an error bound for the prime-counting function expressible using some real-functions such as Li(x), e.g. see Lowell Schoenfeld: Maths of Comput 30,134 (April 1976) 337-360, e.g: |PrimeCountingFn(x) - li(x)| < sqrt(x) * ln(x) / (8*pi) for x>2657 <==> RH. An entirely integer statement was cooked up by Martin Davis, Yuri Matijasevic, and Julia Robinson: Hilbert's Tenth Problem. Diophantine Equations: Positive Aspects of a Negative Solution, pp/ 323-378 in "Mathematical developments arising from Hilbert problems", Proceedings of Symposium of Pure Mathematics, XXVIII AMS 1974. See p.335. a collection: https://web.archive.org/web/20120731034246/http://aimath.org/pl/rhequivalen… -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1