Speaker: Peter Cameron, University of St Andrews

Title: The Random graph

Abstract:

A large random finite graph, with high probability, has no non-trivial symmetry. However, Paul Erdos and Alfred Renyi discovered in 1963 that a random countable graph has an infinite group of automorphisms. The reason for this is even more surprising: there is only one countable random graph (that is, there is a graph which occurs with probability 1 up to isomorphism). This graph, and its automorphism group, have a rich structure, and make occurrences in several areas including set theory, number theory and topology. However, the graph is not an isolated phenomenon. In the late1940s, Roland Fraısse gave a necessary and sufficient condition for the existence of a countable homogeneous structure with prescribed finite substructures; the random graph is an example of his theory. But Fraısse was not the first to take this road. A posthumous paper of Pavel Urysohn (who was drowned in the Bay of Biscay in 1924 at the age of 26) constructed a homogeneous Polish space(complete separable metric space) using methods similar to those later developed by Fraısse.