This book is dedicated to problems involving colored objects, and to results about existence of certain exciting and unexpected properties that occur regardless of how these objects (points in the plane, space, integers, real numbers, subsets, etc.) are colored. In mathematics these results comprise Ramsey Theory. The book will also include some problems that can be solved by inventing colorings, and results that prove the existence of certain colorings, most famous of the latter being, of course, The Four-Color Theorem.
Most books in the field present mathematics as a flower, dried out between the pages of an old dusty volume, so dry that colors are faded and only theorem-proof narrative survives. Along with my previous books, Mathematical Coloring Book will strive to become a live account of a live area. I hope the book will present mathematics as a human endeavor: the reader should expect to find in it not only results, but also portraits of their creators; not only mathematical facts, but also open problems; not only new mathematical research, but also new historical investigations; not only mathematical aspirations, but also moral dilemmas of the times between and during the two World Wars of the twentieth century. Indeed, new facts and artifacts will be presented that are related to the history of the Chromatic Number of the Plane problem, the early history of Ramsey Theory, life of Issai Schur, Pierre Joseph Henry Baudet and Bartel Leendert van der Waerden.
The author hopes the reader will join him on a journey he would not forget, a journey full of passion, where mathematics and history are learned in the process of solving mysteries more exciting than fiction, precisely because they are mysteries of real affairs of human history. Can mathematics be received by all senses, like a vibrant flower, indeed, like life itself? There is one way to find out, and it is to experience this book.
This book would give young active high school and college mathematicians the first accessible introduction to mathematics of coloring in general, and Ramsey Theory in particular. Mathematical professionals, who seem to think that they know everything, would be pleasantly surprised by the unpublished and unnoticed mathematical gems. Young and old mathematicians alike would welcome an opportunity to try their hand – or mind? – on numerous open problems, all easily understood and not at all easily solved.
If the interest of my colleagues at Princeton is any indication, every intelligent reader would welcome an engagement in solutions of historical mysteries, especially those related to WWII. Historians of mathematics would find much new information published and old errors corrected and published for the first time in this book. And everyone will experience seeing, for the first time, faces one has not seen before in print, on rare and unique photographs of the creators of mathematics presented herein, from Francis Guthrie to Frank Ramsey, and documents, such as the one where Adolph Hitler commits a “micromanagement” of firing the Jew, Issai Scur from his job of Professor of the University of Berlin.
I hope this will become a unique book, free from a straight jacket of a typical textbook, but it can be used as a text for a host of various courses, two of which I have personally given to senior and starting graduate students at the University of Colorado: What is Mathematics?, and Mathematical Coloring Course, both presenting a “laboratory” of a mathematician, a place where students learn mathematics and its history by doing them, and realizing in the process what mathematics is and what mathematicians do.
Various parts of this book-in-the-making have been the subject of a good number of talks, including keynote invited talks at Congresses of World Federation of National Mathematics Competitions in Zhong Shan, China (1998) and Melbourne, Australia (2002); a keynote invited talk at the International Conference on Mathematical Education of the Gifted in Rousse, Bulgaria (2003); in reports to International Congresses on Mathematical Education in Seville, Spain (1996) and Tokyo, Japan (2000); and in nearly annual presentations at the Southeastern International Conference on Combinatorics, Graph Theory, and Computing (1992-2003).
Moreover, this not-yet-written-book has been long listed in bibliographies of many articles and some fine books, such as Old and New Unsolved Problems in Plane Geometry and Number Theory, by Victor Klee and Stan Wagon (MAA, 1991, second printing) and Graph Coloring Problems, by Tommy R. Jensen and Bjarne Toft (John Wiley, 1995). As a good wine, this book has been fermenting for a long time: 13 years and counting. This has been a labor of love. But the time is approaching for cutting the umbilical cord and letting the book live her own life.
I have got to admit that the long years of writing this book has produced one immense asset that quickly baked book would never fathom to possess: I have extensively corresponded on the math and history of this book with Paul Erdös, Bartel van der Waerden, Henry Baudet, Dirk Struick, Hilde Brauer, Hilde Abelin-Schur, Walter Ledermann, Nicolaas G. de Bruijn. Many of these great people are not with us any more; others are in their 90s. Their knowledge, their memories will provide blood to the body of my book. I am infinitely indebted to them all, as well as to younger contributors Edward Nelson of Princeton Math and John Isbell, who are merely in their 70s. I thank numerous archives, including those of the University of Cambridge, Trinity College Dublin, University of Cape Town, University of Berlin, University of Leipzig, and University of Amsterdam. I thank Maya Soifer for restarting my creative engine when at times it worked on low rpm. This coloring book is for my late father, a great painter, who introduced colors into my life.
TABLE OF CONTENTS
CHAPTER 0 PROLOGUE
CHAPTER I COLORED CIRCLE AND SPHERE
1. Problems of Striped Fabrics.
2. From 3-Colored Sphere to Borsuk Problem.
CHAPTER II COLORED PLANE: Chromatic Number of the Plane
3. The Problem.
4. The History.
5. Coloring of Finite Sets in the Plane and Results near the Lower Bound.
6. Polychromatic Number of the Plane and Results near the Upper Bound.
7. Continuum of 6-Colorings.
8. Art of Coloring: Ode to Bees.
CHAPTER III COLORED GRAPHS
9. Chromatic Number of a Graph.
10. Dimension of a Graph.
11. Faithful Dimension of a Graph.
12. Edge Chromatic Number of a Graph.
13. Edge Colored Graphs. Ramsey Theorem.
CHAPTER IV FROM PIGEONHOLE PRINCIPLES TO RAMSEY PRINCIPLES
14. From Pigeonhole Principle to the Finite Ramsey Principle.
15. From Infinite Pigeonhole Principle to the Infinite Ramsey Principle.
16. Who was this “Ramsey” anyway?
CHAPTER V COLORED INTEGERS
17. Issai Schur.
18. A Coloring Solution of a Colored Problem: Schur Theorem.
19. Monochromatic Arithmetic Progressions: Van der Waerden Theorem.
20. Psychology of discovery: How Bartel Leendert van der Waerden found his proof.
21. Whose Conjecture had van der Waerden proven?
Two Lives between the Two Wars: Issai Schur and Pierre Joseph Henry Baudet.
22. In search for Van der Waerden.
23. From van der Waerden to Szemeredi, Fürstenberg, and Bergelson and Hindman.
CHAPTER VI COLORED POLYGONS
24. Monochromatic Sets of Points in a 2-Colored Plane. Some Conditional Results.
25. 3-Colored Plane, 2-Colored Space and Ramsey Sets.
26. Gallai Theorem. Tibor Gallai, Ernst Witt, and Adriano Garsia.
27. Partitions of Integers into Arithmetic Progressions and Colored Polygons.
CHAPTER VII Colored Intergers in Service of Geometry, or
How Paul O’Donnell united Ramsean mathematics (and no one noticed)
28. Application of van der Waerden Theorem.
29. Applications of Bergelson-Hindman and Faltings Theorems.
30. Solution of a long standing Erdös Problem.
CHAPTER VIII FOUR COLOR PROBLEM
31. Definitions.
32. Prologue, or How Four Color Conjecture (4CC) Was Born.
33. The Comedy of Errors.
34. Two-Colorable Maps.
35. Three-Colorable Maps.
36. Kempe's Assault on 4CC and Kempe-Heawood Five-Color Map Coloring
Theorem.
37. Peter Guthrie Taite's Equivalence.
38. Four Color Theorem and Generalizations.
39. Two Dozen Years of Debate.
CHAPTER IX PREDICTING THE FUTURE
40. Excursion into sets.
41. Examples: How Chromatic Number can be affected by presence of absence of
Choice.
42. A Glimpse into the Future: Chromatic Number of the Plane with Choice and
with no Choice.
CHAPTER X EPILOGUE
43. Two Celebrated Coloring Problems on the Plane.
