Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5? https://cp4space.wordpress.com/2018/04/15/assorted-news-3/ The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle. Best wishes, Adam P. Goucher
A nice image of the currently smallest known unit-distance graph with chromatic number 5 is here http://www.cs.utexas.edu/~marijn/CNP/826.pdf found by Marijn Heule. It has 826 vertices. For information see https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simpli... On Tue, Apr 17, 2018 at 6:37 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5?
https://cp4space.wordpress.com/2018/04/15/assorted-news-3/
The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle.
Best wishes,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The fact that the graph is so asymmetric gives me a strong intuition that it is nowhere near minimal. On Wed, Apr 18, 2018 at 10:21 AM, James Buddenhagen <jbuddenh@gmail.com> wrote:
A nice image of the currently smallest known unit-distance graph with chromatic number 5 is here http://www.cs.utexas.edu/~marijn/CNP/826.pdf found by Marijn Heule. It has 826 vertices. For information see https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread- simplifying-de-greys-graph/#comment-3867
On Tue, Apr 17, 2018 at 6:37 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5?
https://cp4space.wordpress.com/2018/04/15/assorted-news-3/
The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle.
Best wishes,
Adam P. Goucher
_______________________________________________ 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
Here is the minimal counterexample to Tait's conjecture (about hamiltonian cycles), which has an order-2 automorphism group. http://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html -- APG.
Sent: Wednesday, April 18, 2018 at 4:33 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Aubrey de Grey
The fact that the graph is so asymmetric gives me a strong intuition that it is nowhere near minimal.
On Wed, Apr 18, 2018 at 10:21 AM, James Buddenhagen <jbuddenh@gmail.com> wrote:
A nice image of the currently smallest known unit-distance graph with chromatic number 5 is here http://www.cs.utexas.edu/~marijn/CNP/826.pdf found by Marijn Heule. It has 826 vertices. For information see https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread- simplifying-de-greys-graph/#comment-3867
On Tue, Apr 17, 2018 at 6:37 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5?
https://cp4space.wordpress.com/2018/04/15/assorted-news-3/
The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle.
Best wishes,
Adam P. Goucher
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, there are sad exceptions. I assume that the searchers have considered exploring the space of nested p/q-gons with strategically placed cross-links? On Wed, Apr 18, 2018 at 12:04 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Here is the minimal counterexample to Tait's conjecture (about hamiltonian cycles), which has an order-2 automorphism group.
http://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html
-- APG.
Sent: Wednesday, April 18, 2018 at 4:33 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Aubrey de Grey
The fact that the graph is so asymmetric gives me a strong intuition that it is nowhere near minimal.
On Wed, Apr 18, 2018 at 10:21 AM, James Buddenhagen <jbuddenh@gmail.com> wrote:
A nice image of the currently smallest known unit-distance graph with chromatic number 5 is here http://www.cs.utexas.edu/~marijn/CNP/826.pdf found by Marijn Heule. It has 826 vertices. For information see https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread- simplifying-de-greys-graph/#comment-3867
On Tue, Apr 17, 2018 at 6:37 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5?
https://cp4space.wordpress.com/2018/04/15/assorted-news-3/
The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle.
Best wishes,
Adam P. Goucher
_______________________________________________ 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
_______________________________________________ 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
For nested p/q-gons, I did that search awhile ago. At my write-up I give a picture of a 4-chromatic unit distance graph based on nested 7-gons. I'm not sure if I'm the one that found it first. http://community.wolfram.com/groups/-/m/t/1320004 It may be the smallest unit-distance 4-chromatic graph with no 4-cycles. The most extreme nesting comes from the 30-gon, and this graph is included in Mathematica as GraphData[{"UnitDistance", {391, 1}}] It's a very dense unit-distance graph, with 2190 edges. When I found it, I asked a few graph theorists if they could color it. Turned out it only needed 3 colors. --Ed Pegg Jr On Wed, Apr 18, 2018 at 12:16 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Yes, there are sad exceptions.
I assume that the searchers have considered exploring the space of nested p/q-gons with strategically placed cross-links?
On Wed, Apr 18, 2018 at 12:04 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Here is the minimal counterexample to Tait's conjecture (about hamiltonian cycles), which has an order-2 automorphism group.
http://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html
-- APG.
Sent: Wednesday, April 18, 2018 at 4:33 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Aubrey de Grey
The fact that the graph is so asymmetric gives me a strong intuition that it is nowhere near minimal.
On Wed, Apr 18, 2018 at 10:21 AM, James Buddenhagen < jbuddenh@gmail.com> wrote:
A nice image of the currently smallest known unit-distance graph with chromatic number 5 is here http://www.cs.utexas.edu/~marijn/CNP/826.pdf found by Marijn Heule. It has 826 vertices. For information see https://dustingmixon.wordpress.com/2018/04/14/ polymath16-first-thread- simplifying-de-greys-graph/#comment-3867
On Tue, Apr 17, 2018 at 6:37 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Did you hear the exciting news that Aubrey de Grey has increased the lower bound on the chromatic number of the plane from 4 to 5?
https://cp4space.wordpress.com/2018/04/15/assorted-news-3/
The best upper bound is 7 (from colouring the cells of a hexagonal lattice of appropriate size). The previous lower bound of 4 is from the Moser's spindle.
Best wishes,
Adam P. Goucher
_______________________________________________ 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
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Adam P. Goucher -
Allan Wechsler -
Ed Pegg Jr -
James Buddenhagen