Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Mittagsseminar Talk Information

Date and Time: Tuesday, January 20, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Konstantinos Panagiotou (Max-Planck-Institut für Informatik, Saarbrücken)

Random Graphs from Classes with Constraints

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.

---

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

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

---

Automatic MiSe System Software Version 1.4803M   |   admin login