The Discrete Mathematical Charms of Paul Erdos: A Simple Introduction

Description

Paul Erdos published more papers during his lifetime than any other mathematician, especially in discrete mathematics. He had a nose for beautiful, simply-stated problems with solutions that have far-reaching consequences across mathematics. This captivating book, written for students, provides an easy-to-understand introduction to discrete mathematics by presenting questions that intrigued Erdos, along with his brilliant ways of working toward their answers. It includes young Erdos's proof of Bertrand's postulate, the Erdos-Szekeres Happy End Theorem, De Bruijn-Erdos theorem, Erdos-Rado delta-systems, Erdos-Ko-Rado theorem, Erdos-Stone theorem, the Erdos-Renyi-Sos Friendship Theorem, Erdos-Renyi random graphs, the Chvatal-Erdos theorem on Hamilton cycles, and other results of Erdos, as well as results related to his work, such as Ramsey's theorem or Deza's theorem on weak delta-systems. Its appendix covers topics normally missing from introductory courses. Filled with personal anecdotes about Erdos, this book offers a behind-the-scenes look at interactions with the legendary collaborator.

Vasek Chvatal is Professor Emeritus of Concordia University, where he served as Canada Research Chair in Combinatorial Optimization (2004-2011) and Canada Research Chair in Discrete Mathematics from 2011 to his retirement in 2014. He is the author of Linear Programming (1983) and co-author of The Traveling Salesman Problem: A Computational Study (2007). In the 1970s, he wrote three joint papers with Paul Erdos. He is a recipient of the CSGSS Award for Excellence in Teaching, Rutgers University (1992, 1993, 2001) and co-recipient of the Beale-Orchard-Hays Prize (2000), Frederick W. Lanchester Prize (2007), and John von Neumann Theory Prize (2015).

'Vasek Chvatal was born to write this one-of-a-kind book. Readers cannot help but be captivated by the evident love with which every page has been written. The human side of mathematics is intertwined beautifully with first-rate exposition of first-rate results.' Donald Knuth, Stanford University 'This book is a treasure trove from so many viewpoints. It is a wonderful introduction and an alluring invitation to discrete mathematics - now a central field of mathematics identified mostly with the hero of this book. With lucid, carefully planned chapters on different topics it demonstrates the unique way in which Paul Erdos, one of the most prolific and influential mathematicians of the twentieth century, invented and approached problems. Sprinkled with historical and personal anecdotes and pictures, it opens a window to the unique personality of 'Uncle Paul'. And implicitly, it reveals the charming and candid way in which Vasek Chvatal, an authority in the field and a lifelong friend and collaborator of Erdos, likes to combine teaching and story-telling.' Avi Wigderson, IAS, Princeton 'Paul Erdos is one of the founding fathers of modern combinatorics, whose ability to pose beautiful problems greatly determined the development of this field and influenced many other areas of mathematics. This book uses some basic questions, which intrigued Paul Erdos, to give a nice introduction to many topics in discrete mathematics. It contains a collection of beautiful results, covering such diverse subjects as discrete geometry, Ramsey theory, graph colorings, extremal problems for graphs and set systems and some others. It presents many elegant proofs and exposes the reader to various powerful combinatorial techniques.' Benjamin Sudakov, ETH Zurich 'This is a brilliant book. It manages in one fell swoop to survey and develop a large part of combinatorial mathematics while at the same time chronicling the work of Paul Erdos. His contributions to different areas of mathematics are seen here to be part of a coherent whole. Chvatal's presentation is particularly appealing and accessible. The wonderful personal recollections add to the mathematical content to provide a portrait of Erdos' mind recognizable to those who knew him.' Bruce Rothschild, University of California, Los Angeles 'Vasek Chvatal's book is a gem. Paul Erdos' favorite problems and best work are beautifully laid out. Readers unfamiliar with Erdos' work cannot fail to appreciate its power and elegance, and those who have seen bits and pieces will have the pleasure of seeing it thoughtfully and lovingly presented by a master. It's hard to imagine now, but there was a time when combinatorics was thought to be a jumble of results without depth or coherence. 'Uncle' Paul understood its heart and soul, and nowhere is this more evident than in Chvatal's wonderful compendium. This volume belongs on every math-lover's night-table!' Peter Winkler, Dartmouth College 'Beautiful mathematics is presented with great care and clarity in Vasek Chvatal's book, complemented with well-written anecdotes and personal reminiscences about Paul Erdos. This combination makes the book a very enjoyable reading and a lively tribute to the memory of one of the most prolific mathematicians of all time. Studying discrete mathematics from this book is likely to give a great experience to students and established researchers alike.' Gabor Simonyi, Renyi Institute, Budapest '... Chvatal (emer., Concordia Univ.) has created a gem in this work and deserves congratulation ... Highly recommended.' J. Johnson, Choice Magazine 'This wonderfully written book is undoubtedly a significant contribution to the growing body of literature on the various developments in discrete mathematics over the last several decades. Still, to reduce it to only its mathematical dimension would be an act of injustice not only towards the book but also towards its author. The book is a powerful homage to Paul Erdos as one of the leading mathematicians of the twentieth century as well as a person who, with his unprecedented level of academic generosity and overall human kindness, was one of the pillars of the discrete mathematics community during his lifetime.' Veselin Jungic, MathSciNet