Preface xi Doing mathematics is anything but austere. As an undergraduate teacher of mine, Gian-Carlo Rota, put it: A mathematician’s work is mostly a tangle of guess- work, analogy, wishful thinking and frustration, and proof, far from being the core of discovery, is more often than not a way of making sure that our minds are not playing tricks. That said, the “guesswork” can be finely honed. Uncle Paul’s selec- tion of the right p did not come at random. Brilliance, of course, is more than helpful. But we mortals can also sometimes succeed. Paul Erd˝ os lived2 in Asymptopia. Primes less than n, graphs with v vertices, random walks of t steps—Erd˝ os was fascinated by the limiting behavior as the variables approached, but never reached, infinity. Asymptotics is very much an art. In his masterwork, The Periodic Table, Primo Levi speaks of the personalities of the various elements. A chemist will feel when atoms want or do not want to bind. In asymptotics the various functions n ln n, n2, ln n n , ln n, 1 n ln n all have distinct personalities. Erd˝ os knew these functions as personal friends. This author had the great privilege and joy of learn- ing directly from Paul Erd˝ os. It is my hope that these insights may be passed on, that the reader may similarly feel which function has the right temperament for a given task. My decision to write this work evolved over many years, and it was my students who opened my eyes. I would teach courses in discrete mathematics, probability, Ramsey theory, graph theory, the probabilistic method, number theory, and other areas. I would carefully give, for example, Erd˝ os’s classic result (Theorem 7.1) on Ramsey numbers: If n k 21−(k) 2 1, then R(k, k) n. I spent much less time on the asymptotic implica- tion (7.6), that R(k, k) (1 + o(1)) k e 2 2 k . My students showed me 2 Erd˝ os’s breadth was extraordinary. This refers to only one aspect of his oeuvre.
Previous Page Next Page