Earlier this year, Wiley was proud to publish the fourth edition of The Probabilistic Method by Noga Alon, Baumritter Professor of Mathematics and Computer Science at Tel Aviv University and Joel Spencer, Professor of Mathematics and Computer Science at the Courant Institute of New York University.
Maintaining a standard of excellence that establishes The Probabilistic Method as the leading reference on probabilistic methods in combinatorics, the fourth edition continues to feature a clear writing style, illustrative examples, and illuminating exercises. The new edition includes numerous updates to reflect the most recent developments and advances in discrete mathematics and the connections to other areas in mathematics, theoretical computer science, and statistical physics.
Emphasizing the methodology and techniques that enable problem-solving, this fourth edition begins with a description of tools applied to probabilistic arguments, including basic techniques that use expectation and variance as well as the more advanced applications of martingales and correlation inequalities. The authors explore where probabilistic techniques have been applied successfully and also examine topical coverage such as discrepancy and random graphs, circuit complexity, computational geometry, and derandomization of randomized algorithms.
The book features:
- Additional exercises throughout with hints and solutions to select problems in an appendix to help readers obtain a deeper understanding of the best methods and techniques
- New coverage on topics such as the Local Lemma, Six Standard Deviations result in Discrepancy Theory, Property B, and graph limits
- Updated sections to reflect major developments on the newest topics, discussions of the hypergraph container method, and many new references and improved results
This fourth edition is an ideal textbook for upper-undergraduate and graduate-level students majoring in mathematics, computer science, operations research, and statistics. It is also an excellent reference for researchers and combinatorists who use probabilistic methods, discrete mathematics, and number theory.
Statistics Views talked to Professor Spencer when he was recently visiting Oxford University to give a lecture.
1. What is it about probability and combinatorics that fascinate you?
I’ve been fascinated by discrete mathematics for a long time. Some mathematicians think in terms of continuous things analytically and others like myself in terms of finite objects, but I am particularly fascinated by asymptotics. With all the emphasis these days on Big Data, size is something that people really look at. The notion of sorting a billion elements is not so far-fetched anymore. People do it all the time as they are interested in the structure of very large objects and then in the mathematical sense they become asymptotic and you look at the limit as the size goes to infinity, so these are not infinite objects. I have worked on asymptotic problems from the very beginning. I think this is at the heart of the area I work in.
I wrote a short book for the AMS Student Mathematical Library, called Asymptopia, a word that I invented myself because of the utopia of working on asymptotics. That work is geared towards undergraduates and specifically talks about what methods are that you do when you are trying to make asymptotic calculations.
2. What will be your next book-length undertaking?
The last undertaking was indeed Asymptopia which came out several months ago. I am taking a breather right now. I’ve written a lot of books and there have been various editions of them. I really enjoyed writing them as I feel very much that there is something in a book that says more than the sum of its parts. You can take disparate results and you can put them together in a cohesive area in a book.
Something will come along but I don’t have any particular plans yet.
3. You have also written Ramsey Theory whose latest edition was published in 2013. Could you tell us more about this title please?
This is also an area I worked in from the very start as Ramsey Theory goes back to when I was working on my dissertation. Before that, it was Ramsay Theorems. Frank Ramsay at Cambridge proved some results and over the years, many others came in that worked in the area and we put this together as all of these different theorems were essentially part of one theory and we coined the term, Ramsey Theory. I had a wonderful advisor, Andrew Gleeson, who did some of the very early work on Ramsey Theory, calculating some particular numbers. He was a very bright guy and I told him that I was thinking about these numbers and he showed me some other papers that have those numbers. You wouldn’t believe the amount of work I did trying to find other numbers! This turned out to be wonderful for me as I think it was then that I switched to asymptotics, realising that I was not going to look at the exact value. I was going to look at what happens to these numbers and how can we approximate them in some way.
4. You are Professor of Computer Science and Mathematics at New York University. Please could you tell us about your educational background and what inspired you to pursue your career in mathematics?
I was an undergraduate at MIT majoring in math and then I was a graduate student at Harvard. Like I said earlier, for some reason, I was always been interested in discrete mathematics. I think mathematicians have different mind sets and mine was geared in that way. But the real inspiration was Paul Erdos who was inspirational to countless numbers of people. I had actually left graduate school without a PhD but I was working and with very good people such as Ron Graham and then I met Paul. He would take people like myself with a reasonable amount of talent and bring us to a whole new level. So when he came into my life and we wrote a book together on his theorems, this was inspirational in a way that was really remarkable for me. I think of him often when working with my own students. Sometimes you can really inspire people. Erdos had this circle of people around him and it is a great honour of my life that Erdos was, is and will be the centre of my mathematical life. He was that powerful a figure. He was exceptional at posing problems and if you could solve one, it was the most wonderful thing in the world. For me and so many others, this was the most major influence on my mathematical life. Let me give a religious analogy – if you think of a saint who has a faith and when you are around the saint, you feel the saint’s faith which then gives you the faith, well, that’s how it was with Paul. Everybody called him ‘Uncle Paul’ regardless of what age you were. If you could see his fire, then you received that fire.
5. What are your research interests? What are you working on currently? What are your main objectives and what do you hope to achieve through the results?
I have a couple of wonderful students that I am working with. I am looking at a very well- studied process called the Galton-Watson process where you start with a node that has children with randomness and then they have children, and so on. But what we are adding to the process is logic. Mathematical logic has always been an interest of mine even though I never had any training but read about it. We are interested in looking at properties that are expressible in a certain logic, so this has given what I feel is a new twist on studying these Galton-Watson processes. We are very excited about this and have far more open questions than we have theorems.
6. Are there people that have been influential in your career?
Certainly Erdos whom I have already mentioned, whom is not only number one but in a special class by himself. Another person definitely is Ron Graham. This year I attended his retirement conference in his honour. He is aged 80 but still active and he played a special role throughout my career. When I left Harvard, I had a year at Bell Labs where Ron was, and he was tremendously supportive. I often wonder in what direction I would have gone without his support. My colleague Noga Alon has been very influential. I have been very influenced by the Hungarian School of Mathematics. They have a slightly different way of looking at mathematics – they love to solve problems and it fits me very well. So Budapest is now my second home. I go back frequently. Vera Sos has done fundamental work in number theory, combinatorics and probability and I have learnt so much from her. When I advise my graduate students on where they go for their postdocs I tell them it is vital do have at that stage great people right down the hall. I have been personally very lucky that way. I try to ensure that my students end up in the best situations.