This week’s installment of mathematical problems is
going to be about the four color problem. This problem has to with the involvement
of filling in maps with different colors. The problem started with physical
maps of countries and boundaries, and then shifted into a more abstract
mathematical field. The problem will be covered first, followed up with a five
color solution proof, and finally some history.
The four color problem is, if there is a map can all
the countries or states can be filled in with four colors, in that no two same
colors come into contact with each other. This was purposed in the mid 1800's
and since then people have been filling in actual geographical maps with four
colors. No matter the complexity of the geographical map, it will not require
more than four colors to fill in all the boundaries. The map of the world can
be done, the map of the Untied States can be done, and so can the map of the United
Kingdom counties. All geographical maps fit these criteria. This is where the realm of
mathematics steps in. Instead of using maps that already exist, can a map be
created that can disprove this conjecture? This is because for the average
person, it is a lot simpler to come up with a counter argument rather than
proving it. So people started creating maps, and filling them in. There arose a
problem of repeating maps being checked. Though two maps look different if the
share the same type of relation between borders, then they are in essence the
same map. So instead of filling areas on maps countries were represented with
colored dots. If two countries touched reached other, they were connected with
a line. This allowed for redundancy to be removed, and allowed for deeper
analysis. This deeper analysis comes from the fact that the problem has been
shifted from a coloring book problem, to a networking problem. In the 1970's
this problem took off with the newfound interest in computer science, that arose
in the time period. There is some rather useful insight about networking that
comes in handy in solving the problem. If there is a country, call it country
x, country x can be connected up to five other countries. Meaning in a given
map every country can only connect with five other countries and still fit the
parameters of a map. That is a very useful bit of information to have, because
it allows the problem to simplified, and narrowed down. This will be apparent
in the proof of at least five colors can be used.
In the last part it was mentioned that a country
must have a network with anywhere from one to five connections in it. That part has
its own proof, which was not covered. Going off of that information to prove
five colors, start with seven colors, and work down to five. If there is a map
with seven colors, assuming it is the smallest map with seven colors, there has
to be one of those country x's that follows that networking rule. If that
country is removed, or pulled from the map, then there is a smaller map. The
smaller map would only require six colors then, and if the country x is put
back into place, now there is an extra color that country x can now take,
reducing the number of colors needed. This process can be done down to five,
though five requires a tad more information and proofing, but can be done using
the same logic.
In the mid 1800's a map creator was coloring in the counties of Great
Britain. He tried to optimize his map by filling it in with as few colors as
possible, without the same color touching. He worked at it, and did it with
four colors. He assumed that four colors might be enough to fill any map then.
He purposed the idea to his brother, who in turn passed the idea onto a
mathematician by the name of Augustus De Morgan. Augustus is a famous
mathematician, who is responsible for putting the problem together, and getting
it some attention. The problem remained unsolved for one hundred and twenty
five years after its proposal. Kenneth Appel and Wolfgang Aachen did not solve
it until the 1970’s. There proof was controversial because it was the first
mathematical proof to be done by the use of computer power. Which at the time
was a not considered a guaranteed source.
No comments:
Post a Comment