Large networks, graph limits, and why are they useful

Gergen Lectures Seminar

Laszlo Lovasz (Eötvös Loránd University)

Tuesday, March 4, 2014 -
4:30pm to 6:30pm
Location: 
Physics 128

If you have a very large network (which may be deterministic or the result of some random procedure), we may want to approximate it by a smaller object, or by an infinite (analytic) object. The former question is related to Szemer\'edi's Regularity Lemma and its variants, the latter, to "graph limits". A theory of convergent graph sequences and their limits has been worked out by Benjamini and Schramm (for graphs with bounded degree) and by Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi (for dense graphs). Focusing on the dense case, I will describe the motivation for graph limit theory and some basic facts.

Last updated: 2018/06/23 - 2:16pm