The Other Pure Seminar (TOPS): The Rado Graph: A graph that's so random, it loops back around to become deterministic (Talk 1 of 2)

Speaker: Adam Hamilton

Title: The Rado Graph: A graph that's so random, it loops back around to become deterministic.

Abstract: I will be presenting two talks about the Rado graph.

The first talk will be an introduction to the Rado graph, the random graph on a countable number of vertices. We will prove that the Rado graph is almost surely unique, go over some alternative methods of generating this graph that don't involve randomness, and finally introduce the 0-1 theorem, a surprising theorem that says that any statement in first order logic that can hold in the Rado graph, will hold with probability one. This means that for any statement about a graph, expressed in first order logic, the statement will either hold for almost all graphs or for none of them.

In the second talk, we will investigate the structure of the Rado graph. Despite being created via random process, we will show that the Rado graph has a large, rich automorphism group. We will also look at the Rado graph from the perspective of random walks.

These talks provide a survey about the Rado graph. I will presume mathematical maturity from the audience but very minimal background. Come along, it'll be fun.