four colour map proof
Dan Wright
simple attempt at a proof of the four-colour problem, over on alt.math
(under the same header as this posting). Perhaps this was the better
place to have started that discussion, but I don't want to reproduce
the whole thing. Not sure of the etiquette on all that...
Anyway, if interested people who haven't seen it would look, I'd
appreciate it.
Dan
David C. Ullrich
Wright) wrote:
>I've been trying to get people to consider and critique a relatively
>simple attempt at a proof of the four-colour problem, over on alt.math
>(under the same header as this posting). Perhaps this was the better
>place to have started that discussion, but I don't want to reproduce
>the whole thing. Not sure of the etiquette on all that...
It would be a lot more convenient than what you did, for someone
here who wants to look at it:
First I had to discover that there _is_ no alt.math(!) Then I had
to download a few hundred headers from _each_ of alt.math.recreational
and alt.math.undergrad to look for it. Then I found that if it ever
was there it's no longer on my news server.
>Anyway, if interested people who haven't seen it would look, I'd
>appreciate it.
So then I went to google and found it. I don't know why you're
asking for more feedback, it looks to me like people there have
already explained why it's wrong. The proof starts like so:
>This posting copyright 2003 Daniel James Wright.
>
>Can somebody tell me whether there's a flaw in the following argument
>for the validity of the four-colour map conjecture, and if so what?
>Thanks.
>
>For the conjecture NOT to be correct, it must be possible to create a
>map with a particular, "ultimate" country, U, for which none of the
>four colours in use is ever available. This in turn must be because U
>is bordered by (at least) four countries, P1-P4, already necessarily
>using up all of those colours.
The assertion in the first paragraph is simply wrong. Nat Silver was
exactly right when he pointed this out - your reply to his post seemed
to totally ignore what he'd said.
For the _theorem_ to be false _this_ must happen:
No matter how you try to color the countries one by one,
it must happen that you eventually reach a country U,
bordered by four previously colored countries P1-P4,
which _happen_ to have been colored using all four
colors.
There's a big difference between that and what you
said: It's not necessary that P1-P4 _necessarily_ use
all four colors, there could be another partial coloring
where they don't. And what countries U and P1-P4
lead to the problem can vary from attempted coloring
to attempted coloring.
>Dan
******************
David C. Ullrich
Chip Eastham
"Dan Wright" <daniel_ja...@compuserve.com> wrote in message
news:c76a7fdc.03033...@posting.google.com...
Hi, Dan:
I took a look. It seems you have an insight into the four color
problem, but no proof.
For a counterexample to four coloring of planar maps to exist it
is necessary and sufficient for there to exist a map of a bounded
region of the plane with single bounding curve C (a circular disk,
for example) that cannot be colored without using all four colors
somewhere along the boundary C.
The rest of your "proof" is mere hand-waving, I'm afraid. You
seize upon four countries P1-P4 along this boundary C and then
argue about classifying one or the other of them as necessarily
green or necessarily non-green, reaching apparent contradiction.
Your "contradiction" seems an error of reification, as some of
the commenters there were trying to point out. You didn't show
that any particular country such as P3 is both necessarily green
and necessarily non-green, only that under any coloring there
will be at least one green country on C and some that are not.
However the idea of using a curve to separate a map into simply
connected regions is a vital ingredient to the known proofs of
the four color theorem. The computationally intensive proofs
apply "discharge algorithms" to such regions in order to show
that there will always exist colorings which expose only three
colors around the boundary.
regards, chip
Jonathan Miller
>First I had to discover that there _is_ no alt.math(!)
>
But there is(!).
> Then I had to download a few hundred headers from _each_ of alt.math.recreational and alt.math.undergrad to look for it. Then I found that if it ever was there it's no longer on my news server.
>
Well, I don't know that you *had* to, but it was a reasonable start.
>So then I went to google and found it.
>
I don't know what you googled on, but I found it by googling groups for
four colour map proof by dan wright on alt.math. It popped right up.
> I don't know why you're asking for more feedback, it looks to me like people there have already explained why it's wrong.
>
I guess I'll refrain from commenting on this in the hope that the
feedback isn't convincing him because he feels it's not specific enough.
That *he's* hoping that he's close and the criticism is about some
detail and not the crux.
The crux is that (as far as anyone now knows), actually determining what
the exceptions *have* to look like is hard. Haken and Appel determined
that it had to be one of 1776 (surely some other number, bad memory)
basic configurations, and then went through on a case-by-case basis to
prove that those cases couldn't occur. Not easy.
Jon Miller
>
Dan Wright
you're saying with what I am, but now I get some of it. I now see the
equivalence between my idea of P1-P4 being exposed to a common
neighbour, U, and, as you say:
> For a counterexample to four coloring of planar maps to exist it
> is necessary and sufficient for there to exist a map of a bounded
> region of the plane with single bounding curve C (a circular disk,
> for example) that cannot be colored without using all four colors
> somewhere along the boundary C.
Clearly if such a map could be drawn, you could draw a loop around it,
and the shape between C and the larger loop would be my country U.
Okay. But I'm not convinced the rest is mere hand-waving, as you put
it.
> You
> seize upon four countries P1-P4 along this boundary C and then
> argue about classifying one or the other of them as necessarily
> green or necessarily non-green, reaching apparent contradiction.
First, my proof is about the possibility of BUILDING the
counterexample map. Next, since it's only four countries (presumably
ending up around your border C) that are required to take up all four
colours, I focus on whether it's possible to create a map with four
such countries in the very particular relationship of necessarily
having to be different colours.
I point out that it's easy to get three countries into that
relationship -- just make them all touch each other (though I also
leave open the possbility that there may be other ways, involving them
being connected by/to a larger structure, S). These are P1-P3. That
reduces the task to extending their mutual structure, S, to include a
P4 that necessarily takes whatever colour those three do not.
I conclude that that is impossible, because, basically, to accomplish
it, you'd need to have already accomplished it.
I hope you will have another look, based on the above. I know the
unlikelihood of any such argument being right, I just want to hear
something definitive on why it's not. Thanks.
Dan
David C. Ullrich
<jonathan...@comcast.net> wrote:
>David C. Ullrich wrote:
>
>>First I had to discover that there _is_ no alt.math(!)
>>
>But there is(!).
Hmm. My news server has never heard of it. So I started
with Googles list of groups. The way they present these
things seems a little deceptive - when I click on alt.math.*
I see a list of several groups alt.math.this and alt.math.that,
but no alt.math listed.
But I just checked, I don't find sci.math that way either,
and I believe that _it_ exists... oh well.
>> Then I had to download a few hundred headers from _each_ of alt.math.recreational and alt.math.undergrad to look for it. Then I found that if it ever was there it's no longer on my news server.
>>
>Well, I don't know that you *had* to, but it was a reasonable start.
>
>>So then I went to google and found it.
>>
>I don't know what you googled on, but I found it by googling groups for
>four colour map proof by dan wright on alt.math. It popped right up.
>
>> I don't know why you're asking for more feedback, it looks to me like people there have already explained why it's wrong.
>>
>I guess I'll refrain from commenting on this in the hope that the
>feedback isn't convincing him because he feels it's not specific enough.
Well, I tried to explain why it's wrong, including the correct version
of the statement in the paragraph...
> That *he's* hoping that he's close and the criticism is about some
>detail and not the crux.
>
>The crux is that (as far as anyone now knows), actually determining what
>the exceptions *have* to look like is hard. Haken and Appel determined
>that it had to be one of 1776 (surely some other number, bad memory)
>basic configurations, and then went through on a case-by-case basis to
>prove that those cases couldn't occur. Not easy.
>
>Jon Miller
>
>>
******************
David C. Ullrich
Chip Eastham
> Chip, thanks for your comments. It took me a minute to connect what
> you're saying with what I am, but now I get some of it. I now see the
> equivalence between my idea of P1-P4 being exposed to a common
> neighbour, U, and, as you say:
>
> > For a counterexample to four coloring of planar maps to exist it
> > is necessary and sufficient for there to exist a map of a bounded
> > region of the plane with single bounding curve C (a circular disk,
> > for example) that cannot be colored without using all four colors
> > somewhere along the boundary C.
>
> Clearly if such a map could be drawn, you could draw a loop around it,
> and the shape between C and the larger loop would be my country U.
> Okay. But I'm not convinced the rest is mere hand-waving, as you put
> it.
>
> > You
> > seize upon four countries P1-P4 along this boundary C and then
> > argue about classifying one or the other of them as necessarily
> > green or necessarily non-green, reaching apparent contradiction.
>
> First, my proof is about the possibility of BUILDING the
> counterexample map. Next, since it's only four countries (presumably
> ending up around your border C) that are required to take up all four
> colours, I focus on whether it's possible to create a map with four
> such countries in the very particular relationship of necessarily
> having to be different colours.
>
This is where you slip. A (minimal) counterexample would have
the property that every four coloring of the countries except U
would use all four colors along the boundary with U (my curve C).
You cannot conclude that along this boundary there are four
specific countries that always have four different colors. We
only know that every coloring of the countries other than U
requires some country along the boundary of U to use green,
to use red, etc. There is nothing that pins down the use of the
four colors there to the _same_ four countries in each coloring.
> I point out that it's easy to get three countries into that
> relationship -- just make them all touch each other (though I also
> leave open the possbility that there may be other ways, involving them
> being connected by/to a larger structure, S). These are P1-P3. That
> reduces the task to extending their mutual structure, S, to include a
> P4 that necessarily takes whatever colour those three do not.
>
> I conclude that that is impossible, because, basically, to accomplish
> it, you'd need to have already accomplished it.
>
> I hope you will have another look, based on the above. I know the
> unlikelihood of any such argument being right, I just want to hear
> something definitive on why it's not. Thanks.
>
> Dan
Been there, tried that. It's up to you now.
regards, chip
|-|erc
>
> >This posting copyright 2003 Daniel James Wright.
> >
> >Can somebody tell me whether there's a flaw in the following argument
your name really is Dan Wright!
Herc
Bill Jones
>
> Hi, Dan:
> For a counterexample to four coloring of planar maps to exist it
> is "necessary" and sufficient for there to exist a map of a bounded
> region of the plane with single bounding curve C (a circular disk,
> for example) that cannot be colored without using all four colors
> somewhere along the boundary C.
>
> regards, chip
The above conditions may be 'sufficient'; but are they 'necessary'? Is
it not possible that other conditions might also be 'sufficient'?
Bill J.
Prai Jei
news:962b628d.03040...@posting.google.com...
> > For a counterexample to four coloring of planar maps to exist it
> > is "necessary" and sufficient for there to exist a map of a bounded
> > region of the plane with single bounding curve C (a circular disk,
> > for example) that cannot be colored without using all four colors
> > somewhere along the boundary C.
> >
> > regards, chip
>
> The above conditions may be 'sufficient'; but are they 'necessary'? Is
> it not possible that other conditions might also be 'sufficient'?
I once had a go at tackling the problem along these lines. Assume that any
map of N or fewer regions could be so coloured (i.e. using no more than
three colours for the boundary regions). To a map of N regions, add a new
region on the boundary. The procedure was to device recolouring algorithms
such that the new map of N+1 regions could be recoloured as before. This
would clinch the theorem by induction.
It boiled down to seven basic cases. Three were trivial (no recolouring
necessary) and I was able to specify how to recolour three of the others.
The last one eluded me.......
Chip Eastham
Hi, Bill:
Yes, I believe it is necessary. Assume a map, uncolorable with four
colors, having the minimal number of countries with this property.
Trivially such a map must have at least five countries.
Pick any country U. The rest of the map is colorable (since it has
fewer than the minimal number for uncolorability), yet any such
coloring of the remainder of the map must always expose all four
colors on the boundary with U (otherwise the entire map would
be four colorable).
regards, chip
Dan Wright
now). Even though I thought you were going to say something pretty
much like that, and was already getting prepared to rebut, doing so
has taken me longer than I anticipated. That's some map, that
counter-example map! But, addled though my brain might be at the
moment, I can't find anything wrong with the following.
A configuration of countries must either have or not have the
following quality: that under any valid painting, some combination of
four of its exposed countries must take all four colours.
When adding a country to a configuration in which that is NOT the
case, the new country will either:
-contact three or more countries, of which three have to be different.
This contact will bury one of those original three, leaving at most
three of them now exposed that have to be different. (If there had
been more than one group of three that had to be different, the
possible sameness/differentness of WHICH three were exposed by any
pair of triads should prevent the new shape from having to be
different from any of them, either.)
-contact three or more countries, of which no more than two have to be
different. Since there are paintings in which this group of contacted
countries only uses two different colours, there are paintings in
which the added shape can take either of two colours, itself. Thus,
with respect to the whole configuration, this one does not increase
the number of exposed countries that have to be different.
-contact less than three countries. This new country can also vary,
and thus does not add to the number that have to be different.
Therefore, given any structure in which it's not the case that some
combination of four of its exposed countries must take all four
colours, it's impossible to add a country such that that is now the
case.
Dan
Dan Wright
posting, in regard to the case where the new country makes contact
with three or more countries, of which three DO have to be different.
If this succeeds in producing the counter-example map, you could
always REMOVE the middle of the three contacted countries, rather than
burying it. That would expose the necessarily fourth-colour country
that must have been constraining it. In other words, the
counter-example map can only be created by adding one country, if it
could have been created by removing one.
Bill Jones
In the original configuration, there was one country which bordered
with four other countries. As I understand, no one of these four
countries necessarily touches any of the other three. In the second
case, all of the countries in any group of four must have common
boundaries with each other!
Each configuration is 'sufficient' by itself. Therefore, neither is
'necessary'! Unless, I misinterpret the meaning of 'necessary'?
regards, Bill J.
Dan Wright
I've discovered a succinct, non-mathematical proof of the four colour
problem (unlikely), or that I haven't made the argument clear enough.
Here's what I think is a tighter version.
The argument takes the form, Is it possible to create the
counter-example map (wherein, in every valid painting, at least four
boundary countries take different colours), by adding a shape to one
that is not, yet?
It seems obvious that if you place a next country where it only
borders two others, the variability of the added country will always
allow it to be the same as one of the other boundary countries, and
you won't have created the counter-example map.
The same applies to a next country placed where it contacts three or
more others, of which it is NOT the case that three are different
under all colourings. Here, there are some colourings in which only
two of its neighbours are different, and the added country again
retains the ability not to take whatever fourth colour would complete
the set.
The case with a little more nuance is that in which the next country
makes border contact with three or more others, of which three always
ARE different colours. Here I made two contentions. The first one --
which may not seem to help much -- is that you're making no net gain
in boundary countries. The counterargument would be that you're still
getting the right arrangement of boundary countries, whatever the
number.
The second contention sort of spanned my two postings. If three of
its neighbours always vary, they can certainly force the new country
to always be a fourth colour, with respect to themselves. But as
always, such contact will bury one of the three from being a boundary
country -- what I call the "middle" one.
If it's now the case that some four boundary countries have to vary,
what was the case before? It must have been that these local three
had to vary, and there always had to be another one in the boundary
group that took the same colour as the middle one of these.
It seems pretty easy to show that that situation could only exist if
the actual counter-example situation could.
Thus the conclusion that the counter-example map can always be trimmed
to leave a smaller counter-example map, or, put the other way, that
transitioning up to the counter-example map is predicated on the
crucial structure already existing.
QED?
Dan
David Eppstein
daniel_ja...@compuserve.com (Dan Wright) wrote:
> By your lack of response, I must conclude either that you all agree
> I've discovered a succinct, non-mathematical proof of the four colour
> problem (unlikely), or that I haven't made the argument clear enough.
There's another possibility: that you're not even close to a proof,
sweeping all the difficult parts under the rug with phrases like "it
seems clear that", and we don't want to waste our time with cranks.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Christian Bau
> By your lack of response, I must conclude either that you all agree
> I've discovered a succinct, non-mathematical proof of the four colour
> problem (unlikely), or that I haven't made the argument clear enough.
> Here's what I think is a tighter version.
Now consider a very large country that touches every single country at
the border of your map. Take for example a map of the USA and draw a
thin, long country all the way around it. Didn't see you considering
anything like that.
Leonard Blackburn
> By your lack of response, I must conclude either that you all agree
> I've discovered a succinct, non-mathematical proof of the four colour
> problem (unlikely), or that I haven't made the argument clear enough.
> Here's what I think is a tighter version.
I think you're ignoring the responses. On the surface, I'm guessing
you're making some mistake similar to:
(for all x)[P(x) or Q(x)] implies (for all x)P(x) or (for all x)Q(x).
If not, I apologize for bringing it up.
-Leonard
Chip Eastham
Perhaps you are confusing my posts with those of Dan Wright?
My use of "necessary" and "sufficient" is in connection with logical
equivalence between two statements:
A) There exists a planar map which cannot be four-colored (so that
any two adjacent countries have different colors).
B) There exists a planar map S which consists of a country U and
other countries, such that every four-coloring of S' = S \ {U}
always results in at least one country of each color along the
border with U.
I thought that you were questioning the logical equivalence of
these two statements. You seemed to appreciate that B implies
A, but to doubt whether the reverse is true (that B is the "only"
way for the four-color theorem to be falsified). Therefore I
supplied an elementary proof of the reverse implication, that A
implies B.
If you were instead questioning the position of Dan Wright, I
apologize for inserting myself into the discussion. Dan's
claims do appear to hinge on four particular countries next
to U which always take four different colors (in any four
coloring of S'), and it appears that he attempts to infer
from this that these four countries are mutually adjacent
(hence that by inclusion of U one has five mutually adjacent
countries, which is known to be impossible in a planar graph).
I am but one of many people who have made an effort to point
out this gap in Dan's argument to him, apparently to little
effect. If in the process I have misled you into thinking
I was espousing his point of view, it is perhaps not as
unlikely an event as might appear after the fact. Part of
my discussion was to point out a kernel of valid argument
in Dan's thinking. One hopes to make it clearer by this
approach what precisely in mistaken about his argument.
regards, chip