The New Mathematical Coloring Book : Mathematics of Coloring and the Colorful Life of Its Creators

The New Mathematical Coloring Book (TNMCB) includes striking results of the past 15-year renaissance that produced new approaches, advances, and solutions to problems from the first edition. A large part of the new edition “Ask what your computer can do for you,” presents the recent breakthrough by Aubrey de Grey and works by Marijn Heule, Jaan Parts, Geoffrey Exoo, and Dan Ismailescu. TNMCB introduces new open problems and conjectures that will pave the way to the future keeping the book in the center of the field. TNMCB presents mathematics of coloring as an evolution of ideas, with biographies of their creators and historical setting of the world around them, and the world around us. A new thing in the world at the time, TMCB I is now joined by a colossal sibling containing more than twice as much of what only Alexander Soifer can deliver: an interweaving of mathematics with history and biography, well-seasoned with controversy and opinion. – Peter D. Johnson, Jr. Auburn University Like TMCB I, TMCB II is a unique combination of Mathematics, History, and Biography written by a skilled journalist who has been intimately involved with the story for the last half-century. ...The nature of the subject makes much of the material accessible to students, but also of interest to working Mathematicians. ... In addition to learning some wonderful Mathematics, students will learn to appreciate the influences of Paul Erdős, Ron Graham, and others.– Geoffrey Exoo Indiana State University The beautiful and unique Mathematical coloring book of Alexander Soifer is another case of “good mathematics”, containing a lot of similar examples (it is not by chance that Szemerédi’s Theorem story is included as well) and presenting mathematics as both a science and an art...– Peter Mihók Mathematical Reviews , MathSciNet A postman came to the door with a copy of the masterpiece of the century. I thank you and the mathematics community should thank you for years to come. You have set a standard for writing about mathematics and mathematicians that will be hard to match.– Harold W. Kuhn Princeton University I have never encountered a book of this kind. The best description of it I can give is that it is a mystery novel... I found it hard to stop reading before I finished (in two days) the whole text. Soifer engages the reader's attention not only mathematically, but emotionally and esthetically. May you enjoy the book as much as I did!– Branko Grünbaum University of Washington I am in absolute awe of your 2008 book. – Aubrey D.N.J. de Grey LEV Foundation To Paint the Portrait of a Bird Foreword to the Second Edition Foreword to the Second Edition Foreword to the First Edition Foreword to the First Edition Foreword to the First Edition Acknowledgments-2023 Acknowledgments-2009 Greetings to the Reader 2023 Greetings to the Reader 2009 Contents About the Author Part I: Merry-Go-Round Chapter 1: A Story of Colored Polygons and Arithmetic Progressions 1.1 The Story of Creation 1.2 The Problem of Colored Polygons 1.3 Translation into the Language of Arithmetic Progressions 1.4 Prehistory 1.5 Completing the Go-Round Part II: Colored Plane Chapter 2: Chromatic Number of the Plane: The Problem Chapter 3: Chromatic Number of the Plane: A Historical Essay Chapter 4: Polychromatic Number of the Plane and Results Near the Lower Bound Chapter 5: De Bruijn-Erdos Reduction to Finite Sets and Results Near the Lower Bound Chapter 6: Polychromatic Number of the Plane and Results Near the Upper Bound 6.1 Stechkin ́s 6-Coloring 6.2 The Best 6-Coloring of the Plane 6.3 The Age of Tiling Chapter 7: Continuum of 6-Colorings of the Plane Chapter 8: Chromatic Number of the Plane in Special Circumstances Chapter 9: Measurable Chromatic Number of the Plane 9.1 Definitions 9.2 Bounds for the Measurable Chromatic Number of the Plane 9.3 Kenneth J. Falconer Chapter 10: Coloring in Space Chapter 11: Rational Coloring Part III: Coloring Graphs Chapter 12: Chromatic Number of a Graph 12.1 The Basics 12.2 Chromatic Number and Girth 12.3 Wormald ́s Application Chapter 13: Dimension of a Graph 13.1 Dimension of a Graph 13.2 Euclidean Dimension of a Graph Chapter 14: Embedding 4-Chromatic Graphs in the Plane 14.1 A Brief Overture 14.2 Attaching a 3-Cycle to Foundation Points in Three Balls 14.3 Attaching a k-Cycle to a Foundation Set of Type (a1,a2,a3,0)δ 14.4 Attaching a k-Cycle to a Foundation Set of Type (a1,a2,a3,1)δ 14.5 Attaching a k-Cycle to the Foundation Sets of Types (a1,a2,0,0)δ and (a1,0,a3,0)δ 14.6 Removing Coincidences 14.7 O ́Donnell ́s Embeddings Appendix Chapter 15: Embedding World Series 15.1 A 56-Vertex, Girth 4, 4-Chromatic Unit Distance Graph 15.2 A 47-Vertex, Girth 4, 4-Chromatic Unit Distance Graph [Chi] 15.3 A 40-Vertex, Girth 4, 4-Chromatic Unit Distance Graph 15.4 A 23-Vertex, Girth 4, 4-Chromatic Unit Distance Graph 15.5 A 45-Vertex, Girth 5, 4-Chromatic Unit Distance Graph Chapter 16: Exoo-Ismailescu: The Final Word on Problem 15.4 16.1 A Brief Story of Submission 16.2 Constructing Triangle-Free, 4-Chromatic Unit Distance Graphs 16.3 A Triangle-Free, 4-Chromatic Unit Distance Graph on 21 Vertices 16.4 A Triangle-Free, 4-Chromatic Unit Distance Graph on 19 Vertices 16.5 A Triangle-Free, 4-Chromatic Unit Distance Graph on 17 Vertices Chapter 17: Edge Chromatic Number of a Graph 17.1 Vizing ́s Edge Chromatic Number Theorem 17.2 Total Insanity Around Total Chromatic Number Conjecture 17.3 What Else Can We Color in a Graph? Chapter 18: Carsten Thomassen ́s 7-Color Theorem Part IV: Coloring Maps Chapter 19: How the Four-Color Conjecture Was Born 19.1 The Problem Is Born 19.2 A Touch of Historiography and a Historical Conjecture 19.3 The Creator of the Four-Color Conjecture: Francis Guthrie 19.4 The Brother Chapter 20: A Victorian Comedy of Errors and Colorful Progress 20.1 A Victorian Comedy of Errors 20.2 2-Colorable Maps 20.3 3-Colorable Maps 20.4 The New Life of the Three-Color Problem Chapter 21: Kempe-Heawood ́s Five-Color Theorem and Tait ́s Equivalence 21.1 Kempe ́s 1879 Attempted Proof of the Four-Color Theorem 21.2 The Hole 21.3 The Counterexample 21.4 The Kempe-Heawood Five-Color Theorem 21.5 Tait ́s Equivalence 21.6 Frederick Guthrie ́s Three-Dimensional Generalization Chapter 22: The Four-Color Theorem Chapter 23: The Great Debate 23.1 40 Years of Debate 23.2 Twenty Years Later, or Another Time - Another Proof 23.3 The Future that Commenced 80 Years Ago: Hugo Hadwiger ́s Conjecture Chapter 24: How Does One Color Infinite Maps? A Bagatelle Chapter 25: Chromatic Number of the Plane Meets Map Coloring: Townsend-Woodall ́s 5-Color Theorem 25.1 On Stephen P. Townsend ́s 1979 Proof 25.2 Proof of Townsend-Woodall ́s 5-Color Theorem Part V: Colored Graphs Chapter 26: Paul Erdos 26.1 The First Encounter 26.2 Old Snapshots of the Young Chapter 27: De Bruijn-Erdos ́ Theorem and Its History 27.1 The De Bruijn-Erdos Compactness Theorem Chapter 28: Nicolaas Govert de Bruijn Chapter 29: Edge-Colored Graphs: Ramsey and Folkman Numbers 29.1 Ramsey Numbers 29.2 Folkman Numbers Part VI: The Ramsey Principles Chapter 30: From Pigeonhole Principle to Ramsey Principle 30.1 Infinite Pigeonhole and Infinite Ramsey Principles 30.2 Pigeonhole Principle and Finite Ramsey Principle Chapter 31: The Happy End Problem 31.1 The Problem 31.2 The Story Behind the Happy End Problem 31.3 An Early Photograph of Turn Pl and His First Family 31.4 Progress on the Happy End Problem 31.5 The Happy End Players Leave the Stage as Shakespearian Heroes Chapter 32: The Man Behind the Theory: Frank Plumpton Ramsey 32.1 Frank Plumpton Ramsey and the Origin of the Term ``Ramsey Theory ́ ́ 32.2 What ́s in a Name? That Which We Call a Rose by Any Other Name Would Smell as Sweet 32.3 Bruce Lee Rothschild 32.4 Remembering Ronald Lewis Graham 32.5 Reflections on Ramsey and Economics, by Harold W. Kuhn 32.5.1 Harold William Kuhn Part VII: Colored Integers: Ramsey Theory Before Ramsey and Its AfterMath Chapter 33: Ramsey Theory Before Ramsey: Hilbert ́s Theorem Chapter 34: Ramsey Theory Before Ramsey: Schur ́s Coloring Solution of a Colored Problem and Its Generalizations 34.1 Schur ́s Masterpiece 34.2 Schur ́s Numbers 34.3 Generalized Schur 34.4 Nonlinear Equations or Pythagoras Meets Ramsey 34.5 Marienus Johannes Hendrikus ``Marijn ́ ́ Heule Chapter 35: Ramsey Theory Before Ramsey: Van der Waerden Tells the Story of Creation Chapter 36: A Japanese Insight into Baudet-Schur-Van der Waerden ́s Theorem Chapter 37: Whose Conjecture Did Van der Waerden Prove? Two Lives Between Two Wars: Issai Schur and Pierre Joseph Henry Baudet 37.1 Prologue 37.2 Issai Schur 37.3 Argument for Schur ́s Authorship of the Conjecture 37.4 Enters Henry Baudet II 37.5 Pierre Joseph Henry Baudet 37.6 Argument for Baudet ́s Authorship of the Conjecture 37.7 Summing Up Chapter 38: Monochromatic Arithmetic Progressions or Life After Van der Waerden ́ Proof 38.1 Schur ́s Generalization 38.2 Density and Arithmetic Progressions 38.3 Who and When Conjectured What Szemerédi Proved? 38.4 Paul Erdos ́ Favorite Conjecture 38.5 Hillel ``Harry ́ ́ Furstenberg 38.6 Bergelson ́s AG Arrays 38.7 Van der Waerden ́s Numbers 38.8 Saharon Shelah 38.9 Timothy Gowers Chapter 39: In Search of Van der Waerden: The Early Life 39.1 What You Will Find in This and the Following Three Chapters 39.2 Why Van der Waerden and Why Me? 39.3 The Family 39.4 Van der Waerden at Amsterdam 39.5 Van der Waerden at Hamburg 39.6 The Story of the Book 39.7 The Theorem on Arithmetic Progressions 39.8 From Göttingen to Groningen 39.9 Transformations of the Book 39.10 On to Germany Chapter 40: In Search of Van der Waerden: The Nazi Leipzig, 1933-1945 40.1 The Dawn of the Nazi Era 40.2 The Princeton Job Offer 40.3 Eulogy for the Beloved Teacher 40.4 One Faculty Meeting at Leipzig 40.5 Germany Treacherously Invades Holland 40.6 A Dream of Göttingen Chapter 41: In Search of Van der Waerden: Amsterdam, Year 1945 41.1 Home, Bittersweet Home 41.2 The New World or Old? 41.3 ``The Defense ́ ́ 41.3.1 Defense 41.4 Van der Waerden and Van der Corput: A Dialog in Letters Chapter 42: In Search of Van der Waerden: The Unsettling Years, 1946-1951 42.1 The Het Parool Affair 42.2 Job History 1945-1947 42.3 ``America! America! God Shed His Grace on Thee ́ ́ 42.4 Werner Heisenberg ́s Unpublished Work ``On Active and Passive Opposition in the Third Reich ́ ́ 42.5 Professorship at Amsterdam 42.6 Escape to Neutrality 42.7 Zurück nach Zürich 42.8 Today I: The Scholar and the State 42.9 Today II: ``The Silent Agreement ́ ́ 42.10 Today III: From Rolf Nevanlinna Prize to Abacus Medal: A Noteworthy History of an IMU Prize Chapter 43: How the Monochromatic AP Theorem Became Classic: Khinchin and Lukomskaya PartVIII: Colored Polygons: Euclidean Ramsey Theory Chapter 44: Monochromatic Polygons in a 2-Colored Plane Chapter 45: 3-Colored Plane, 2-Colored Space, and Ramsey Sets Chapter 46: The Gallai Theorem 46.1 Tibor Gallai and His Theorem 46.2 Ernst Witt 46.3 Adriano Garsia 46.4 An Application of Gallai 46.5 Hales-Jewett ́s Tic-Tac-Toe Part IX: Colored Integers in Service of the Chromatic Number of the Plane: How O’Donnell Unified Ramsey Theory and No One Noticed Chapter 47: O ́Donnell Earns His Doctorate Chapter 48: Applications of the Baudet-Schur-Van der Waerden Chapter 49: Applications of the Bergelson-Leibman and the Mordell-Faltings Theorems Chapter 50: Solution of an Erdos Problem: The O ́Donnell Theorem 50.1 Paul O ́Donnell Part X: Ask What Your Computer Can Do for You Chapter 51: Aubrey D.N.J. de Grey ́s Breakthrough Chapter 52: De Grey ́s Construction 52.1 The Plan 52.2 The 4-Colorings of J in Which No Copy of H Contains a Monochromatic Triple 52.3 61-Vertex Graph K Assembled from Two Copies of J 52.4 121-Vertex Graph L Assembled from Two Copies of K 52.5 In Search of Graph M 52.6 Graphs with High Edge Density and Spindle Density 52.7 Construction of a Graph That Serves as M 52.8 Testing 4-Colorability of Edge-Dense, Spindle-Dense Graphs 52.9 Identification of Smaller Solutions 52.10 Status of Shrinking the Graph N 52.11 Reception of de Grey ́s Breakthrough 52.12 Aubrey D.N.J. de Grey 52.13 The Effect of the Breakthrough on Predictions of Many Chapter 53: Marienus Johannes Hendrikus ``Marijn ́ ́ Heule 53.1 The Records 53.2 The Plan 53.3 A Few Definitions 53.4 Propositional Formulas 53.5 Clausal Proofs 53.6 Clausal Proof Minimization 53.7 Encoding 53.8 Graph Trimming 53.9 Randomization 53.10 Critical Graphs 53.11 Validation 53.12 Results 53.12.1 Finding a Small Symmetric Subgraph 53.12.2 Merging Critical Graphs 53.12.3 Minimizing the Small Part 53.12.4 Analysis 53.13 Conclusions 53.14 Marijn Heule ́s Summing-Up Chapter 54: Can We Reach Chromatic 5 Without Mosers Spindles? Chapter 55: Triangle-Free 5-Chromatic Unit Distance Graphs Chapter 56: Jaan Parts ́ Current World Record 56.1 The Record 56.2 Jaan Parts Part XI: What About Chromatic 6? Chapter 57: A Stroke of Brilliance: Matthew Huddleston ́s Proof Chapter 58: Geoffrey Exoo and Dan Ismailescu, or 2 Men for 2 Forbidden Distances 58.1 The Spindling Method 58.2 Two-Distance Graphs of Chromatic Number At Least 5 58.3 Two-Distance Graph of Chromatic Number At Least 6 58.4 Geoffrey Exoo 58.5 Dan Ismailescu Chapter 59: Jaan Parts on Two-Distance 6-Coloring Chapter 60: Forbidden Odds, Binaries, and Factorials 60.1 One Odd Problem 60.2 Forbidden Binaries and Factorials Chapter 61: 7- and 8-Chromatic Two-Distance Graphs Part XII: Predicting the Future Chapter 62: What If We Had No Choice? 62.1 Prologue 62.2 The Axiom of Choice and Its Relatives 62.3 The First Example 62.4 Examples in the Plane 62.5 Examples in Space Chapter 63: AfterMath and the Shelah-Soifer Class of Graphs 63.1 Shelah-Soifer Graphs 63.2 A Unit-Distance Shelah-Soifer Graph Chapter 64: A Glimpse into the Future: Chromatic Number of the Plane, Theorems, and Conjectures 64.1 Conditional Chromatic Number of the Plane Theorem 64.2 Unconditional Chromatic Number of the Plane Theorem 64.3 The Conjecture Part XIII: Imagining the Real, Realizing the Imaginary Chapter 65: What Do the Founding Set Theorists Think About the Foundations? Chapter 66: So, What Does It All Mean? Chapter 67: Imagining the Real or Realizing the Imaginary: Platonism Versus Imaginism Part XIV: Farewell to the Reader Chapter 68: Two Celebrated Problems Bibliography Name Index Subject Index Index of Notations