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

Monday, April 20, 2009

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041

Lecture - 14:15

Stefan Felsner - TU Berlin

Sampling from Distributive Lattices - The Markov Chain Approach

For many fundamental sampling problems, the best approach for solving them is to take a long enough random walk on an appropriately Markov chain and return the final state of the chain. A variety of techniques have been developed to prove how long "long enough" is, i.e., to bound the mixing time. If we want to sample from the elements of a distributive lattice a monotone coupling from the past can be used to generate a perfect sample. In this case "long enough" is just the number of steps the algorithm needs until it stops. We introduce this method and review known bounds for the mixing time.
In a second part we concentrate on a specific example (Widom-Rowlinson model with q=2) and show a proof for rapid mixing. The method based on block coupling requires the use of nontrivial tools from probability (Strassen's Theorem) and combinatorics (Ahlswede-Daykin inequality).
(joint work with Peter Winkler and Daniel Heldt)

Colloquium - 16:00

Antonios Varvitsiotis - Athen

Counting the number of embeddings of minimally rigid graphs

We show how to exploit the Henneberg constructions of Laman graphs and of the 1-skeleta of simplicial polyhedra in order to compute bounds on their respective number of Euclidean embeddings. This approach leads to upper bounds of $2^{k+1} 4^{n-k-5}$ for the planar and $2^{k+1}8^{n-k-5}$ for the spatial case, where $k=\#$ of degree-2 and degree-3 vertices, respectively. We also establish general lower bounds of about $(2.37)^n$ and $(2.52)^n$ for the planar and spatial cases respectively. These bounds are tight for all cases up to $n=8$ in the plane and up to $n=7$ in space. This is joint work with Pr. Ioannis Z. Emiris.

Letzte Aktualisierung: 14.04.2009