Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 20, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Konstantinos Panagiotou (Max-Planck-Institut für Informatik, Saarbrücken)
In this talk we will discuss properties of graphs drawn uniformly at random from graph classes with structural constraints, like for example planar graphs. In particular, denote for a graph G by b(s; G) the number of blocks (i.e. maximal biconnected subgraphs) of G that contain exactly s vertices, and let lb(G) be the number of vertices in the largest block of G. We show that under certain natural and easy to verify assumptions on the graph class under consideration, there are only two ways how a random graph with n vertices looks like with high probability:
I) lb(G) < log n
II) lb(G) ~ cn for some c depending on the graph class, and the second largest block contains n^a vertices, where a < 1.
Moreover, we provide sharp concentration results for b(s; G) for all admissible s. As corollaries we show that random planar graphs are of type (II), while for example K_4-minor free graphs are of type (I). We will discuss some implications of this results towards a random graph theory for constrained graph classes, and talk about the major remaining challenges.
Some of the presented results are joint work with Angelika Steger.
Automatic MiSe System Software Version 1.4803M | admin login