Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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