Random graphs and graph limits

Logic, Games, and Graphs Seminar

Meeting Details

For more information about this meeting, contact Kristin Berrigan, Andrew Belmonte, Jan Reimann, Linda Westrick.

Speaker: Jan Reimann, Penn State University

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).

Room Reservation Information

Room Number: 106 McAllister

Date: 03/13/2019

Time: 2:30pm - 3:30pm