Erdős on graphs: his legacy of unsolved problems

This book is a tribute to Paul Erdos, the wandering mathematician once described as the "prince of problem solvers and the absolute monarch of problem posers." It examines the legacy of open problems he left to the world after his death in 1996. Cover......Page 1 Half Title......Page 2 Title Page......Page 4 Copyright Page......Page 5 Dedication......Page 6 Table of Contents......Page 8 Preface......Page 10 Remembering Uncle Paul......Page 11 Acknowledgements......Page 12 Chapter 1: Introduction......Page 14 1.1: Definitions and Notation......Page 15 1.2: About the References......Page 16 2.2: Origins......Page 18 2.3: Classical Ramsey Theory......Page 21 2.4: Graph Ramsey Theory......Page 28 2.5: Multicolored Ramsey Numbers......Page 34 2.6: Size Ramsey Numbers......Page 38 2.7: Induced Ramsey Numbers......Page 42 2.8: Ramsey Theory for Hypergraphs......Page 43 3.2: Origins......Page 46 3.3: Turán Numbers for Bipartite Graphs......Page 49 3.4: Turán Problems for Even Cycles and Their Generalizations......Page 52 3.5: General Extremal Problems......Page 57 4.1: Introduction......Page 70 4.2: Origins......Page 71 4.3: Chromatic Number and Girth......Page 73 4.4: Chromatic Numbers and Cliques......Page 74 4.5: List Colorings......Page 75 4.6: Critical Graphs......Page 78 4.7: Chromatic Index......Page 80 4.8: General Coloring Problems......Page 81 4.9: Covering and Packing......Page 83 5.1: Introduction......Page 86 5.2: Origins......Page 87 5.3: The Chromatic Number of a Random Graph......Page 92 5.4: General Problems on Random Graphs......Page 94 5.5: Subgraph Enumeration......Page 96 6.1: Introduction......Page 102 6.2: Origins......Page 103 6.3: Turán Problems for Hypergraphs......Page 105 6.4: Stars......Page 108 6.5: A Problem of Erdős, Faber, and Lovász......Page 110 6.6: Chromatic Hypergraphs......Page 112 6.7: General Hypergraph Problems......Page 115 7.1: Origins......Page 122 7.2: Introduction......Page 124 7.3: Ordinary Partition Relations for Ordinals......Page 125 7.4: Chromatic Numbers and Infinite Graphs......Page 126 7.5: General Problems for Infinite Graphs......Page 128 Paul Erdős, The World's Most Beloved Mathematical Genius "Leaves"......Page 132 Erdős, Cars and Goats, and Bayes' Theorem......Page 143 Erdős, The Other Woman, and The Theorem of Penta-Chords......Page 144 Index......Page 152