Re:Graph Coloring, or Proof by Crayon
by Ogre on Tuesday December 18, 2012 @01:47PM
(#4938844)
My dad was a mathemetician ("was" as in he died in 2001, otherwise I'd be sending this to him to comment on). I never understood most of what he did, but I know that some of the work he did was based on or related to the four-color proof referenced here. I once had a slightly less math intensive book (but still very academic) mainly about the four color theorem that referenced one of his papers as well, but alas I don't have it handy to find the relevant quote. I don't know where my copy went, but I bet my mom still has one.
I don't know that I have a point to this really other than to say that this post reminded me of my Dad, and all the things I haven't been able to send him links to for the last 11 years.
Re:Graph Coloring, or Proof by Crayon
by AbsoluteZeroFF on Tuesday December 18, 2012 @01:39PM
(#4938816)
I find it amazing that people with such a deep and detailed grasp of mathematics such as this person are able to also express very advanced concepts in layman's terms through real-world examples and practical applications.
I'm only a semi-advanced secondary school student, so many of the concepts are way over my head at this point. Things like this article serve as catalysts to curiosity and are inspirations to pursue the study of the mathematics.
Re:Graph Coloring, or Proof by Crayon
by richforrester on Tuesday December 18, 2012 @07:52PM
(#4940621)
That's pretty much what I came to post here, but way more eloquent than when I would've written it :)
Articles like this make me realize that what was the most boring subject in school 10 years ago, is now quickly becoming my favorite tool in the world. Gotta love mathematics.
Re:Graph Coloring, or Proof by Crayon
by pjungwir on Tuesday December 18, 2012 @02:10PM
(#4939000)
If people want more like this, _Introductory Graph Theory_ by Chartrand is an enjoying and easy read. In fact it looks like Dover has all kinds of short treatments of math subjects suitable to the layperson. And if you don't know about Martin Gardner, you really must check him out! _The Colossal Book of Mathematics_ and _The Night is Large_ are both wonderful big collections, and there are tons of smaller sets of essays.
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @02:52PM
(#4939227)
I spent an afternoon one-on-one with Martin Gardner just a couple of months before he passed away. Fantastic man, wonderful to be with, and still sharp as anything at 95.
Deeply missed - I so wish I'd got in touch with him earlier. Like 40 years ago.
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @04:38PM
(#4939730)
It is true under the convention that we color each contiguous region the same color, and each contiguous region can get any color. It is pretty clearly not true if you insist that non-contiguous regions must be colored the same, which is what happens with enclaves.
This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @04:59PM
(#4939835)
In mapping, enclaves are usually colored the same as the "parent" country to which they belong. It's an additional restriction that's actually well catered for in the generic graph coloring context, as opposed to the "map" coloring of the original problem (which did not bother with the enclave issue).
Re:Graph Coloring, or Proof by Crayon
by esrauch on Tuesday December 18, 2012 @06:21PM
(#4940244)
I believe his claim is that one country has 4 disconnected regions. If you have that and can only use one graph node to represent all of the disconnected regions then the adjacency graph isn't necessarily planar.
Re:Graph Coloring, or Proof by Crayon
by jscipione on Tuesday December 18, 2012 @03:18PM
(#4939365)
I don't understand why the Costa Rica example is 3-colorable. The green province in the middle touches 5 other provinces so it seems like it should be 5-colorable.
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @03:48PM
(#4939501)
Consider a pizza sliced into six pieces. Each piece touches only their neighbor on each side, so you can color them alternately red and blue. Now suppose someone carved an island in the middle around an olive that no one wants. That touches all six, but can still be colored green, so we use only three colors in total, despite the middle "region" having six neighbors.
Re:Graph Coloring, or Proof by Crayon
by Evbn on Tuesday December 18, 2012 @03:29PM
(#4939412)
I don't know Paris specifically, but but nautilusy spiral happens (in anthropology, and also biology) when new growth happens that the position closest to the center, which is a natural goal when proximity is a desirable feature (minimized construction costs, maximize access to community, minimize outer perimeter for defense, etc)
I don't know that I have a point to this really other than to say that this post reminded me of my Dad, and all the things I haven't been able to send him links to for the last 11 years.
I'm only a semi-advanced secondary school student, so many of the concepts are way over my head at this point. Things like this article serve as catalysts to curiosity and are inspirations to pursue the study of the mathematics.
Articles like this make me realize that what was the most boring subject in school 10 years ago, is now quickly becoming my favorite tool in the world. Gotta love mathematics.
Deeply missed - I so wish I'd got in touch with him earlier. Like 40 years ago.
6 - R
7 - G
1 - B
15 - B
16 - R
8 - Cannot be R G or B
I tried to find if there was some theory behind it but all I could really find was "saturation degree".
Not true. A map of a country with four or more enclaves (e.g. late 19th century China) would not meet this condition.
This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.
The traditional 4-color map rule only says that each neighboring region has a different color, not that the colors are meaningful.