## The random graph, 4

This year is the 100th birthday of Paul Erdős.

After his death in 1996, a two-volume book entitled The Mathematics of Paul Erdős, edited by Ron Graham and Jaroslav Nešetřil, was published. I was fortunate enough to get to write a chapter in the book on one of my favourite topics, the random graph, which I have discussed here at some length.

The random graph was an appropriate topic for a book with this title, since it was Erdős and Rényi who showed its existence. Erdős and Spencer remarked, in their book on probabilistic methods in combinatorics, that the Erdős–Rényi theorem “demolishes the theory of infinite random graphs”: there is only one (at least in the countable case). My contention was that it creates, instead, the theory of the infinite random graph.

Now the book is being revised and reissued to commemorate the Erdős centenary, and I had the opportunity to bring my chapter up to date. I have just posted it on the arXiv here. Comments very welcome: there is a short window for making small changes. (I am sure I have omitted stuff, got things wrong, etc. Please tell me!)

There is quite a bit of new material, but in just over twenty pages I couldn’t give very much detail. However, I was glad to be able to include something which also links in with a couple of recent posts of mine.

A permutation pattern can be regarded as a relational structure consisting of a finite set with two total orders (what I called a biorder): the first order matches the set with {1,2,…,n}, and the second then defines a permutation of these numbers. The set of all permutation patterns is the age of the unique generic countable biorder, a remarkable structure in which any interval in one order, no matter how small, is distributed densely throughout the other. In a preprint (arXiv:1103.5686), Böttcher and Foniok show that the set of finite permutation patterns is a Ramsey class, a result also obtained by Sokić. It follows from the theory of Kechris, Pestov and Todorcevic that the automorphism group of the countable generic biorder is absolutely amenable. More generally, this holds for n-orders for all n, by a general construction of Bodirsky (arXiv:1204.3258).

I think that even Erdős could not have foreseen the remarkable synergy between quite different subjects that has happened here, while he was with us. Now he is reading the Book, he is chuckling to think of the surprises still in store for us!