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!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history and tagged . Bookmark the permalink.

2 Responses to The random graph, 4

  1. Jon Awbrey says:

    It could be that my old machine has trouble with the newer pdfs, but I didn’t find the word biorder in that chapter. For some odd reason (whose critique I omit) the stuff on permutation patterns and flows reminds me of a couple of my own inquiries, one on Riffs and Rotes and the other on Differential Logic and Dynamic Systems, but I’m still working on readable accounts of those, so I’ll just leave these bookmarks here as a reminder to revisit them (quasi-)periodically.

  2. Pingback: The random graph, 4 « Guzman's Mathematics Weblog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.