Monday, January 13, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
The use of generating functions has provided a natural language in several areas of mathematics. In particular, Analytic Combinatorics takes benefit of complex analysis over counting formulas in order to get quantitative enumerative results. In several situations, this analysis provides a very precise picture of the combinatorial family under study.
In this talk we will show this philosophy in the context of graph enumeration. Following the pioneering work of Giménez and Noy, we will survey which is the general strategy to get enumerative estimates for the number of planar graphs and, in some cases, of graphs defined by certain minor conditions. In particular, we will emphasize the relation linking this domain with the maps enumeration setting.
We will also explain how to use analytic techniques in order to describe the qualitative picture that emerges when selecting uniformly at random a graph with a fixed size in the family under study.
If time permits, open problems and new directions will be discussed.
Colloquium - 16:00
Abstract:
In recent years there has been a growing interest in random graphs sampled uniformly from a suitable structured class of (labelled) graphs, such as planar graphs. In particular, bridge-addable classes have received considerable attention. A class of graphs is called bridge-addable if for each graph in the class and each pair u and v of vertices in different components, the graph obtained by adding an edge joining u and v must also be in the class. The concept was introduced in 2005 by McDiarmid, Steger and Welsh, who showed that, for a random graph sampled uniformly from such a class, the probability that it is connected is at least 1/e. We generalise this result to relatively bridge-addable classes of graphs, which are classes of graphs where some but not necessarily all of the possible bridges are allowed to be introduced. We start with a bridge-addable class A and a host graph H, and consider the set of subgraphs of H in A. Our connectivity bound involves the edge-expansion properties of the host graph H. We also give a bound on the expected number of vertices not in the largest component. Furthermore, we investigate whether these bounds are tight, and in particular give detailed results about random forests in balanced complete multipartite graphs.