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

To Paint a Bird

Foreword

Foreword

Foreword

Acknowledgments

Contents

Greetings to the Reader

Merry-Go-Round

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 Tongue of APs

1.4 Prehistory

1.5 Completing the Go-Round

Colored Plane

Chromatic Number of the Plane: The Problem

Chromatic Number of the Plane: An Historical Essay

Polychromatic Number of the Plane and Results Near the Lower Bound

De Bruijn–Erdös Reduction to Finite Sets and Results Near the Lower Bound

Polychromatic Number of the Plane and Results Near the Upper Bound

6.1 Stechkin’s 6-Coloring

6.2 Best 6-Coloring of the Plane

6.3 The Age of Tiling

Continuum of 6-Colorings of the Plane

Chromatic Number of the Plane in Special Circumstances

Measurable Chromatic Number of the Plane

9.1 Definitions

9.2 Lower Bound for Measurable Chromatic Number of the Plane

9.3 Kenneth J. Falconer

Coloring in Space

Rational Coloring

Coloring Graphs

Chromatic Number of a Graph

12.1 The Basics

12.2 Chromatic Number and Girth

12.3 Wormald’s Application

Dimension of a Graph

13.1 Dimension of a Graph

13.2 Euclidean Dimension of a Graph

Embedding 4-Chromatic Graphs in the Plane

14.1 A Brief Overture

14.2 Attaching a 3-Cycle to Foundation Points in 3 Balls

14.3 Attaching a k-Cycle to a Foundation Set of Type (a1, a2, a3, 0)d

14.4 Attaching a k-Cycle to a Foundation Set of Type (a1, a2, a3, 1)d

14.5 Attaching a k-Cycle to Foundation Sets of Types (a1, a2, 0, 0)d and (a1, 0, a3, 0)d

14.6 Removing Coincidences

14.7 O’Donnell’s Embeddings

14.8 Appendix

Embedding World Records

15.1 A 56-Vertex, Girth 4, 4-Chromatic Unit Distance Graph [ Odo1]

15.2 A 47-Vertex, Girth 4, 4-Chromatic, Unit Distance Graph [ Chi6]

15.3 A 40-Vertex, Girth 4, 4-Chromatic, Unit Distance Graph [ Odo2]

15.4 A 23-Vertex, Girth 4, 4-Chromatic, Unit Distance Graph [ HO]

15.5 A 45-Vertex, Girth 5, 4-Chromatic, Unit Distance Graph [ HO]

Edge Chromatic Number of a Graph

16.1 Vizing’s Edge Chromatic Number Theorem

16.2 Total Insanity around the Total Chromatic Number Conjecture

Carsten Thomassen’s 7-Color Theorem

Coloring Maps

How the Four-Color ConjectureWas Born

18.1 The Problem is Born

18.2 A Touch of Historiography

18.3 Creator of the 4 CC, Francis Guthrie

18.4 The Brother

Victorian Comedy of Errors and Colorful Progress

19.1 Victorian Comedy of Errors

19.2 2-Colorable Maps

19.3 3-Colorable Maps

19.4 The New Life of the Three-Color Problem

Kempe–Heawood’s Five-Color Theorem and Tait’s Equivalence

20.1 Kempe’s 1879 Attempted Proof

20.2 The Hole

20.3 The Counterexample

20.4 Kempe–Heawood’s Five-Color Theorem

20.5 Tait’s Equivalence

20.6 Frederick Guthrie’s Three-Dimensional Generalization

The Four-Color Theorem

The Great Debate

22.1 Thirty Plus Years of Debate

22.2 Twenty Years Later, or Another Time – Another Proof

22.3 The Future that commenced 65 Years Ago: Hugo Hadwiger’s Conjecture

How Does One Color Infinite Maps? A Bagatelle

Chromatic Number of the Plane Meets Map Coloring: Townsend – Woodall’s 5- Color Theorem

24.1 On Stephen P. Townsend’s 1979 Proof

24.2 Proof of Townsend–Woodall’s 5-Color Theorem

Colored Graphs

Paul Erdös

25.1 The First Encounter

25.2 Old Snapshots of the Young

De Bruijn–Erdös’s Theorem and Its History

26.1 De Bruijn–Erdös’s Compactness Theorem

26.2 Nicolaas Govert de Bruijn

Edge Colored Graphs: Ramsey and Folkman Numbers

27.1 Ramsey Numbers

27.2 Folkman Numbers

The Ramsey Principle

From Pigeonhole Principle to Ramsey Principle

28.1 Infinite Pigeonhole and Infinite Ramsey Principles

28.2 Pigeonhole and Finite Ramsey Principles

The Happy End Problem

29.1 The Problem

29.2 The Story Behind the Problem

29.3 Progress on the Happy End Problem

29.4 The Happy End Players Leave the Stage as Shakespearian Heroes

The Man behind the Theory: Frank Plumpton Ramsey

30.1 Frank Plumpton Ramsey and the Origin of the Term “ Ramsey Theory&rdquo

30.2 Reflections on Ramsey and Economics, by Harold W. Kuhn

Colored Integers: Ramsey Theory Before Ramsey and Its AfterMath

Ramsey Theory Before Ramsey: Hilbert’s Theorem

Ramsey Theory Before Ramsey: Schur’s Coloring Solution of a Colored Problem and Its Generalizations

32.1 Schur’s Masterpiece

32.2 Generalized Schur

32.3 Non-linear Regular Equations

Ramsey Theory before Ramsey: Van der Waerden Tells the Story of Creation

Whose Conjecture Did Van derWaerden Prove? Two Lives Between TwoWars: Issai Schur and Pierre Joseph Henry Baudet

34.1 Prologue

34.2 Issai Schur

34.3 Argument for Schur’s Authorship of the Conjecture

34.4 Enters Henry Baudet II

34.5 Pierre Joseph Henry Baudet

34.6 Argument for Baudet’s Authorship of the Conjecture

34.7 Epilogue

Monochromatic Arithmetic Progressions: Life After Van derWaerden

35.1 Generalized Schur

35.2 Density and Arithmetic Progressions

35.3 Who and When Conjectured What Szemeredi Proved?

35.4 Paul Erdös’s Favorite Conjecture

35.5 Hillel Furstenberg

35.6 Bergelson’s AG Arrays

35.7 Van der Waerden’s Numbers

35.8 A Japanese Bagatelle

In Search of Van der Waerden: The Early Years

36.1 Prologue: Why I Had to Undertake the Search for Van derWaerden

36.2 The Family

36.3 Young Bartel

36.4 Van der Waerden at Hamburg

36.5 The Story of the Book

36.6 Theorem on Monochromatic Arithmetic Progressions

36.7 Göttingen and Groningen

36.8 Transformations of The Book

36.9 Algebraic Revolution That Produced Just One Book

36.10 Epilogue: On to Germany

In Search of Van der Waerden: The Nazi Leipzig, 1933 – 1945

37.1 Prologue

37.2 Before the German Occupation of Holland: 1931–1940

37.3 Years of the German Occupation of the Netherlands: 1940 – 1945

37.4 Epilogue: TheWar Ends

In Search of Van der Waerden: The Postwar Amsterdam, 1945166

38.1 Breidablik

38.2 NewWorld or Old?

38.3 Defense

38.4 Van der Waerden and Van der Corput: Dialog in Letters

38.5 A Rebellion in Brouwer’s Amsterdam

In Search of Van der Waerden: The Unsettling Years, 1946 – 1951

39.1 The Het Parool Affair

39.2 Job History 1945–1947

39.3 “America! America!&rdquo

39.4 Van der Waerden, Goudsmit and Heisenberg: A ‘Letteral Triangle&rsquo

39.5 Professorship at Amsterdam

39.6 Escape to Neutrality

39.7 Epilogue: The Drama of Van der Waerden

Colored Polygons: Euclidean Ramsey Theory

Monochromatic Polygons in a 2-Colored Plane

3-Colored Plane, 2-Colored Space, and Ramsey Sets

Gallai’s Theorem

42.1 Tibor Gallai and His Theorem

42.2 Double Induction

42.3 Proof of Gallai’s Theorem byWitt

42.4 Adriano Garsia

42.5 An Application of Gallai

42.6 Hales-Jewett’s Tic-Tac-Toe

Colored Integers in Service of Chromatic Number of the Plane: How O’Donnell Unified Ramsey Theory and No One Noticed

Application of Baudet–Schur –Van derWaerden

Application of Bergelson–Leibman’s and Mordell – Faltings’ Theorems

Solution of an Erdös Problem: O'Donnell's Theorem

45.1 O'Donnell's Theorem

45.2 Paul O'Donnell

Predicting the Future

What If We Had No Choice?

46.1 Prologue

46.2 The Axiom of Choice and its Relatives

46.3 The First Example

46.4 Examples in the plane

46.5 Examples in space

46.6 AfterMath & Shelah–Soifer Class of Graphs

46.7 An Unit Distance Shelah–Soifer Graph

A Glimpse into the Future: Chromatic Number of the Plane, Theorems and Conjectures

47.1 Conditional Chromatic Number of the Plane Theorem

47.2 Unconditional Chromatic Number of the Plane Theorem

47.3 The Conjecture

Imagining the Real, Realizing the Imaginary

48.1 What Do the Founding Set Theorists Think about the Foundations?

48.2 So, What Does It All Mean?

48.3 Imagining the Real vs. Realizing the Imaginary

Farewell to the Reader

Two Celebrated Problems

Bibliography

Name Index

Subject Index

Index of Notations