December 11 , 2006
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
The (classical) Tutte polynomial of a graph G is a two-variable
polynomial T(G;x,y) that encodes much information about G. The number of
spanning trees in G, the number of acyclic orientations of G and the partition
function of the q-state Potts model are all specialisations of the Tutte
polynomial. From a complexity-theoretic point of view, "mapping the Tutte
plane" amounts to determining the computational complexity of evaluating
T(G;x,y), given G, for each rational pair (x,y). For exact computation, the
mapping was done in detail by Jaeger, Vertigan and Welsh. For approximate
computation (within specified relative error) much less is known, though some
progress has recently been made.
The talk will start by introducing the Tutte polynomial, and describing
what is currently known. More recent work (with Leslie Goldberg,
Liverpool) will then be covered in more detail, including sketch proofs.
I'll assume only a basic knowledge of computational complexity theory.
Colloquium - 16:00
Abstract:
In this talk we will study a fundamental enumerative problem: what is the number of connected graphs with n vertices and m edges?
While this question can be answered using enumerative methods, here we will employ probabilistic techniques.
Following Erdös and Rényi, we first investigate the regime $m\sim\frac12\ln n$.
Then, we make a detour to the component structure of random graphs $G_{n,m}$ with $m=O(n)$ edges
and study the number of vertices and edges in the largest component of the random graph.
More precisely, we derive a local limit theorem for these parameters.
Finally, we will see that this local limit theorem readily yields the desired formula for the number of conncected graphs.
Parts of this talk are based on joint work with Michael Behrisch and Mihyun Kang.