There are ten kinds of people in the world. Those who think in binary and those who don't.

Department of Computer Science and Department of Mathematics

Courant Institute, New York University

New York, NY 10012, U.S.A.

212-998-3219 (voice) 212-995-4124 (fax)

In Spring 2015 I am scheduled to teach Algebra II and Fundamental Algorithms. Information about these courses will be posted sometime in Fall 2014. Students may email with queries at any time.

Asymptotics in one form or another are part of the landscape for every mathematician. The objective of this book is to present the ideas of how to approach asymptotic problems that arise in discrete mathematics, analysis of algorithms, and number theory. A broad range of topics is covered, including distribution of prime integers, Erdos Magic, random graphs, Ramsey numbers, and asymptotic geometry.

The author is a disciple of Paul Erdos, who taught him about Asymptopia. Primes less than n, graphs with v vertices, random walks of t steps--Erdos was fascinated by the limiting behavior as the variables approached, but never reached, infinity. Asymptotics is very much an art. The various functions nlnn, n^2, (ln n)/n, \sqrt{\ln n}, ln(ln n) all have distinct personalities. Erdos knew these functions as personal friends. It is the author's hope that these insights may be passed on, that the reader may similarly feel which function has the right temperament for a given task.

Asymptopia is a beautiful world. Enjoy!

For ordering information from AMS (also available on Amazon) click here

Click (Material will be slightly different from the text here and below) for preface

Click here for Chapter 0 on primes

Click here for Chapter 1 on Stirling's Formula

Chapters: An Infinity of Primes; Stirling's Formula; Big Oh, Little Oh and All That; Integration in Asymptopia; From Integrals to Sums; Asymptotics of Binomial Coefficients; Unicyclic Graphs; Ramsey Numbers; Large Deviations; Primes; Asymptotic Geometry; Algorithms; Potpourri; Really Big Numbers!

Click here for the frontcover front cover with a great picture of Uncle Paul

Click here for a richgetricher new Probabilistic Lens on Preferential Attachment

Click here for a phasetransition new chapter on the Erdos-Renyi Phase Transition, with particular emphasis on the Critical Window.

Click for more, available from archives here Click here Hannah1 Hannah2 Hannah3 Hannah4 for our most beautiful and most attentive reader. She's a fox! And, in strong competition: johanna and jazmin SPECIAL OFFER: Yes, your child (grandchild, niece, nephew, sibling) can have an Erdos Number of 1+\sqrt{-1}! Just send a photo of him/her absorbed in reading/playing/teething our book and I'll post it!

Photo by MA

Click for family photos, or a photo of Paul Erdos.

Robin Moser, a student of Emo Welzl (ETH), has given an algorithmic implementation of the Lovasz Local Lemma. A rough explanation:

postscript LaTeX pdf Click for Moser's paper with Gabor Tardos .

Nikhil Bansal (at TU Eindhoven (Holland)) has given an algorithmic
implementation of my result that given any n sets on n points there
is a 2-coloring with all discrepencies less than 6 \sqrt{n}. I had
long conjectured that no algorithm would exist.
Semidefinite Programming is a key ingredient. His preprint,
Constructive Algorithms for Discrepancy Minimization, is available on arXiv.
Click for
Bansal's paper .
or here

postscript
LaTeX
pdf
for my own rough explanation. Shachar Lovett and Raghu Meka
ArXiV link .
have come up with another argument, using a restricted Brownian Motion.

Erdos Wikipedia page

Danielle (daughter)'s website

Erdos Number Project

Budapest Semesters in Mathematics

Combinatorialist Rogue Gallery

[TOP]