Michael Cohen, NDSU

Math Club, October 13^th, 2015.

Title:  The Infinite Random Graph

Abstract:  Consider the following random process: start with n many points where n is a finite number, and for each pair of distinct points, flip a fair coin to decide whether to connect the points by an edge or not.  What is the probability that two random vertex-edge graphs generated by this process will be isomorphic?  For large values of n it is easy to see that getting isomorphic finite random graphs is extremely unlikely.  So what about if n = infinity?  I'll demonstrate the shocking fact (due to Paul Erdos and Alfred Renyi) that two infinite random graphs are isomorphic with 100% probability!  Moreover this probability-1 random graph has many curious properties-- for instance it contains a copy of every other countably infinite graph, and it is indestructible.  This talk is geared for undergraduates, but for graduate- and professional-level mathematicians I'll save a treat at the end regarding the construction of so-called universal metric spaces.