 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, August 26, 2014, 12:15 pm

Duration: 30 minutes

Location: LFW C4

Speaker: Konstantinos Panagiotou (Mathematisches Institut der Universität München)

## Scaling Limits for Random Graphs

Given a connected graph G with vertex set V we can associate naturally to it a metric space (V, d), where d(u,v) denotes the shortest path distance of u and v in G. If G is a random graph, then this metric space is itself a random variable, and the aim of this talk is to study its asymptotic properties when the size of G becomes large.

We consider so-called block-stable classes that can be defined as follows. Suppose that we are given a class B of 2-connected graphs, which may also include the graph consisting of a single edge. Then we let C = C(B) be the class of all connected graphs whose blocks, i.e., maximal subgraphs that contain no cut-vertex, are in B. For example, if B is the class of all 2-connected planar graphs (and the single edge), then C is the class of all connected planar graphs; if B is the class that contains only the graph that consists of a single edge, then we recover the class of trees.

For a random graph from a block-stable class with n vertices we study the associated random metric space. For a general class of choices for B we show that it converges (in a well-defined sense) to an object called the continuum random tree, and obtain as a corollary for example the distribution of the diameter. In this talk I will give an informal picture of this object and describe the intuition behind its seminal construction by Aldous.

Joint work with B. Stufler and K. Weller.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks