By Cheryl Dorschner Article published November 5, 2003
Students at Allenbrook Elementary School in Williston were surprised last month when the faded United States map painted long ago on the concrete patio at the school’s entrance was refurbished in eye-popping pink, yellow, green and orange. Strong opinions about the color choice clattered in the halls and at recess, but few seem to have thought about the placement or the number of those colors.
“I like it repainted,” said Adam Kaminsky, 9, of Williston. “It would be cool if they painted every state a different color.”
His friend Chandler Jacobson, a third-grader who also lives in Willison, disagreed. “They’re just a little bit ugly. I’d keep orange and change the blue to dark blue and add purple,” he said, “Three colors would be enough.”
But three colors are not enough.
And it took mathematicians until 1976 to prove it.
Puzzle as fundamental problem
A story often told: it was 1852 when a mathematics student Francis Guthrie noticed that the counties of England could be colored with just four colors yet all adjacent counties were done in different colors. He asked his professor, Augustus De Morgan, whether four colors were enough for every map — real or imagined.
This “quaternion of colors” was widely treated as a simple puzzle, but in time mathematicians realized it was a fundamental problem.
“It was thought to be easy, but had several false proofs that stood for a decade,” says Dan Archdeacon, a professor of mathematics and statistics. “Finally solved in 1976, this was the first proof that used computer analysis — and that was controversial because mathematical purists wanted to be able to check the details. But that couldn’t be done in one lifetime.”
Archdeacon will discuss the controversy and history of this “quaternion of colors” in his University Scholar Seminar: “A Tale of Crayons and Their Consequences: Why Four Colors Suffice,” at 4 p.m. on Nov. 12 in Memorial Lounge, Waterman Building. The public is welcome to this lecture, which is sponsored by the Graduate College. Refreshments will be served after the presentation.
Multi-dimensional mathematician
Archdeacon teaches in the Department of Mathematics and Statistics. He is this year’s University Scholar in the area of basic and applied sciences. The University Scholar Awards Program annually recognizes faculty for sustained excellence in research and scholarly work. Scholars are nominated by their colleagues and chosen by a panel of faculty.
Solving mathematical problems through graphs on surfaces — topographical graph theory — is Archdeacon’s research specialty. Archdeacon draws graphs on planes, such as the four-color maps in this classic problem, and on three-dimensional shapes such as a cube and torus (that’s math-talk for a doughnut).
Of course, he doesn’t stop there. Shapes that turn improbably upon themselves, such as Moebius strips and Klein bottles are his forté. “Four dimensions — don’t scare me at all,” he smiles. “And five or six dimensions are interesting.”
Sitting in his office where books share shelf space with mathematical shapes and puzzles posing as sculpture, he calls up a few pages of solutions on the computer in his office to show a visitor his work. Pages of dot-connected diamond matrices interspersed by mathematical sentences scroll by. Archdeacon is wearing a shirt with repeating geometric shapes in four colors. He jumps up and scrawls the numbers 1-16 in a 4x4 table to explain a point. He erases the numbers and sits down. He goes back to try again.
Resolutely understated, he says his research is simply “problems in geometry and drawing pretty pictures.” His record shows more to it. Archdeacon has published widely in the mathematical fields of graph theory, combinatorics and theoretical computer science. He frequently is a guest speaker at national and international meetings. For the past four years he has been the managing editor for the Journal of Graph Theory, the leading professional publication in the field. The breadth of Archdeacon’s mathematical knowledge is wide — he has taught more than 30 different courses. And like “A Tale of Crayons,” his course syllabi would lure even the mathphobic. Topics in his courses include: poker-hand probability, a lecture on an Ann Landers column and answering the question “what color is my hat?”
“My research does tend to look like doodling,” he says, looking apologetic. In fact, it looks more like a game of dominoes with the blacks and whites reversed and the dots tied with black thread.
He tells a tale on himself.
“Once on a nine-hour flight, instead of sleeping, I started working on a problem. I spent a solid eight hours drawing graphs on a Moebius strip,” he recalls. “When we landed the person next to me leaned over and said, ‘What were you doing all that time?’ I answered, ‘Math.’ The passenger replied, ‘I thought that might be math.’”
