Dr. Kenneth Appel and the Four Color Map Theorem: Part 2

When mathematicians look at the four color map problem, they often turn the regions into vertices or nodes - here represented by ovals - and draw a line between any two nodes whose regions share a border. This object is called a graph, and because none of the lines connecting nodes crosses any other, the specific type of graph is called planar.

Dr. Kenneth Appel proved that all such planar graphs can be painted with four or less colors such that no two nodes that have a line connecting them directly are the same color. If you think about any graph, you could always add a new node an a few lines from that node to some of the other nodes on the existing graph. The implication of this is that there are infinitely many graphs.

Here's the tricky part of Dr. Appel's proof and I will not try to present an explanation for it.  There are ways to make one graph equivalent to another, which means that if one graph can be four-colored, the equivalent graph can be four-colored as well. Even though there are infinitely many graphs, Dr. Appel's method proved there are exactly 1,936 different equivalence classes.

It's not uncommon for mathematical proofs to have to several cases that have to be taken separately, but 1,936 is a lot of cases.  Instead of doing each one by hand, Appel decided to write a computer program that looked at every case. When it was finished and it had looked at all the data, it had proved each of the cases could be color with no more than four colors and the proof was complete.

There were many mathematicians who were not satisfied with the new method, but there were many who saw this as a way to use computers to forward the field of mathematical inquiry. While the controversy is not yet over, Appel's proof is accepted and the use of computers in math research is much more common now than it was in the 1970s.

Best wishes to the family and friends of Dr. Kenneth Appel, from a fan.

Dr. Kenneth Appel and the Four Color Map Theorem: Part 1

Dr. Kenneth I. Appel died earlier this month at the age of 80. He is best known in mathematics four proving the Four Color Theorem, which states that any map of regions drawn on a flat piece of paper can be colored with no more than four colors in such a way that no two neighboring regions are the same color.

The proof was controversial in its day - the 1970s - because it used a computer to complete a vital but time consuming step.

Here is a map of the Western United States. Let me show a way to color it using four colors. It is not unique and the method I use causes a problem at the end, but by switching things around that problem can be solved.

An important idea in map coloring is that two regions are adjacent if they have a common edge, not if they meet at a common corner. In this example we have the four states that meet at a corner, In the same way a checkerboard can use two colors without people being confused, we can have Arizona and Colorado share a color, here signified by the number 1, and New Mexico and Utah share a different color, signified by the number 2.

Having done this, we now have states that border a 1 state and a 2 state, so I give all these states - Nevada, Wyoming and Oklahoma - the number 3.

Having done things in this method, I will now be forced to use a fourth color when mapping Kansas and Nebraska, and likewise there will be a forcing issue once, California, Oregon and Idaho are colored in. I also colored in Texas with a 1 since it was bordered by a 2 and 3.

I can easily finished the rest of the map, but this pattern has a problem. Imagine that some single region surrounds all these states. Because states on the outside edges have all four colors, this huge imagined state would have to be a fifth color, which would say four colors do not suffice. If I had started the problem knowing about that constraint, I could have still solved the new problem with four colors. The easiest way to do this changing as few states as possible is to switch the 3 and 4 in Wyoming and Nebraska, switch the 3 and 4 in Nevada and Oregon and change Washington to a 2. Then all the states on the outside have the numbers (colors) 1, 2 and 3 and the surrounding region can be given the color 4.

Tomorrow, I'll give a sketch of the proof, glossing over some difficult math and discussing the controversy of using computers in proofs.

I present this picture as tribute of the moment. Appel was at the University of Illinois when he published and the local post office commemorated his achievement with this postmark stating FOUR COLORS SUFFICE. It became a collector's item for mathematicians, like this postcard sent from the Urbana post office to Ulm, Germany while the postmark was being used.
 

The Statistical World: Part 3, life and death

When discussing probabilities, the two common measurement systems are ratios and percents. A ratio would be written as 1 chance in 3 or a probability of 1/3. The same number as a percent would round to 33% or possibly 33.3%, which as a fraction would be 33/100 or 33.3/100. Going past a tenth of a percent in rounding is rare.

When discussing death statistics, the usual time period is a year and the usual scale is per 100,000 population. The most likely causes of death for all adults are heart disease and cancer, both currently slightly under 200 deaths be 100,000 population in the United States, according to The New England Journal of Medicine.

Heart disease is dropping quickly as a cause of death. In 1960, it killed 369 of every 100,000 people, nearly twice the rate we see today. Cancer, on the other hand, is rising slowly. It went from 149 of 100,000 in 1960 to 186 of 100,000 in 2010. The general consensus is that we are seeing more cancer deaths because people are living longer and not dying of other diseases.

And then there is death by violence. In the general population, it is a much smaller risk than the major diseases. In 2010, accidents caused 38.2 deaths per 100,000 population, making it the fifth most common killer. The only other death by violence in the top ten these days is suicide at 12.2 per 100,000. The murder rate is much lower.

I show a picture of a gun here because of the noticeable dichotomy in suicide rates between men and women. Women's suicide rate is less than 5 per 100,000 while men's rates about 19 per 100,000. That would seem to say men are about four times more likely to kill themselves than women are, but that is not the entire picture. When looking at reported suicide attempts, women try to kill themselves at a rate three times greater than men's. Multiplying three by four, this means a man attempting suicide is twelve times more likely to succeed than a woman.

Men attempting suicide are much more likely to use a gun than women are. For all the fear we have of mass killers, the biggest public safety problem concerning guns happens alone behind closed doors.

   

I apologize here midway through this post for morbidness, but it is about to get worse. Now we look at infant mortality, babies born alive but not surviving to a first birthday. Instead of being counting on the scale of 100,000, infant mortality is counted per 1,000 live births.

In 1960, infant mortality was much worse than it is today, even in industrialized nations. The United States was losing 26 of every 1,000 babies, which would round  2.6% By reports I have seen, it was significantly worse in 1956, the year infant mortality mattered to me personally, though I was blissfully unaware.

Unaware, but not untouched. When I was a baby, I contracted bronchialitis, an inflammation of the small blood vessels in the lung. There have been attempts to find a cure, but now as then, for the most part this is a watch and wait situation. I was fed through a tube in my heel and - spoiler alert - I survived. The scar, once very noticeable, is now high up on my ankle.

This graph shows six countries arbitrarily chosen from among the industrialized world: France, Ireland, Sweden, Switzerland, the United Kingdom and the United States. Even in 1960, we were not "number one", as we so often have been taught to think of ourselves. Now we are in sixth place out of these six. 

This is not random chance. Every country we think of as being "advanced" or "industrialized" does a better job of keeping babies alive. The countries we compete with are like Croatia and other Eastern European still trying to catch up after decades of living under backward Communist rule. (Notice that the countries ahead of us all practice what is called socialism by American standards.)

Infant mortality is a difficult and complex subject. It is getting better, even in the worst places, but even in the best places that are around 2 per 1,000 live births lost, that would multiply out to 200 per 100,000. it's as bad as heart disease is for the general population.

Infant mortality is not part of the general conversation in this country. It should be and it should not be a cause of conflict culture, one political side against another. We have the means to do better. We only need to add the political will.

The Statistical World: Part 2

As someone who use to gamble much more than I do now,  I have a visceral understanding of probability that non-gamblers do not have.

For example, if we reach this position in a game of backgammon, here are the odds of winning.

If it's black's turn: game over. Black wins 100% of the time.

If it's White's turn: There are exactly 19 rolls that win and 17 rolls that lose. It's a little better than flipping a fair coin, which would be 50%-50%. This rounds to 52.8% chance to win and a 47.2% chance to lose.

The only thing to question is if "fair dice" exist, or even "fair coins". Lots of data has been compiled and the answer is yes. Most coins in your pocket will come up heads when flipped about 50% of the time, and most dice have a roughly even distribution of the six possible numbers.

And then there is randomness in the real world. if you saw the first episode of Mad Men, you might recall that the Surgeon General's 1960 report on the effects of smoking and the subsequent publishing in Reader's Digest was a major plot point. To drive home the point that Don Draper is not just a pretty face, he comes up with the Lucky Strike slogan "It's toasted" on the spot when pitching to the worried owners.

If fact, the slogan is real and pre-dates the 1960 advertising crisis by several years. Mad Men's first episode gets several things right, including that the tobacco industry would be barred from using testimonials from doctors or even dentists in the years to come.

But what are the exact probabilities of cigarette smoking causing you harm and shortening your life? Here the numbers get hazy. Many different factors can be considered other than smoking, some that make things better and some that make things worse. It is about as far as you can get from an exact science, but serious experts take randomness into account and still claim smoking has multiple ways it can screw up your health, many of them very significant changes for the worse indeed.

Tomorrow, we talk about the randomness.

The statistical world: Part 1

We live in a statistical world. What I mean is that for most of the decisions we face, there are some choices that are better than others, but they do not guarantee success or even that minimal level of success, breaking even.

Tic-tac-toe is part of the mathematical world. In the mathematical world we have proof, a guarantee of success or a guarantee of failure. If two player are at the maximum skill level in tic-tac-toe, every game is a draw, because the first player puts his or her mark in the center and the second player puts the opposite mark in one of the four corners.

Not every game in the mathematical world ends in a draw. In the simple number game "How much money does your dad make?", the first player names a number and the second player can always name a higher number. There are other simple games where going second is a forced win, like certain variations of Nim.
 

Yahtzee is the commercial name for a game that has been around for a long time. It is more involved than tic-tac-toe, but at the end of the 20th Century computer scientists "solved" the game, meaning they found the optimal play in every possible situation, meaning every possible roll with even possible combination of scores you have already achieved. If you were to match two computers perfectly programmed, you would not expect a draw in every game. In fact, actual tie scores should be extremely rare. What you would expect in the very long run is that both sides would win equal numbers of games, regardless of who played first or second. (Yahtzee is really a solitaire game, though usually played in groups. My dice rolls do not effect yours and vice versa, though some players might make decisions because they are ahead or behind late in a particular game that they would not make in a true solitaire game.

Even though we know the best way to play, it does not insure victory or even a draw every time. Randomness is so great in Yahtzee that the best possible strategy might lose to some other strategy if both players are promised to roll the same values in all cases until the game ends.

This is what I mean by the statistical world. Risks and rewards may or may not be completely understood, but even if we know the odds down to exact values, randomness can produce very strange results. Tomorrow, I will discuss the idea of assessing risk, something we do not always do very well.
 

U.S. vs. the Rest of the World: Climate change as measured from the 1988-1999 to 1999-2010 eras

Here's the map of consistent weather stations in the United States - with a few scattered in southern Canada - that reported at least one temperature every season from 1988 to 2010. If you go on comment boards around the Internet, there are people who post with confidence that global warming has stopped and the world has not gotten warmer since 1998.

The data shown here does not agree with that statement. I use the method of comparing two eras that start and end in strong La Niña years with a strong El Niño in between. I could switch and use strong El Niño years and the endpoints with a strong La Niña in between, but that would not bring us as close to present day as this method does.

What can be said is that the warming trend slowed down using this measurement system. Here are the numbers from the United States stations compared to the data from the rest of the world.

Total stations: 
U.S.A.: 3094
Rest of world 3363

Warming stations vs. cooling stations
U.S.A.: 71.5% warming, 28.5% cooling
Rest of world: 79.0% warming, 21.0% cooling

Average temperature change:
U.S.A.: 0.19° C
Rest of world: 0.29° C


This is still a warming trend, but not as fast as we saw comparing 1975-1988 to 1988-1999. If this continues, this would mean about a degree rise Celsius in the U.S.and a degree and half everyplace else. This is under the two degree per century threshold which climate scientists consider catastrophic.

Notice that the rest of the world has finally caught up and surpassed the United States in total consistent weather stations. A regularly reporting weather station is a useful thing, but not a vital part of the infrastructure. It's something of a luxury and back in 1955 the United States far outstripped the rest of the planet in being able to afford such luxuries, the aftereffects of World War II ten years earlier still being felt by the countries where the battles were fought.  As so many statistical measurements tell us, we are no longer number one in the world in quality of life.


Another number that jumps out at me is that no matter how many stations report in the United States and how many stations report every place else, the ratio of the temperature change stays relatively constant, the rest of the world warming a little more than 50% faster than the U.S. This could just be coincidence, but it would be interesting to find out why. If there is a cause other than random chance, it might mean the United States is doing something other countries could emulate to bring their warming trends down.

After several weeks work, I am convinced climate change is real. The simplest way to explain it is the planet is getting warmer in general, but certainly not at the same rate everywhere. Just looking at the temperatures does not give any answer to the question of whether mankind's actions have any effect on the increase we are seeing; that takes modeling and modeling such a complex system has to be inexact, even on the incredibly powerful computers we have in the 21st Century. But if there is a man-made cause for temperatures rising slower in the United States than everywhere else, it would be in our best interest financially and environmentally to export that cause to the rest of the world.

U.S. vs. the Rest of the World: Climate change as measured from the 1975-1988 to 1988-1999 eras

Yesterday, we looked at the eras 1955-1975 compared to 1975-1988. Moving forward, now we look at 1975-1988 compared to 1988-1999.

In the United States, the warming trend increased quite a bit compared to the earlier era differences. 80% of weather stations that reported every season showed a warming trend and the average increase was 0.3° C compared to 0.09° C, and this increase takes place over a shorter period of time.

Here are the numbers of the U.S. vs, the rest of the world.

Total stations: 
U.S.A.: 3534
Rest of world 3046

Warming stations vs. cooling stations
U.S.A.: 80.4% warming, 19.6% cooling
Rest of world: 86.2% warming, 13.8% cooling

Average temperature change:
U.S.A.: 0.30° C
Rest of world: 0.47° C


These changes are much more extreme than similar comparisons between the earlier eras reported yesterday. Climate scientists consider about two degrees Celsius in a century to be catastrophic warming. Since this is a twenty five year time span, the United States rate stretched to over a century would not be alarming, but the rest of the world would be.


Tomorrow, the 1988-1999 era compared to 1999-2010 era, a time when some global warming skeptics say the earth began cooling.