The Four Color Theorem was solved by Haken and Appel in 1976, with a proof that involved the use of computers. The current state of the argument along these lines can be found in work of Robertson, Sanders, Seymour, and Thomas. Many have found the Haken/Appel proof unsatisfying, largely because the use of computers makes it uninformative to people. While this aspect is considerably lessened in recent work, interest in a proof along different lines persists.

Howard Levi, at the end of a long and distinguished career in mathematics, spent the last years of his life working on a proof of the Four Color Theorem along algebraic lines. He died in 2002 with his proof unfinished. What he did establish was an interesting equivalent algebraic formulation of the problem, involving finite fields. Others have also produced algebraic reformulations of the problem, see the references below, but there are significant novelties in Howard's work to make it of independent interest.

- Yu. Matiyasevich. A criteria for colorability of vertices stated in terms of edge orientations (in Russian),
*Discrete Analysis*(Novosibirsk), 26, 1974, 65-71. - N. Alon, M. Tarsi. Coloring and orientations of graphs,
*Combinatorica*, 12, 1992, 125-134. - N. Alon. Combinatorial Nullstellensatz.
*Combinatorics, Probability and Computing*, 8, 1999, 7-29. - Yu. Matiyasevich. Some algebraic methods for calculation of the number of colorings of a graph (in Russian).
*Zapiski Nauchnykh Seminarov POMI*, 293, 2001, 193-205 (available via www.pdmi.ras.ru). - M. Mnuk, Representing graph properties by polynomial ideals. In V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, editors,
*Computer Algebra in Scientific Computing, CASC 2001. Proceedings of the Fourth International Workshop on Computer Algebra in Scientific Computing*, Konstanz, pages 431-444. Springer-Verlag, September 2001. - N. Alon. Discrete Mathematics: Methods and Challanges,
*Proceedings of ICM 2002*, vol. 1, 119-135 (available via http://front.math.ucdavis.edu/ICM2002).

Howard left notes and partially written papers that were somewhat chaotic. Paul Meyer and myself were friends of Howard of long standing, and we took it on ourselves to bring some order to this chaos. In this we were extensively assisted by Alan Hoffman, also an old friend of Howard, and especially by Don Coppersmith. We have produced the paper found here We acknowledge its imperfections---this is not our area. But we make it available as a tribute to our friend, relying on the search engines of the world to bring it to the attention of specialists, in the hope that it may be found of some use. Click here for the paper.

Here is a very brief sketch of Howard's life. He was born in the Bronx and graduated from DeWitt Clinton High School there. He received his AB (1937) and PhD (1941) from Columbia University. His PhD was in differential algebra, under Joseph Fels Ritt. After receiving his degree, he was a Research Scientist on the Manhattan Project during WW II. Following this he returned to Columbia as a faculty member, from 1943 to 1962. He then moved to Hunter College, and subsequently Lehman College, which began as Hunter in the Bronx and became a separate college of City University of New York in 1968. He remained on the faculty there until his retirement.

Howard was a friend of the cartoonist Crockett Johnson, who created the comic strip *Barnaby* and wrote the well-known children's book *Harold and the Puple Crayon*. Mr. Johnson enjoyed making geometric diagrams using matchsticks and formulating conjectures concerning them. One of them turned out to be deep and interesting, and eventually resulted in a research paper of Howard's. This is just one example of his breadth of interest, which also ranged over music and literature. He was an excellent pianist and organist, and had deep knowledge of Shakespeare and the English classics in general. At one time he taught the Great Books course for the English Department at Columbia.

Melvin Fitting

[Return to home page]