Past Combinatorial Theory Seminar

In Dept of Statistics

Recently random planar structures, such as planar graphs and outerplanar graphs, have received much attention. Typical questions one would ask about them are the following: how many of them are there, can we sample a random instance uniformly at random, and what properties does a random planar structure have ? To answer these questions we decompose the planar structures along their connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating funtions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the so-called recursive method: We derive recursive counting formulas along the decomposition, which yields a deterministic polynomial time algorithm to sample a planar structure that is uniformly distributed. In this talk we show how to apply these methods to several labeled planar structures, e.g., planar graphs, cubic planar graphs, and outerplanar graphs.

In Dept of Statistics

In Corpus

We will discuss the mixing rate of the standard random walk on the giant

component of the random graph G(n,p). We tie down the mixing rate precisely

for all values of p greater than (1+c)/n for any positive constant c. We need

to develop a new bound on the mixing time of general Markov chains, inspired

by and extending work of Kannan and Lovasz. This is joint work with Nick

Fountoulakis.