Math Is Fun Forum

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Mapping with only four colors-proof by Li, Ming and me

I used to say in another post that a Chinese philosopher was going to public his proof online on mapping colors can be four. Now that he (Li (or Lee), Ming) has fulfilled his promise, I am glad to public a George-revised version of his publication. However the "proof" has been recently found insufficient and false so anyone who lacks time can just ignore this thread-added on 2/22/07

First, let's investigate the Mapping problem into some depth.

Apparently it's about how to color a map with only four colors. But in fact these four colors can only distinguish neighboring regions rather than countries. We should not expect  to display countries with multiple seperate regions with one color and allow different colors for each region. That is to say, continential U.S. and Alaska can be demonstrated by two colors, Britain Island and Northern Ireland can have two colors. Insular Italy and Sicilly can have two colors. After all, two colors may fulfill the task to distinguish them from the around, though failling to identify them as one.

The next step is to define neighboring and seperate clearly. Of course, they should be defined as complementary- nonneighboring is seperate. But in practice, let us concentrate on how to painta map. Take a chessboard for example, the blacks are only neighboring whites, but a black should not be regarded as neighboring to the four blacks diagonal. Yes they are neighboring on four POINTs, but ONE color(black) can distinguish them already. This is different than two regions neighboring on a line segmene when one color confuses the two. Thus Li, Ming defined neighboring as the state when two regions have a common boarder with a length larger than infinitesimal, and seperate as nonneighboring.

To be continued...

Last edited by George,Y (2007-02-21 22:24:49)

---

X'(y-Xβ)=0

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Mapping with only four colors-proof by Li, Ming and me

I used to say in another post that a Chinese philosopher was going to public his proof online on mapping colors can be four.

Is this what you're saying?  The following map can't be colored by 3 colors.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

yes, but by 4 colors.

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

This is what I was saying. This map can be paint by only 2 colors. Note that the diagonal two with crossmarks aren't neighboring to each other according to Li, Ming's defination.

---

X'(y-Xβ)=0

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Mapping with only four colors-proof by Li, Ming and me

Right George.  The map I posted can only be colored by 4 colors.  You were talking about a proof.  Is this not sufficient?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

The four color map problem studies the possibility of any maps. You have only a particular one. You know the difference, don't you?

---

X'(y-Xβ)=0

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Mapping with only four colors-proof by Li, Ming and me

The theorem in your opening post is that "mapping colors can be four."  No?  Doesn't just one example prove this?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Re: Mapping with only four colors-proof by Li, Ming and me

I remember reading about this proof. I believe a key part of the proof was a computer program, and the logic of the program was incorporated in the proof. Just as memory serves me. Maybe I should consult Wikipedia on this.

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Re: Mapping with only four colors-proof by Li, Ming and me

Wikipedia states "... was the first major theorem to be proven using a computer, and the proof is not accepted by all mathematicians because it would be unfeasible for a human to verify by hand..."

The article also talks about Non-Contiguous Regions!

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Mapping with only four colors-proof by Li, Ming and me

Ah, so the theorem is that all such maps are of color 4 or less.  Why couldn't you just say that, George? 

mapping colors can be four

Rather, mapping colors must be four or less.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Yes, exactly. I supposed everyone knows this theorem but I was wrong. Perhaps it's better for me to replace "a map" in my first post by "any map".

Apparently it's about how to color aany map with only four colors.

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Apparently what I discussed in the 3rd graph is on real maps, which means practical cases rather than a simple sample map, Ricky.

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

OK, I need to tell something about the context. The mapping with only four colors problem originally occured in a French mind one or two centuries ago. He looked at the world map, and thought:"why not reduce the number of colors needed to a minimum?" He thought 4 or 5 might be the answer. But so far, only 5 is proved. The 4 is proved only by program, as mathsisfun just wrote. During the solving history, people found the theorem should be refined a little bit-that is on countries with multiple seperate regions, as I have discussed in Post 1.

I sincerely hope that the readers-including you-know how hard this theorem is.(After all, one century is a long time  )

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

The article also talks about Non-Contiguous Regions!- Does it allow multiple colors for continential US and Alaska?

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Continued:

Ming then defined a group of regions that are neighboring to each other as an All Neighboring Group(ANG) .
He then investigated how many regions  such a group can have. So far, we only can find a maximum of 4 regions that can compose an ANG on a plane or on a sphere.

We can list them below.
1 region, covering all the map.
2 regions, 2 types:

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

ANG of 3 regions, 3 types:

Last edited by George,Y (2007-02-17 16:36:14)

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

ANGs of 4 regions:

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Note the chess board in Post 4 is not an All Neighboring Group because diagonal squares are not neighboring according to the defination of neighboring. We may also note that to distinguish any ANG, the number of colors is always the same as that of regions (because any is neighboring to and must be distinguished from the rest). Actually the chessboard consists only ANGs of 2 regions, and two colors- black and white are enough to distinguish all the squares.

In addition, maps of a sphere is more or less the same.

But so far, is there an ANG of 5 regions? or of 6 regions? Luckily if we found a ANG-6 or more we could easily get a ANG-5 as a part of it. So the question can be narrowed into whether we can find an ANG-5 on a plane or on a sphere. However, can you?

Thus Ming pospulated the Axiom:
An All Neighboring Group on a plane or on a sphere has at most 4 regions.

Another Theorem proposed by me:
To color an ANG, you cannot use  colors less than the regions it has.
It's easy to prove this theorem by simple logic or common sense. You color one region, then the other, but not the same color, the third not the same to any of the previous... until you complete.

To be continued...

---

X'(y-Xβ)=0

Jai Ganesh

Administrator

Registered: 2005-06-28

Posts: 46,245

Re: Mapping with only four colors-proof by Li, Ming and me

I had read long time back, in FLT by Simon Singh, about this.

Here is a good link on the topic.

These images would help in understanding the problem.

---

It appears to me that if one wants to make progress in mathematics, one should study the masters and not the pupils. - Niels Henrik Abel.

Nothing is better than reading and gaining more and more knowledge - Stephen William Hawking.

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Back to Ming's Axiom:
An All Neighboring Group on a plane or on a sphere has at most 4 regions.
All means any two of it obey "neighboring".
"Neighboring" means the two have a common boarder different than a single dot.

Naturally, I derive a corollary from the axiom.

Any region can  neighbors the each of  at most 3 regions that are neighboring to each other.

The proof is easy, if the corollary is wrong, more than 3, the axiom is thus false. So if the axiom is true, the corollary must be true.

Then here is my method of coloring a blank map:

First, prepare 4 colors on a panel.

Then, find an ANG and use different colors from the 4. The number of the colors can at most be 4, so you don't need any new color.

Then find a neighboring region that at least neighbors one of the colored region and color it using a color different than those of all the neighboring colored regions. Surely those colors at most are 3, from the panel 4. At this extreme circumstance you only need the last one of the 4, again you do not need a new color different than the 4 on the panel. On other circumstances, you surely have more choices, but still within the 4 on the panel.

Repeat the step above, again and again, until you color all the regions on a given map. And the map is colored by the 4 colors on your panel.

The proof is done.

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Any questions or confusions???

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Note that if a regions neighbors more than 3 colors, they must be seperated into different ANGs, which allows you to use colors repeatedly.

Take the latter map of Post 17 for example, Now suppose you have to color the black region(suppose it is blank) but it neighbors 4, the 3 inside and the arounding post region(sleek blue). We only need to consider the 3 inside. So we choose a color different from them(black), then we can solve the outside that is seperate from the 3 inside. We can use red, yellow or blue repeatedly to color the outside.

Well, the third paragraph
Then find a neighboring region that at least neighbors one of the colored region and color it using a color different than those of all the neighboring colored regions. Surely those colors at most are 3, from the panel 4. At this extreme circumstance you only need the last one of the 4, again you do not need a new color different than the 4 on the panel. On other circumstances, you surely have more choices, but still within the 4 on the panel.

has this FLAW:

The new region may neighbor more than 3 colored regions. Despite that at most 3 of them are neighboring to each other, requiring 3 different colors, the existing neighboring regions may have been already colored by 4 colors.

Uhhh...difficult

---

X'(y-Xβ)=0

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Mapping with only four colors-proof by Li, Ming and me

The statement has more potential to be false on a sphere than on a plane, because of regions being able to loop around.

For example, on a sphere, the regions | A | B | C | would all be touching each other, but on a plane A and C would be separated.

I've tried finding a counter-example that involves using those loops, but I haven't found one yet. Of course, that isn't helped by the fact that I'm not entirely sure what the net of a sphere is.
I can show that the rule definitely doesn't apply to a map on a donut though.

---

Why did the vector cross the road?
It wanted to be normal.

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

Yes he admits the donut will be different. But he states that a sphere is more or less the same as a plane with infinite streches-you can assume the four infinite corners picked together as the other pole of the sphere. Projective Geometry, he argues.

---

X'(y-Xβ)=0

George,Y

Member

Registered: 2006-03-12

Posts: 1,379

Re: Mapping with only four colors-proof by Li, Ming and me

His orginal proof does not provide a method like mine, instead he simply claims any map is composed by combinations of ANG-2, ANG-3 and ANG-4. So his proof is insufficient too.

---

X'(y-Xβ)=0