Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

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

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

Previous talks by year: 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