| [home] - [up] |
Abstract: The permanent of a matrix is a multivariate polynomial that is similar to the more familiar determinant, except that all monomials are given positive sign. In contrast to the determinant, which can be evaluated efficiently using Gaussian elimination, the permanent is known to be #P-complete, even in the special case of a 0,1-matrix. This classical result of Valiant almost certainly rules out a polynomial-time algorithm for computing the permanent of such a matrix exactly.
However, the question of whether the permanent of a 0,1-matrix can be efficiently approximated was open until 2000. I shall present a "fully-polynomial randomised approximation scheme" for the permanent of a 0,1-matrix (more generally, of an arbitrary matrix with non-negative entries). In the process, I hope to convey some of the ideas that are employed in the analysis of algorithms of this type, particularly in bounding the "mixing time" of complex Markov chains. Inevitably, in a presentation of this length, I shall be ignoring most of the technical detail. I'll say more about the proof techniques in subsequent, more technical talks.
The work I describe is joint with Alistair Sinclair (Berkeley) and Eric Vigoda (Chicago).
Mark Jerrum will give two more technical seminar presentations in the Oberseminar of Prof. Ziegler's group at TU Berlin, MA 645, at 2pm on Tuesday, Feb. 3 and Thursday, Feb. 5.
Colloquium - 16:00
Abstract: We study upper and lower bounds for the number of spanning trees of a planar graph. We present a new method based on transfer matrices for computing the asymptotic number of spanning trees of some recursively constructible families of graphs. Upper-bounds for the number of spanning trees of planar triangulated graphs, and planar graphs with girth 4 and 5, will be discussed.
The motivation arises from trying to embed polyhedra on a 3D-grid using the Maxwell-Cremona lifting.