Wolfgang Haken, 1928–2022

Introduction

Figure 1.

In the fall of 1947, when Wolfgang Haken was a 19-year-old undergraduate at the University of Kiel, he took an introductory topology course from Karl-Heinrich Weise. In this course, Weise mentioned a number of famous open problems in topology, including the Unknotting Problem, the Four Color Problem, and the Poincaré Conjecture. Haken spent his entire career working on these three problems and their ramifications; he solved the first two, and, in the case of the first, showed that the techniques he had developed for the solution could be applied far beyond the original problem.

The section by Marc Lackenby and Peter Shalen describes Haken’s approach to the Unknotting Problem through his theory of normal surfaces, and the far more general results which he obtained using this theory and his closely related theory of hierarchies. This section also gives an indication of the very diverse ways in which other researchers have exploited these theories, both in $3$-manifold theory and in geometric group theory. The section by Robin Wilson recounts the fascinating saga of the successful attack on the Four Color Problem by Kenneth Appel and Wolfgang Haken, which was groundbreaking in its extensive involvement of computers.

In contrast to his spectacular successes with the Unknotting Problem and the Four Color Problem, Haken’s huge efforts in connection with the Poincaré Conjecture did not yield a proof. However, as Lackenby and Shalen point out, in the years following Grigori Perelman’s proof of William Thurston’s Geometrization Conjecture—of which the Poincaré Conjecture is a special case—a number of the most striking consequences of Perelman’s work involved normal surfaces and hierarchies. This is a further illustration of the enormous influence that Haken’s ideas have had on $3$-manifold theory.

Haken’s distinctive approach to mathematical research was described by one of his colleagues at the University of Illinois Urbana-Champaign:

Mathematicians usually know when they have gotten too deep into the forest to proceed any further. That is the time Haken takes out his penknife and cuts down the trees one at a time.

Given Haken’s magnificent output, it appears that this could be a very effective approach. Of course, in order to succeed with this approach, one had to be Wolfgang Haken.

Those of us who knew Haken remember him as a wonderfully kind and generous person with a delightful low-key sense of humor. These traits come through in Patrick Callahan’s section about his days as a PhD student under Haken’s direction. Ilya Kapovich’s biographical section gives insight into the obstacles that Haken had to overcome on the way to his phenomenal mathematical successes, and into a family legacy that is as impressive as his mathematical legacy.

Wolfgang Haken’s Life

By Ilya Kapovich

Wolfgang⁠¹ Haken⁠² was born in Berlin on June 21, 1928. His father was a physicist working for the German Patent Office and his mother stayed home to take care of the family and household. His two older brothers died of scarlet fever in 1927, and Wolfgang grew up as an only child. During his childhood in Berlin, Wolfgang developed an early interest in mathematics. At the age of 4, he made what he thought was his first important mathematical discovery: that counting should start with $0$ rather than with $1$, and that $0$ is the first natural number. He tried to convince his father to patent this fact but did not succeed at the time. Wolfgang’s mother died in August 1939, several days before the start of World War II, and the family remained in Berlin for most of the war. In 1944, at the age of 15, Wolfgang was drafted to serve in an anti-aircraft battery. He was soon transferred from Berlin to Dessau and from there to Soest, where he remained until the end of the war. After the war, Wolfgang first worked as a farmhand, and passed a high school GED exam in 1946.

¹

With gracious permission from the University of Illinois, this section incorporates substantial portions of the article by Ilya Kapovich, “Wolfgang Haken: a biographical sketch,” Illinois J. Math. 60 (2016), no. 1, iii–ix.

✖

²

Born Wolfgang Rudolf Günther Haken. He dropped his middle names and changed his legal name to just “Wolfgang Haken” in 1976, when he became a US citizen.

✖

In the summer of 1946, he started his undergraduate studies at the University of Kiel. At the age of 17, Haken was the youngest student at Kiel, as the universities in Germany then had a rule not to admit anyone under the age of 23. Initially, Haken wanted to become a physicist but his interests gradually changed to mathematics. At the time, Kiel had only two mathematics faculty members: a professor of mathematics and a professor of geometry, which were regarded as different subjects when the university was founded in the 17th century. The professor of mathematics at Kiel was Karl-Heinrich Weise; most of Haken’s mathematics classes were taught by Weise. In the Fall of 1947, while Haken was still an undergraduate, he attended a topology course by Weise. In this course, Weise stated several famous open problems in topology, including the Poincaré Conjecture, the Four Color Problem, and the Unknotting Problem. This experience marked the start of Haken’s interest in topology. Remarkably, as was mentioned in the Introduction, of the three major mathematical problems that motivated Haken’s interest in topology, Haken eventually solved two—the Unknotting Problem and the Four Color Problem.

Haken received a pre-diploma (roughly equivalent to the Bachelor of Science degree) in physics and mathematics at Kiel in 1948. He then started his doctoral studies in mathematics at Kiel, with Weise as his thesis advisor. Haken obtained his doctorate from Kiel in 1953, with the dissertation entitled “Ein topologischer Satz über die Einbettung $(d-1)$-dimensionaler Mannigfaltigkeiten in $d$-dimensionale Mannigfaltigkeiten.”

Haken met his future wife, Anna-Irmgard Freiin von Bredow, at Kiel in 1950 where she was also studying mathematics as an undergraduate. They were married in 1953. In 1959, Anna-Irmgard also received a doctorate in mathematics with Weise as her advisor.

After getting his doctorate, Haken obtained a job at Siemens in Munich as an electrical engineer, where he worked on designing microwave devices until 1962. The first three of Wolfgang and Anna-Irmgard’s six children were born during this period: Armin in 1957, Dorothea in 1959, and Lippold in 1961.

In 1956, Haken sustained a near-fatal accident while mountain climbing in the German Alps. He fell more than 30 feet and remained in a coma for several days. The accident significantly damaged Wolfgang’s foot but did not dampen his enthusiasm for the outdoors.

While at Munich, Haken continued doing mathematical research in combinatorial topology. He solved the long-standing Unknotting Problem by producing an algorithm for deciding whether a knot diagram represents the trivial knot. The solution of the Unknotting Problem got Haken’s work noticed by several mathematicians in the United States. Ralph Fox, a topologist at Princeton, had his graduate students go over Haken’s proof in detail, and, somewhat to Fox’s surprise, they found the proof to be correct.

Bill Boone, a group theorist at the University of Illinois at Urbana-Champaign (UIUC), also became intrigued by Haken’s paper. At the time, Boone was working on topics related to the unsolvability of the word problem for finitely presented groups, and he understood that there were close connections between algorithmic problems in group theory and algorithmic problems in low-dimensional topology. Since by then it was known that the word problem for finitely presented groups is, in general, undecidable, Boone expected the Unknotting Problem to be undecidable as well. Therefore Haken’s proof came as a considerable surprise to him. Just six weeks after the publication of Haken’s 1961 paper Hak61b on the Unknotting Problem in Acta Mathematica, Boone invited Haken to come to UIUC for a year.

Haken came to Urbana-Champaign with his family in 1962 and spent the 1962–1963 academic year at UIUC as a visiting professor. When preparing for his year at UIUC, Mahlon Day, who was the Mathematics Department Head, suggested that Haken obtain a US immigrant visa (which was relatively simple to do at the time). Haken followed this advice, which made it easier for him to eventually settle permanently in the US. During his year at Illinois, Haken applied for and obtained a temporary membership at the Institute for Advanced Study at Princeton. He spent two years, 1963–1965, at Princeton. In 1965, Haken joined the faculty at the Department of Mathematics at UIUC as a tenured professor. The last three children of Wolfgang and Anna-Irmgard were born in the US: Agnes in 1964, Rudolf in 1965, and Armgard in 1968.

In Haken’s paper Hak61b and his later papers Hak61aHak62Hak68 he went far beyond the Unknotting Problem, making huge inroads into the more general Equivalence Problem for knots, and the essentially still more general Homeomorphism Problem for 3-manifolds. In doing so he introduced the concepts of normal surface, incompressible surface, and hierarchy. All these terms will be explained in the next section, on knots and 3-manifolds, where an account of the enormous influence of these concepts—extending even far beyond Haken’s original applications of them—will be given. It will be seen that these concepts, and Haken’s work in this area, are still bearing fruit today.

In the late 1960s, Haken began to work on the Four Color Problem, which had fascinated him ever since the 1947 topology course by Weise and a subsequent 1948 lecture at Kiel by Heinrich Heesch. In 1976, Haken and Kenneth Appel (who was also a professor at UIUC then) proved the Four Color Theorem. Their proof included a substantial computer-aided component and marked the first time that a major mathematical result of this level of importance was solved with the help of a computer.

After an announcement in the Bulletin of the AMS in 1976 AH76a, the proof was published in 1977 in the Illinois Journal of Mathematics AH77AHK77.

Inevitably, the proof generated much discussion and controversy in the mathematical community. In retrospect, the proof was to a large extent responsible for the birth of computational and experimental mathematics as significant directions in modern mathematical research.

Shortly after Appel and Haken announced their proof in 1976, the UIUC Department of Mathematics put the phrase “Four Colors Suffice” on its official postmark, which remained in use until the mid-1990s: see Figure 2.

Figure 2.

The “Four Colors Suffice” postmark used by the UIUC Department of Mathematics after the Appel–Haken proof.

Wolfgang Haken delivered an invited address at the International Congress of Mathematicians in Helsinki in 1978. In 1979, Haken and Appel shared the Fulkerson Prize from the American Mathematical Society for their solution of the Four Color Problem.

Haken remained a professor in the UIUC Department of Mathematics until his retirement in 1998. He was also a member of the University of Illinois Center for Advanced Study from 1993 to 1998. While at UIUC, Haken was a thesis advisor for seven PhD students: Richard Rempel (1973), Thomas Osgood (1973), Mark Dugopolski (1977), Howard Burkom (1978), Robert Fry (1979), Patrick Callahan (1994), and Scott Brown (1995).

The “Saturday hike” is a delightful UIUC tradition going back to 1909 and having a long association with the mathematics department; the hike was for many years led by the late Joseph Leo Doob. From the 1960s through the rest of his life, Wolfgang Haken was a constant participant in the Saturday hike, as were many other members of the Haken clan. Wolfgang’s wife Anna-Irmgard was an informal leader of the hike from 1993 to 2005, and continued to come to the hike in subsequent years, while her health allowed. Anna-Irmgard, the beloved matriarch of the Haken clan, passed away on April 4, 2017.

In retirement, much of Wolfgang’s scientific interests concerned thinking about fundamental problems in cosmology. He also remained keenly interested in low-dimensional topology and was extremely pleased to see the tremendous progress in the field, including Grigori Perelman’s proof of the Poincaré Conjecture and the proof of the Virtual Haken Conjecture by Ian Agol and Daniel Wise. In 2016, the Illinois Journal of Mathematics published a special Haken volume honoring Haken’s mathematical contributions and influence. In November 2017, the UIUC Mathematics Department hosted a Four Color Fest to celebrate the 40th anniversary of the proof of the Four Color Theorem by Appel and Haken.

Three of Wolfgang Haken’s six children live in the Urbana-Champaign area. Rudolf Haken, a renowned musician and a composer, is a professor of viola in the UIUC School of Music. Lippold Haken designs electronic musical instruments and equipment and owns a company manufacturing a unique “Continuum Fingerboard.” He is also retired from the position of teaching professor in the Department of Electrical and Computer Engineering at UIUC, where he conducted research related to sound. Armgard Haken received BS and MS degrees in biology from UIUC, and is currently a research coordinator at the Midwest Big Data Innovation Hub, housed within the National Center for Supercomputing Applications at UIUC.

Haken’s eldest son, Armin, obtained a PhD degree in mathematics from UIUC in 1984, specializing in complexity theory and problems related to theoretical computer science. He is now a retired software engineer in San Francisco. Dorothea Blostein, née Haken, received a PhD degree in computer science from UIUC in 1987 and is currently a professor in the School of Computing at Queen’s University in Kingston, Ontario. Agnes Debrunner, née Haken, received a BS degree in animal science from UIUC. She is a leader in the US underwater hockey community and lives near Denver, Colorado. In addition to their six children, Wolfgang and Anna-Irmgard had 13 grandchildren, and the Haken clan continues to grow.

Wolfgang Haken passed away on October 2, 2022, at the age of 94, in Champaign, Illinois, surrounded by his family.

Ilya Kapovich is a professor of mathematics at Hunter College of CUNY. His email address is ik535@hunter.cuny.edu.

Knots and 3-Manifolds

By Marc Lackenby and Peter Shalen

Haken’s first major mathematical achievement was the solution to the Unknotting Problem, which appeared in his 1961 paper Hak61b. The problem had first been raised by Dehn in 1910, and was one of the most fundamental questions in knot theory.

Knots are just simple closed curves smoothly embedded in 3-dimensional space. A knot is usually represented by means of a diagram, which is a generic projection to a plane, with over/under information given at each crossing. In the Unknotting Problem, one is given a diagram of a knot, and the challenge is to determine whether it is the trivial knot, in other words whether it can be deformed, without crossing through itself, into a round circle. What is required is an algorithm that can provide a completely reliable answer.

Since the work of Alan Turing in the 1930s, it had been known that there are some problems that admit no algorithmic solution. Indeed, in his final published paper in 1954, Turing wrote “No systematic method is yet known by which one can tell whether two knots are the same.” Although Turing did not explicitly say this, it was clear that he was raising the possibility that this problem might not be solvable. After some experimentation, it quickly becomes clear that the Unknotting Problem is certainly not straightforward, as it is possible to produce diagrams of the trivial knot that admit no immediate simplification. An example, due to Haken (with a small correction due to Ian Agol), is given in Figure 3.

Figure 3.

A trivial(!) knot.

A round circle in 3-space is the boundary of a disk. Indeed, this is a characterization of the trivial knot. For if one were to deform the round circle without passing through itself forming a knot $K$, then one could at the same time deform the disk. Thus any trivial knot forms the boundary of a smoothly embedded disk in 3-space. Conversely, if a knot $K$ bounds a smoothly embedded disk, then one can deform the knot within this disk until it is a nearly-round curve that is visibly unknotted. The challenge, therefore, is to decide whether a given knot in 3-space bounds a smoothly embedded disk. This is called a spanning disk.

Normal surfaces

It is technically convenient to consider the given knot $K$ not as lying in $\mathbb{R}^3$, but in its one-point compactification, the 3-sphere $S^3$. The reason why this is helpful is that if we thicken $K$ to form an open solid torus $N(K)$, then the space $S^3 \setminus N(K)$, which is called the exterior of the knot $K$, is compact. The exterior is a 3-manifold with boundary⁠³, which means that it is locally modeled on the closed upper-half space $\mathbb{R}^3_+$. If $K$ is a trivial knot, a spanning disk for $K$ can be chosen so that it intersects the exterior $M$ of $K$ in an “essential” disk $D$. To say that $D$ is essential means that it is properly embedded in the sense that $D\cap \partial M=\partial D$, and is not boundary-parallel—i.e., is not obtained from a disk in $\partial M$ by pushing the interior of the disk into the interior of $M$. The Unknotting Problem is then reduced to determining whether the exterior of a knot contains an essential disk.

³

The manifolds we consider will in fact be smooth or piecewise linear, as will their submanifolds. In three dimensions, the transition between smooth and piecewise linear structures on a manifold is well-understood and elementary, and contains no surprises.

✖

Haken’s approach to this problem used the notion of a “normal surface.” Normal surfaces had already appeared in the work of Kneser in the 1930s to prove results about spheres in 3-manifolds, but Haken developed a systematic theory of such surfaces and recognized their huge power as a tool for addressing algorithmic questions.

The context for normal surface theory is a triangulation of a given $3$-manifold $M$ (with boundary), which is just a description of $M$ as a collection of tetrahedra with some of their faces glued in pairs. A triangulation of the exterior of a knot $K$ can easily be built from a given diagram of $K$. If a compact $3$-manifold with boundary contains an essential disk, one can consider how such a disk intersects the tetrahedra of the triangulation. By suitably modifying the disk, one can always arrange that it intersects each tetrahedron in a collection of triangles and quadrilaterals, as shown in Figure 4. A properly embedded surface which meets the tetrahedra in this way is said to be normal. (In fact, Haken used an alternative formulation of normal surface theory, using handle structures rather than triangulations, but we will focus on the triangulated version here.)

Figure 4.

Components of intersection of a normal surface with a tetrahedron.

Thus, the Unknotting Problem reduces to the question of whether the exterior of $K$ contains an essential disk which is a normal surface. This does not immediately solve the problem, as there may well be infinitely many normal surfaces in a given triangulation. However, Haken was able to show that one only needs to check a finite list of possible normal surfaces. His method was to encode a normal surface by combinatorial data in the following way. In each tetrahedron, there are four possible types of normal triangles and three types of normal quadrilaterals. Thus, if there are $t$ tetrahedra, then a normal surface $S$ determines a vector $(S)$ whose entries are $7t$ non-negative integers, called coordinates, that count the number of triangles and quadrilaterals of each type; the vector $(S)$ determines the surface $S$ up to a harmless equivalence relation. Haken observed that $(S)$ satisfies some simple restrictions. One restriction is that, within each tetrahedron, there can be at most one type of quadrilateral, as otherwise the surface could not be embedded. Thus there are $3^t$ possibilities for the set of types of quadrilaterals that appear in a given surface. When one has fixed such a set, $2t$ of the coordinates are constrained to equal $0$. The other restriction is that when two tetrahedra are glued along a face $F$, then the requirement that the triangles and quadrilaterals in the adjacent tetrahedra patch together correctly along $F$ imposes three linear constraints on $(S)$. It turns out that these two sets of constraints are sufficient as well as necessary for an element of ${\mathbb{N}}^{7t}$ to be the vector of a normal surface. Thus the set $\mathfrak{X}$ consisting of all vectors of normal surfaces is a union of $3^t$ “cones” in ${\mathbb{N}}^{7t}$, each of which is defined by a system of linear equations with integer coefficients. In particular, if $S_1$ and $S_2$ are normal surfaces such that $(S_1)$ and $(S_2)$ lie in the same cone, we may define the sum $S$ of $S_1$ and $S_2$ by $(S) = (S_1) + (S_2)$.

From the description of $\mathfrak{X}$ as a finite union of cones, Haken deduced, by very general arguments about solutions to systems of integer linear equations, that $\mathfrak{X}$ contains a finite set of “fundamental” vectors such that every vector in $\mathfrak{X}$ is a non-negative integer linear combination of fundamental vectors. Furthermore, the fundamental vectors can be found algorithmically from the equations; the surfaces corresponding to fundamental vectors are also said to be fundamental. Using a topological interpretation of the sum of two surfaces, Haken was able to show that if some surface is an essential disk, then some fundamental surface is an essential disk. Thus, one can decide whether a knot is the trivial knot, by going through each of the fundamental surfaces and checking whether any of them is an essential disk.

This was a brilliant and elegant solution to the Unknotting Problem.

Incompressible surfaces, hierarchies, and the Homeomorphism Problem

After solving the Unknotting Problem in Hak61b, Haken went on to the more general problem, highlighted by Turing, of deciding whether two knots are equivalent, in the sense that one can be deformed into the other without crossing through itself. This Knot Equivalence Problem was a much greater challenge.

Just as a trivial knot bounds a spanning disk in $S^3$, a general knot $K$ always bounds a compact, connected, orientable surface in $S^3$, called a Seifert surface. Compact orientable surfaces are classified up to homeomorphism by two numerical invariants: their number of boundary components (which in this case is $1$) and their genus (which is their number of “handles”). Necessarily, when a knot is non-trivial, the genus of any of its Seifert surfaces is greater than zero.

Not all Seifert surfaces are interesting. For example, one can modify a given Seifert surface by adding a large number of handles in a tiny neighborhood of a point. In order to focus on surfaces that really reflect the topological structure of a given $3$-manifold (such as a knot exterior), Haken introduced the notion of an “incompressible surface.” A compressing disk for a properly embedded surface $S$ in a $3$-manifold $M$ is defined to be a disk $D$ contained in the interior of $M$ with $D \cap S = \partial D$, such that the boundary of $D$ is not “trivial” in the sense that it already bounds a disk in $S$. The significance of this notion is that a compressing disk for $S$ can be used to modify $S$ by the operation shown in Figure 5 below, called a compression, which will produce a surface that is “simpler” than $S$ in a useful sense.

Figure 5.

A compression.

For example, if $S$ is connected and has connected boundary, like the surfaces in a knot exterior arising from Seifert surfaces, a surface obtained from $S$ by a compression will have a component having the same boundary as $S$ but having smaller genus.

We may define an incompressible surface in a compact, orientable $3$-manifold $M$ to be a properly embedded orientable $2$-manifold $S$ in $M$ which is not boundary-parallel, is not a $2$-sphere bounding a ball, and has no compressing disks. For example, if for a given knot $K$ we choose a Seifert surface $F$ whose genus is minimal among all Seifert surfaces for $K$, the properly embedded surface in the exterior of $K$ that arises from $F$ will be incompressible. This minimal genus is classically called the genus of $K$.

Any incompressible surface can be isotoped (i.e., deformed through a continuous family of embedded surfaces) to a normal surface. Using this fact, it is possible to use Haken’s method of fundamental normal surfaces to find the genus of a knot algorithmically. However, this does not solve the Knot Equivalence Problem, because there are infinitely many inequivalent knots of any given positive genus.

Haken dealt with this issue by introducing a completely new idea in Hak62: the notion of a “hierarchy.” Suppose that one starts with a 3-manifold with boundary $M_1$, for example the exterior of a given knot. One provides an incompressible surface $S_1$ in $M_1$. Then one removes an open regular neighborhood of $S_1$ from $M_1$, forming a new 3-manifold with boundary, called $M_2$ say. Then in $M_2$, one finds a new properly embedded incompressible surface $S_2$, one removes an open regular neighborhood of that, and so on. If the process terminates, in the sense that for some $n$ the 3-manifold $M_n$ is a disjoint union of 3-balls, then the manifolds $M_1,\ldots ,M_n$ are said to constitute a hierarchy for $M_1$.

Haken proved, making strong use of normal surface theory, that every knot exterior has a hierarchy; one can take the surface $S_1$ to be the incompressible surface that arises from a minimal-genus Seifert surface. But what he proved is far more general: a compact, orientable $3$-manifold $M$ with non-empty boundary always admits a hierarchy, provided that $M$ is irreducible, in the sense that it is connected and that every $2$-sphere in $M$ bounds a $3$-ball. Every knot exterior is irreducible. What is even more important is that, thanks to a result known as the prime decomposition theorem Hem04⁠⁴, most questions about arbitrary compact, orientable $3$-manifolds can be reduced to the special case of irreducible manifolds, so that irreducibility is not a serious restriction. (The prime decomposition theorem is often attributed to Kneser and Milnor, but Milnor’s part had been done independently by Haken in his paper Hak61a.)

⁴

To keep the number of references under control, and to benefit non-expert readers who want to learn more, we will often cite texts and survey articles that contain references to the original papers.

✖

The version of Haken’s theorem on the existence of hierarchies that we have mentioned includes the hypothesis that the manifold $M$ has non-empty boundary. But if an irreducible, orientable $3$-manifold $M$ is closed, i.e., is compact and has no boundary, and if $M$ contains some (necessarily closed) incompressible surface, the theorem immediately implies that $M$ has a hierarchy.

The great thing about hierarchies is that they permit the use of inductive methods. One can view the manifolds further down the hierarchy as “simpler” than the original one, and one can often use our knowledge of the simpler manifolds to establish information about the original manifold. Haken’s theorem on the existence of hierarchies has turned out to be a tremendously powerful tool in $3$-manifold theory, as we shall explain in more detail later. For this reason, a compact, orientable, irreducible 3-manifold $M$ that satisfies the hypothesis of the theorem—that either $\partial M\ne \emptyset$, or $M$ is closed and contains an incompressible surface— is now called a Haken manifold, a term introduced by William Jaco. A sufficient condition for a closed irreducible manifold $M$ to be a Haken manifold is that its first betti number $\dim H_1(M;{\mathbb{Q}})$ be strictly positive.

Haken used hierarchies in Hak62 and Hak68 to provide a solution to the Homeomorphism Problem for Haken manifolds, and the very closely related Equivalence Problem for knots, with some exceptions. He was able to show that a Haken manifold can be recovered from information about the surfaces in a hierarchy and the way that they glue together. Thus, one can reformulate the Homeomorphism Problem, by asking whether the two given Haken manifolds admit hierarchies that use the same surfaces glued together in the same way. This is useful, since the translation into a question about surfaces permitted Haken to use the theory of normal surfaces that he developed for the Unknotting Problem.

By 1968, the only case of these problems with which Haken could not deal was the case of “fibered $3$-manifolds” or “fibered knots.” A $3$-manifold is said to be fibered if it can be obtained from a product $F\times [0,1]$, where $F$ is a $2$-manifold, by gluing $F\times \{0\}$ to $F\times \{1\}$ by some homeomorphism. Fibered manifolds can be thought of as Haken manifolds with particularly simple hierarchies; from a slightly fancier point of view, they are $3$-manifolds that admit locally trivial fibrations over a circle. A knot is fibered if its exterior is fibered. In the late 1970s, Geoffrey Hemion (see Lac22) succeeded in solving the Homeomorphism Problem for fibered manifolds, using quite different methods from Haken’s. This is a neat example of how two different approaches to a problem can perfectly complement each other.

Haken’s proof was both lengthy and delicate, and in many places, his argument was sketchy. Indeed, it was not until 2003 that Sergei Matveev gave a full account of Haken’s proof, filling in many of the details and dealing with some of the cases that Haken had omitted. (See Lac22.) While this was an important contribution, it confirmed the essential correctness of Haken’s work in this area, which constitutes a stunning achievement.

In the decades following Haken and Hemion’s solution to the Homeomorphism Problem for Haken manifolds, William Jaco, Hyam Rubinstein and others further illustrated the power of Haken’s methods by extending them to other kinds of $3$-manifolds. A particularly striking example, developed through the combined efforts of Rubinstein and Abigail Thompson, is an algorithm to determine whether a triangulated 3-manifold is homeomorphic to the 3-sphere. This is a long way from the theory of hierarchies that was developed by Haken, since the 3-sphere is known not to contain any closed embedded orientable incompressible surfaces. Thus, there is no obvious surface to place into normal form. Instead, Rubinstein and Thompson used “almost normal” surfaces, which are embedded surfaces that intersect each tetrahedron of the triangulation in a collection of triangles and quadrilaterals, except in exactly one tetrahedron, where exactly one piece is not a triangle or quadrilateral, but is an “octagon” in a suitable sense. They were able to show that the 3-sphere could be detected by searching for normal and almost normal spheres, and using Haken’s method of encoding normal surfaces by vectors satisfying linear constraints. For an account of these developments, with further references, see Lac22.

Normal surfaces and the fundamental group

Remarkably, while Haken was developing his ideas about incompressible and normal surfaces in the early and middle 1960s, other researchers, notably David Epstein and John Stallings, were working with incompressible surfaces from a radically different point of view. Rather than thinking about algorithms, which were the focus of Haken’s work, these researchers were concerned with the very classical question of the extent to which the algebraic invariants of a $3$-manifold determine its topological type. Their results depended strongly on work by Christos Papakyriakopoulos from the 1950s, which implies that a connected orientable incompressible surface $F$ in a connected orientable $3$-manifold $M$ is $\pi _1$-injective in the sense that the inclusion homomorphism from $\pi _1(F)$ to $\pi _1(M)$ is injective. This is a powerful tool for studying the way that the fundamental group of a $3$-manifold controls its topological structure. Perhaps the most celebrated result from this period is Stallings’s fibration theorem, which implies that a compact, orientable, irreducible $3$-manifold is fibered if and only if its fundamental group admits a homomorphism onto ${\mathbb{Z}}$ with a finitely generated kernel.

It was apparently Friedhelm Waldhausen who recognized the connection between these two very different strains of research involving incompressible surfaces. He exploited the connection to prove a series of extraordinary theorems, one of which implies—among other things—that two closed Haken manifolds are homeomorphic if their fundamental groups are isomorphic. Needless to say, his proofs involved a great many ingenious ideas, but it seems fair to say that the main tools that he used are the ingredients in the proof of the Stallings fibration theorem on the one hand, and Haken’s result on the existence of hierarchies on the other.

A good reference for these developments is Hem04.

The interaction between the existence of hierarchies and the $\pi _1$-injectivity of incompressible surfaces led to an explosion of work on the topological structure of Haken manifolds. The so-called characteristic submanifold theory was developed by Klaus Johannson Joh79 and, independently, by William Jaco and Peter Shalen JS79; the two approaches were quite different, but the use of hierarchies, and of the $\pi _1$-injectivity of incompressible surfaces, was ubiquitous in each. Rather than attempting to explain the characteristic submanifold theory here, we shall emphasize one by-product of the theory: if $M$ is a Haken manifold, which for simplicity we will take to be closed, then there is a canonical (possibly empty) system of incompressible tori in $M$, and the components of the submanifold obtained by splitting $M$ along these tori have nice properties.

Just how nice these “pieces” of $M$ are was later revealed by William Thurston’s geometrization theorem Mor84: the interior of each piece admits a geometric structure, locally modeled on a $3$-dimensional homogeneous space. There are several different homogeneous spaces that arise in this context; one is Euclidean $3$-space, and another is hyperbolic $3$-space, the non-Euclidean space discovered by Gauss, Bolyai and Lobachevski. Of the various classes of locally homogeneous manifolds, those modeled on hyperbolic spaces are by far the richest. Indeed, the deep part of Thurston’s result was a characterization of those Haken manifolds that admit a hyperbolic structure. And his proof of this revolutionary result, whose influence on $3$-manifold theory is still being felt, was an induction on the length of a hierarchy, in which the induction step makes crucial use of $\pi _1$-injectivity.

Whereas the use of hierarchies in the work that we have been describing followed the same basic pattern as their use in Waldhausen’s work, other developments in the late 20th century involved unexpected twists in the application of Haken’s ideas. David Gabai discovered a very surprising refinement of the notion of a hierarchy, called a sutured manifold hierarchy, which turned out to be the key to solving a number of previously intractable problems in $3$-manifold theory (see Sch90). William Floyd and Ulrich Oertel showed that much of normal surface theory can be reinterpreted in terms of geometric objects in a $3$-manifold called branched surfaces; their work elucidated the geometric meaning of normal surfaces. Oertel and Allen Hatcher, working in the context of branched surfaces, initiated the study of $2$-dimensional measured laminations in $3$-manifolds; these are generalizations of normal surfaces given by solutions of the normal surface equations in which the coordinates are real numbers rather than integers. John Morgan and Peter Shalen used incompressible measured laminations in their work on actions of $3$-manifold groups on real trees, which gave a new perspective on one of the main steps in Thurston’s geometrization theorem. (The expository article MS85 gives references for both the Floyd–Oertel paper and the Morgan–Shalen papers.)

Before Waldhausen’s work, it is unclear to what extent people whose work used incompressible surfaces from the perspective of algebraic topology were aware of the connection with Haken’s work. Haken himself seems to have been quite unaware of the connection. One of the authors of this section, Peter Shalen, was astonished when Haken told him that, before seeing Waldhausen’s paper, it had never occurred to him that incompressible surfaces might have anything to do with fundamental groups. Having first encountered Haken’s work through Waldhausen’s papers, Shalen’s own perspective was that incompressible surfaces were important precisely because of their connection with fundamental groups. After thinking it over, he realized that this difference in perspective is itself a reflection of the power and versatility of normal surface theory. Its role in the algorithmic side of $3$-manifold topology is very different from its role in the side of the subject involving algebraic invariants and geometric structures, and yet it is central to both.

Recent developments

Both aspects of the theory of normal surfaces and hierarchies have continued to flourish, although not in the way that might have been predicted. Three-manifold theory has taken quite unexpected directions because of a huge development in 2002–2003.

We have mentioned that Thurston’s proof of his geometrization theorem for Haken manifolds was based on an induction on the length of a hierarchy. Thurston conjectured an extension of his theorem to arbitrary compact $3$-manifolds, which includes the Poincaré Conjecture as a special case. (The Poincaré Conjecture, which asserts that every compact, simply connected $3$-manifold without boundary is homeomorphic to $S^3$, was one of the three problems that Haken was introduced to in Weise’s lecture. It remained one of the most significant unsolved problems in topology throughout the twentieth century, and in particular, it resisted Haken’s considerable efforts to prove it.) Grigori Perelman’s proof of this conjecture of Thurston’s was perhaps the most important breakthrough in the history of the subject. Perelman used radically different techniques from Thurston’s, based on work by Richard Hamilton (see Mor09), and his proof did not involve hierarchies or normal surfaces. However, far from rendering the ideas of hierarchies or normal surfaces obsolete, Perelman’s work opened vast new opportunities for exploiting these ideas of Haken’s.

A spectacular example of how the use of hierarchies interacts with geometrization was provided by the so-called virtual Haken conjecture and virtual fibering conjecture. These were established by Ian Agol as the culmination of a program developed by Daniel Wise, and building on work by Jeremy Kahn and Vladimir Markovic. (Agol’s paper Ago13 provides references to the relevant papers by Wise and Kahn-Markovic.) The virtual Haken conjecture, first hinted at by Waldhausen, asserts that every closed irreducible $3$-manifold with infinite fundamental group is finitely covered by a Haken manifold. The virtual fibering conjecture, first speculated about by Thurston (and so strong that it was once widely considered implausible), asserts that every hyperbolic $3$-manifold which is closed (or even has finite volume) is finitely covered by a fibered manifold. Wise’s program is very largely group-theoretical, and his and Agol’s results have major group-theoretical implications beyond $3$-manifold theory. The point to be stressed here is that a group-theoretical counterpart of the notion of a hierarchy is central to the program. Thus we see the ideas that Haken developed to study knots and $3$-manifolds bearing fruit in a wider context, as well as being central to the most remarkable recent developments in $3$-manifold theory.

Another remarkable interaction between Haken’s work and geometrization involves the Homeomorphism Problem. Gregory Kuperberg, using Perelman’s theorem as a starting point, has written down a completely general solution to the Homeomorphism Problem for $3$-manifolds, which he says is essentially due to Thurston and Robert Riley (both of whom assumed the geometrization conjecture). This solution does not involve normal surface theory. However, by combining geometrization with normal surface theory, Kuperberg has established a much stronger result: that the Homeomorphism Problem is solvable by an algorithm with execution time bounded by a tower of exponentials. (See Lac22 for an account of this work.) Thus we see Haken’s ideas being applied in ever stronger ways to the problems for which he first designed them.

Marc Lackenby is a professor of mathematics at the University of Oxford. His email address is lackenby@maths.ox.ac.uk.

Peter Shalen is a professor emeritus in the Department of Mathematics, Statistics, and Computer Science at the University of Illinois at Chicago. His email address is shalen@uic.edu.

The Four Color Theorem

By Robin Wilson

The Four Color Theorem states:

The regions of every plane map can be colored with just four colors so that neighboring regions receive different colors.

First posed as a problem by Francis Guthrie in 1852, it was not until 1976 that the theorem was proved, by Wolfgang Haken and Kenneth Appel of UIUC. Their proof was one of the earliest to make substantial use of a computer.

In 1879, it was shown that it is sufficient to consider cubic maps, where exactly three regions meet at each intersection. In the same year, Alfred Kempe claimed a proof that was widely accepted until a fatal flaw was exposed in 1890. Kempe’s paper, although incorrect, contained several ideas that would resurface in the eventual proof.

Over the next 50 years, it gradually became clear that the problem splits into two parts. In the following, a configuration of ring-size $k$ is a collection of regions surrounded by an external ring of $k$ regions: see Figure 6.

Figure 6.

A configuration with ring-size 14.

Unavoidable sets of configurations: Kempe proved that every cubic map must contain at least one region bounded by at most five edges: a digon, triangle, quadrilateral, or pentagon. Any set of configurations (such as these four) is unavoidable if every cubic map must contain at least one of them.

Reducible configurations: A configuration is reducible if any coloring of the surrounding ring can be extended to the interior regions, either directly or after interchanging pairs of colors (known as Kempe-interchanges). Note that no reducible configuration can appear in a minimal counterexample to the Four Color Theorem.

Kempe proved that digons, triangles, and quadrilaterals are reducible, but failed to do so for pentagons. In 1904, Paul Wernicke replaced the pentagon by two adjacent pentagons and a pentagon adjacent to a hexagon, giving a new unavoidable set, and this result was further extended by Philip Franklin in 1922, and by Henri Lebesgue (of Lebesgue integral fame) in 1940.

In 1913, George Birkhoff gave a systematic treatment of reducible configurations, showing that every set of configurations with ring-size up to $5$ (other than the pentagon) is reducible, and proving the reducibility of a particular configuration of four pentagons with ring-size $6$, known as the Birkhoff diamond: see Figure 7.

Figure 7.

The Birkhoff diamond.

Several mathematicians then built on these ideas, obtaining many reducible configurations. In particular, Franklin introduced new ones in a counting argument which proved that every cubic map with up to $25$ regions can be $4$-colored. By 1940, this number had increased to $35$.

Further details on, and references for, these early developments and those described below can be found in the author’s book Four Colors Suffice Wil14; the quotations by Haken and others are taken from an article by Donald MacKenzie Mac99 much of which was based on unpublished interviews that were conducted in 1994.

Enter Heesch and Haken

Much of this work was piecemeal, with attempts to find unavoidable sets and reducible configurations being largely independent of each other. It was not until the 1940s that Heinrich Heesch entered the fray. Heesch had contributed to the solution of the 18th of Hilbert’s celebrated problems, and around 1935 became interested in map coloring. He realized that to prove the Four Color Theorem, it was enough to find an unavoidable set of reducible configurations: every map must include at least one of them, but none can appear in a minimal counterexample.

In the late 1940s, Heesch lectured on his findings at the University of Kiel, and in 1948 one student who attended was Wolfgang Haken, who was studying mathematics, philosophy, and physics, and who had been aware of the Four Color Problem since hearing about it in Weise’s topology course. Haken later recalled Heesch’s lecture, much of which he did not understand at the time, and remembered Heesch’s claim that there might be some 10,000 cases to be investigated.

Over the next 20 years, Haken solved the Unknotting Problem, and moved to the University of Illinois Urbana-Champaign, where he did much of his fundamental work on the Equivalence Problem for knots and the Homeomorphism Problem for 3-manifolds. During this period he also spent much time on the Poincaré Conjecture. In 1966, unable to complete a proof of this conjecture, he began thinking about the Four Color Problem. He contacted Heesch, who was still working on the problem and had discovered thousands of reducible configurations.

Unavoidable sets were still rather scarce, and in order to produce them, Heesch invented his method of discharging (as it was later named by Haken). Here, to investigate whether certain configurations form an unavoidable set, he assumed the contrary. He then assigned a “charge” of $6-k$ to each $k$-sided region; it then follows from Euler’s polyhedron formula that the total charge over the whole map is positive. He next attempted to move these charges around the map in such a way that no charge was created or destroyed; this is called discharging the map. In many cases this could be done so that every region received a non-positive charge. This contradiction confirmed that the given configurations did indeed form an unavoidable set.

Heesch also contributed to the theory of reducible configurations, and defined a configuration to be $D$-reducible if every coloring of the surrounding ring can be extended to the interior regions (either directly or after Kempe-interchanges of colors), and to be $C$-reducible if this can be carried out after the configuration had been simplified in some appropriate way. His aim was to develop systematic methods for generating reducible configurations, looking at both $D$-reducible and $C$-reducible cases. If a configuration was not $D$-reducible, he frequently saw how to modify it so as to determine its $C$-reducibility, and in this way he could restrict his attention to a smaller number of possible colorings. Over the years he developed an uncanny knack of recognizing reducible configurations with at least 80 percent accuracy: as Haken remarked:

What fascinated me most was that Heesch looked at the configuration, and he said either “No, there is no chance: that cannot be reducible” or “But this one: that is certainly reducible.”

Haken invited Heesch to lecture at UIUC, and asked whether computers might help in the examination of large numbers of configurations. Heesch had already obtained the help of a mathematics graduate who developed a method for testing $D$-reducibility that was sufficiently routine to be implemented on a computer, even though this might take a long time.

The complexity of a configuration can be measured by its ring-size; for example, the Birkhoff diamond has ring-size $6$ and there are $31$ essentially different colorings of the surrounding regions to consider, but for configurations with ring-size $14$ there are nearly 200,000 colorings. Larger ring-sizes were way beyond the capacity of computers of the time.

Haken bid to the University of Illinois for time on a new supercomputer whose construction was nearing completion, but it was not yet ready for use. Eventually, they were referred to the Atomic Energy Commission’s Brookhaven laboratory in Long Island, where there was a Cray Control Data 6600 machine, the most powerful machine of its day, which could test configurations of up to ring-size $14$.

In 1970, Heesch sent Haken the results of a new discharging experiment which, if applied to a general map, would yield about $8900$ “bad” configurations extending up to ring-size $18$, in which some regions would still have positive charge. Haken, however, was pessimistic about dealing with so many configurations, especially since several were fairly large. For some time, he had felt that the complexity of the problem would be substantially simplified by better discharging methods. By restricting his attention to maps without hexagons or heptagons, he obtained a much simpler procedure and communicated his findings to Heesch; it is at this stage that Haken began to contribute to the eventual solution of the problem.

Impressed by Haken’s findings, Heesch invited Haken to collaborate with him, and in 1971 sent him three “obstacles” whose presence seemed to prevent configurations from being reducible—a $4$-legger region adjoining four consecutive regions of the surrounding ring, a $3$-legger articulation region adjoining three surrounding regions that are not all adjacent, and a hanging $5$-$5$ pair of adjacent pentagons that adjoin a single region inside the surrounding ring: see Figure 8.

Figure 8.

Heesch’s obstacles to reducibility.

But by now, Haken was changing his approach. Unlike everyone else whose objective seemed to be to collect reducible configurations by the hundreds before packaging them into an unavoidable set, Haken’s primary motivation was to aim directly for an unavoidable set. In order to avoid wasting expensive computer time checking configurations that would eventually be of no interest, this set was to contain only configurations that were likely to be reducible—in particular, they should contain none of the obstacles. Any configuration that subsequently proved not to be reducible could then be dealt with individually. As he later commented:

If you want to improve something, you should not improve that part which is already in good shape. The weakest point is always the one you should improve. This is a very simple answer to why we got it and not the others.

By this time, most workers on the Four Color Problem were using the “dual formulation” of coloring the vertices of the corresponding graph. In particular, Heesch devised a useful notation for representing regions by appropriate symbols so that they can be easily distinguished, such as • for pentagons, $\cdot$ for hexagons, $\circ$ for heptagons, and $\nabla$ for nonagons.

Enter Appel

With little knowledge of computing, Wolfgang Haken considered giving up the problem until more powerful machines had become available to deal with the massive calculations that would clearly be necessary. Informed that his ideas could not be programmed, he announced:

The computer experts have told me that it is not possible to go on like that. But right now I’m quitting. I consider this to be the point to which and not beyond one can go without a computer.

Attending this lecture was his colleague Kenneth Appel, a computer programmer with much practical experience. Afterward, Appel told Haken that he considered the experts’ view to be nonsense, and offered to work on implementing the discharging procedures. Haken was delighted to accept Appel’s offer, and they decided to concentrate their search on unavoidable sets, without taking time to check the configurations for reducibility; in particular, they focused on “geographically good configurations” that contain neither of Heesch’s first two obstacles, and would check for reducibility when an entire unavoidable set had been constructed.

Figure 9.

Wolfgang Haken and Kenneth Appel.

Their first exploratory computer runs provided much useful information, but the computer output was enormous, with some configurations appearing many times; they would clearly need to keep such duplications under control if the eventual list were to be manageable. Fortunately, the computer program had run in just a few hours, and so they could experiment as often as necessary. Any changes to the program were easily implemented and the paper stacks of outputs of later runs were much reduced in thickness; eventually they would come down to a fraction of an inch.

From then on, they continually modified the discharging algorithm or the computer program so that the program grew while the output shrank. This two-way dialog with the computer continued, as problems were sorted out and new ones arose. Within six months of experimenting and improving their procedures, they realized that their method for producing a finite unavoidable set of geographically good configurations in reasonable time was feasible.

In early 1975, they introduced the third of Heesch’s obstacles; this inevitably involved changes in procedure, but was carried out successfully with only a doubling in the size of the unavoidable set.

As soon as it seemed that they could probably find an obstacle-free unavoidable set of configurations which were likely to be reducible, they started the massive detailed check for reducibility. Inevitably, a few “rogue” reducible configurations would appear in the list, but their hope was that these would be relatively few in number.

In mid-1974, realizing that they needed help with the reducibility programs, they had enlisted the help of John Koch, a graduate student, to work on the $C$-reducibility of configurations. Appel and Haken were particularly interested in two types of modification that were relatively easy to implement, and Koch discovered that most of his configurations were fortunately of these types.

By early 1976, Haken and Appel could work on the final details of the discharging procedure. To do this, they sought “problem configurations” and immediately tested them for reducibility—this could usually be done fairly quickly. In the event, the final process involved $487$ discharging rules, requiring the investigation by hand of about 10,000 neighborhoods of regions with positive charge and the reducibility testing by computer of some $2000$ configurations. All configurations were of ring-size $14$ or less.

The last few months were extremely heavy on computer time, but Appel, Haken, and Koch were fortunate. Few institutions would have given them $1200$ hours on the computer, but the university’s computer center was very supportive, and in March 1976 a powerful new machine was bought by the university’s administrators. This proved to be so powerful that everything proceeded far more quickly than they had expected, saving them much time on the reducibility testing. Meanwhile, with the help of Haken’s daughter Dorothea, they spent months of exhausting and stressful effort working through the 2000 or so configurations that would eventually form the unavoidable set.

Figure 10.

Some of Haken and Appel’s configurations.

Suddenly by late June, almost before they realized what was happening, the entire job was finished: the Hakens had completed the construction of the unavoidable set. Within two days Appel tested the final configurations for reducibility, and celebrated their achievement by announcing on the department’s blackboard:

Modulo careful checking it appears that four colors suffice.

By this time, Haken and Appel knew that they were safe: even if a few configurations proved to be irreducible, there was more than enough self-correction in the system for them to be quickly replaced: no single faulty configuration could destroy the entire edifice. In fact, their system included so much self-correction that they effectively had many thousands of proofs of the Four Color Theorem, instead of just one!

Armed with this confidence, they went public. On July 22, 1976, they formally informed their colleagues and sent complete preprints to everyone in the field. One recipient was Bill Tutte, who waxed eloquent, comparing their achievement with the slaying of a fabled Norwegian sea monster:

Wolfgang Haken
Smote the Kraken
One! Two! Three! Four!
Quoth he: “The monster is no more.”

They quickly wrote short reports for the Bulletin of the American Mathematical Society AH76a and Discrete Mathematics AH76b, but decided to submit their full solution to the Illinois Journal of Mathematics, partly because they wanted it to appear locally, but mainly so that they could suggest suitable referees. By December they were able to refine the proof and prepare it for publication. The result substantially improved on the rough-and-ready preprint they had sent out in July: in particular, their preprint had contained duplications and configurations contained within others, and by eliminating these they reduced their original list of $1936$ reducible configurations to $1482$.

Their solution appeared in two parts in the December 1977 issue of the Illinois Journal. Part I AH77 on Discharging outlined the overall strategy of their proof, while Part II AHK77 on Reducibility, written with John Koch, listed the entire set and described the computer implementation. These were supplemented by microfiche containing 450 pages of further diagrams and detailed explanations.

Wolfgang Haken and Kenneth Appel had achieved their goal: the Four Color Theorem was proved.

Aftermath

The Appel–Haken proof was greeted with enthusiasm—a longstanding problem had at last been solved—but also with skepticism, great disappointment, or outright rejection. Their extensive use of computers was widely criticized, and raised philosophical questions as to whether a proof is valid if it cannot be checked by hand. At a Joint AMS-MAA Summer meeting in Toronto a lecture by Haken to a capacity audience received only polite applause, and when explaining their proof to mathematics departments, its authors were often made to feel unwelcome; in one case, they were even barred from meeting graduate students for having introduced totally inappropriate methods into mathematics. Since then, with the passage of time, the use of computers in mathematical proof has become more widespread.

Inevitably, there were typos in their paper, and also a minor error that needed two weeks for Haken to correct, but the proof emerged largely unscathed. Haken and Appel wrote several further papers on the subject, including one in 1986 in The Mathematical Intelligencer discussing such purported errors. In 1989, they followed this with a hefty tome AH89, published by the AMS, which was entitled Every Planar Map is Four Colorable. This gave further details and included a printed version of their earlier microfiche.

In 1994, Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas took a more systematic approach to the problem. Using essentially Appel and Haken’s method, they produced an unavoidable set of 633 configurations, reducing the number of discharging rules from 487 to just 32. Interestingly, they chose to use computers in both the unavoidability and reducibility parts of their proof, believing that such an approach was more reliable than hand calculation. Their proof could be externally verified on a home computer in just a few hours. Shortly after this, Robin Thomas wrote an article in the AMS Notices linking the Four Color Theorem to the divisibility of integers, the algebra of 3-dimensional vectors, and results on matrices and tensors.

Two further events are worthy of mention. Because $D$-reducible configurations are simpler to deal with than $C$-reducible ones, John P. Steinberger gave a proof in 2008 that was based on only the former; it involved 2832 configurations with ring-size up to 16 and used 42 discharging rules. Meanwhile, in 2004, the French computer scientist Georges Gonthier had provided a fully machine-checked proof of the theorem, which was a formal language implementation and machine verification of the approach of Robertson and his coworkers.

But for graph theorists this was by no means the end of the line, as the Four Color Theorem is just one special instance of some much harder problems; these include finding proofs for Hadwiger’s conjecture and the five-flow conjecture, and on these problems good progress has already been made. With these in mind, we leave our final poetic musings to Bill Tutte:

The Four Color Theorem is the tip of the iceberg, the thin end of the wedge, and the first cuckoo of Spring.

Robin Wilson is a professor emeritus in the Department of Mathematics at The Open University. His email address is robin.wilson@open.ac.uk.

Haken as Thesis Advisor

By Patrick Callahan

I was one of Haken’s last PhD students, completing my degree in 1994, a few years before his retirement.

When I started graduate school in mathematics in 1989, the University of Illinois Urbana-Champaign was (and still is) one of the largest graduate math programs in the United States. There were almost 300 graduate students in the mathematics department and almost one hundred of us were first-year students. With over 70 faculty members, finding a good advisor was an important step for all graduate students and UIUC offered many choices. I decided to meet one on one with every mathematics faculty who was involved in topology, algebra, or number theory. Two rules of thumb that were shared among students seeking advisors were: look for recent, successful graduates completing and finding positions and learn who their advisor was, and look for faculty that were currently active and well-networked in their field. Despite this, I ended up choosing Wolfgang Haken who had not had a graduate student in almost 20 years and had not published or participated in conferences in quite some time. Many people thought working with Haken would be a risky choice.

When I met with Haken he told me that he was very excited about the new developments in $3$-manifolds and knot theory but that he was not currently active in the field. However, he made me an interesting offer. He had recently been nominated as a member of the University of Illinois Center for Advanced Study, which included an annual travel stipend. He was not up for much travel, so he said he would be my advisor if he could send me to interesting topology meetings about which I would report back to him. This was an incredible arrangement that I gladly accepted. I was fortunate as a first-year graduate student to be able to travel and meet all the amazing researchers in the field. I was sent to meetings in Israel, France, and across the United States.

It was an exciting time for low-dimensional topology. Three-manifolds and knot theory had spawned a large active research community, which was often surprised when I introduced myself as Haken’s student since there had not been any such students in a good many years. But Haken’s work was foundational, and Haken manifolds were a critical player in the Geometrization Conjecture. I would return from these conferences and report to Haken what current progress was happening in the field. He would always pause for a long time and then say something like “Ja ja…that is most interesting,” then go silent again for another long pause and then tell me to continue recounting what I learned at the conference.

Haken was an atypical advisor. Although he had an office, we would rarely meet there. Rather, there were two somewhat unusual places he liked to work, and when I wanted to meet with him, I would go searching for him in those places. The first unusual location was in an empty classroom in the basement of Altgeld Hall, usually with the lights off. Many times he would not have any paper or anything with him. He would just be sitting in a dark basement in deep thought. The other unique location I would look for him was almost the opposite. He would often sit in the loud and crowded student union and be deep in thought surrounded by hordes of noisy students.

Although often taciturn, Haken would sometimes share anecdotes about his life and work. I recall him telling me that during World War II there was a paper shortage so he would take down propaganda posters and write on the back of them to do his research. He would talk about the controversies around the solution to the Four Color Theorem. Some mathematicians thought that the use of a computer could not be trusted or considered a valid proof. Even though 20 years had elapsed, Haken continued many correspondences regarding the Four Color Theorem. He would regularly get letters sent by professionals and amateurs alike claiming to have found some new clever proof. Haken would take the time to read all of them and send back careful and encouraging feedback. I remember him reading a handwritten letter claiming a new proof, around fifty pages long, for which he found an “unrepairable” error on the 48th page. I asked him why he still read all these letters and he replied, “If this person had made it a little further without an error they might have really discovered something. You never know.” Haken said that the field had a responsibility to read plausible claims carefully and not dismiss them just because the authors lacked the professional academic credentials.

Conversations with Haken had a slow pace. He would talk slowly and carefully and there were often long pauses. I once thought that this was because English was not his native language, but a German graduate student informed me that Haken was the same way when conversing in German. Haken was one of the most careful thinkers I have ever met. He paid prodigious attention to details. One of my fond memories regarding details was when I submitted my dissertation. I, perhaps pretentiously, thought it seemed like a good idea to start Chapter 1 with an epigraph in the original Greek from Aeschylus’ Agamemnon. I do not know classical Greek and had made an error when copying it. When Haken returned my draft, he had corrected the quote, in classical Greek.

I recently pulled out a copy of my dissertation. I found the acknowledgement:

I would like to thank my advisor, Professor Wolfgang Haken, for being the exact type of advisor I needed, and for his support and confidence in me.

I cannot speak to what it was like having Haken as an advisor in the 1970s in the heyday of the Four Color Theorem, but in the 1990s, Haken was indeed the exact type of advisor I needed. He was endlessly curious, and provided the means for me to see the world and be part of a vibrant community of researchers in low-dimensional topology. In some small sense I was his eyes and ears at this stage in his career. Haken was also very hands off in that he never gave me a specific problem to do nor did he tell me what I should work on. He didn’t even discourage me when I spent a year working on the Lens Space Conjecture, a special case of the Geometrization Conjecture which was then still open and was notorious for its difficulty. He always had an appetite for big unsolved problems. Haken was very patient and carefully critiqued my many unsuccessful attempts. He was in no hurry. He told me that being a mathematician is mostly about having ideas that fail over and over again, only rarely having one actually work. He encouraged me not to shy away from big problems and to keep looking at and thinking about things differently: to keep having ideas. That was just the advisor I needed.

Patrick Callahan is the CEO of Math ANEX and Callahan Consulting. His email address is callahan.web@gmail.com.