Random graphs and graph limits

Meeting Details

Abstract: When does a growing sequence of graphs have a limit, and how can the limit object be described? A classic example is the countable, infinite random graph, also known as the Rado graph, which is the limit of a sequence of finite random graphs. In this talk, I will first introduce a relatively new, analytic approach to graph limits, which has become known as graphons. I will then discuss the complexity of certain universal objects (Fraissé limits from logic), when viewed as graphons. In particular, I will show that if a 0-1-valued graphon is constructed in a "tame" way (via a kind of finite extension method), then the induced fiber topology (also known as the $r_W$-topology) is not compact. This is joint work with Cameron Freer (MIT).