PIMS-UVic Discrete Math Seminar: Anthony Quas

Given a collection of points S in a metric space and a probability p in (0,1), one can make a random graph by independently joining any pair of points in S that are less than 1 apart by an edge with probability p; and no edge with probability 1-p. Points 1 or more apart are never joined by edges. In a surprising paper, Bonato and Janssen showed that if the metric space is the real line and S is a randomly chosen countable dense set, then the random graphs obtained by this process are almost surely isomorphic. Furthermore, somewhat like the Rado graph, the isomorphism class of the graph obtained does not depend on the particular p or the particular S (with probability 1). They call the resulting graph the Geometric Rado graph on R. Bonato and Janssen also showed that this Rado property fails in two dimensions.

I will discuss Bonato and Janssen’s results, and then describe some joint work, extending the results to larger metric spaces. One of the motivating questions is “which features of the metric space and/or the vertex set S are revealed by the isomorphism class of the graph?”