Anthony Bonato: The new world of infinite random geometric graphs

Place: Fields Institute (Room 210)

Date: April 20, 2018 (13:30-15:00)

Speaker: Anthony Bonato

Title: The new world of infinite random geometric graphs

Abstract:

The \emph{infinite random} or \emph{Rado graph} $R$ has been of interest to graph theorists, probabilists, and logicians for the last half-century. The graph $R$ has many peculiar properties, such as its \emph{categoricity}: $R$ is the unique countable graph satisfying certain adjacency properties. Erd\H{o}s and R\'{e}nyi proved in 1963 that a countably infinite binomial random graph is isomorphic to $R$.

Random graph processes giving unique limits are, however, rare. Recent joint work with Jeannette Janssen proved the existence of a family of random geometric graphs with unique limits. These graphs arise in the normed space $\ell _{\infty }^{n}$, which consists of $\mathbb{R}^{n}$ equipped with the $L_{\infty }$-norm. Balister, Bollob\'{a}s, Gunderson, Leader, and Walters used tools from functional analysis to show that these unique limit graphs are deeply tied to the $L_{\infty }$-norm. Precisely, a random geometric graph on any normed, finite-dimensional space not isometric $\ell _{\infty}^{n}$ gives non-isomorphic limits with probability $1$.

With Janssen and Anthony Quas, we have discovered unique limits in infinite dimensional settings including sequences spaces and spaces of continuous functions. We survey these newly discovered infinite random geometric graphs and their properties.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.