#
Monday Lecture and Colloquium

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

###
Mark Jerrum - Queen Mary College, University of London

###
The computational complexity of the Tutte polynomial

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

###
Amin Coja-Oghlan - Humboldt Universität zu Berlin

###
Counting Connected Graphs via the Probabilistic Method

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

Letzte Aktualisierung:
01.12.2006