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
Abstract:
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
Abstract:
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.