The Four Color Theorem might seem simple: Any map can be colored using four colors without bordering countries sharing the same color. However, Jeremy Tyson, professor of mathematics and director of the Illinois Geometry Lab, said it’s not as straightforward as it seems.
“The Four Color Theorem was a long-standing problem in mathematics,” Tyson said. In fact, it took over a century — and two Illinois mathematicians — to prove the theorem, originally posed by Francis Guthrie, a South African mathematician, in 1852.
That’s why in early November, the Illinois Mathematics Department held a Four Color Fest to honor both the historical and mathematical significance of the theorem.
Guthrie wondered if only four colors could be used on a map to distinguish different states and boundaries, without the same colors appearing directly next to each other. In 1976, Illinois mathematicians Wolfgang Haken and the late Kenneth Appel, answered his question with their proof of the Four Color Theorem.
“It’s of interest because it was such a long standing problem within the field,” Tyson said. “It spurred a lot of interest and development of areas of mathematics just from people working on the problem. There were false proofs in the past and errors were found. Finding those errors spurred new areas of mathematics.”
Tyson, who led the planning of the Four Color Fest, said the event fell in line with the 150th anniversary of the University of Illinois and the 40th anniversary of the theorem’s publication in the Illinois Journal of Mathematics in 1977. Wolfgang Haken is expected to attend some events along with two of his sons who teach at Illinois and will participate in the festivities. The son of Kenneth Appel will also participate in the event honoring the famous proof.
“The proof was rather unique among mathematical proofs of the time. This was the first proof that made essential use of computers,” Tyson said. “Back then that was a very new approach to mathematics — one could say almost controversial. There were questions partly because it wasn’t something people could check by hand. They would have to trust the computer.”
With help from computer technology, Appel and Haken developed a proof for the conjecture that four is the smallest number of colors required to color the regions of an arbitrary map in such a manner that any two adjacent countries are painted with different colors.
As a result, the Appel-Haken Four Color Theorem is a landmark in geometry, graph and network theory, and computer science.
The fest honored these achievements Nov. 2-4 through a series of lectures and events sponsored by the Departments of Mathematics, Statistics, and Electrical and Computer Engineering, the Center for Advanced Study, and the School of Music.
Robin Wilson, president of the British Society for the History of Mathematics, and the author of "Four Colours Suffice: How the Map Problem Was Solved,” kicked off the event with a lecture surveying the theorem as well as the University of Illinois’ role in finding the solution.
“I read the book myself when I was younger,” Tyson said. "It's a wonderful introduction to the Four Color Theorem for a general audience. Over the course of his career, Professor Wilson has done a lot of work on the history of mathematics."
Another lecture was presented by Andrew Appel, son of Kenneth Appel and the Eugene Higgins Professor of Computer Science at Princeton University, about how ideas and algorithms which came out of the computer-assisted proof of the Four Color Theorem have been used in the study of other problems in machine proofs and computer science.
Aside from these two lectures, the Illinois Geometry Lab hosted an open house with Four Color Theorem-related activities for K-12 students and the community. Tyson said the open house was extremely interactive, with various activities available for participants, such as map coloring, as well as lessons explaining some of the ideas and concepts in Appel and Haken's proof.
To end the celebration, a “Concert: A Portrait in Four Colors” took place in the Music Building. The featured instrument of the evening was the Haken Continuum, invented by Lippold Haken, Wolfgang Haken’s son and a lecturer of electrical and computer engineering at Illinois. The piece was composed specifically for the event by Rudolf Haken, another son of Wolfgang Haken and a professor of viola at the University of Illinois, in the School of Music. He was one of the performers in the concert.
“I’m excited to share a compelling story about something the department produced, maybe one of the signature results that came out of the department,” Tyson said. “This is definitely something people are aware of when they think of Illinois and mathematics.”