December 1 - 2000:

On December 1, there will be another Mark Kac Seminar. This seminar 
will take place on Achter Sint Pieter nr. 200, room 012. Achter Sint Pieter 
is a street behind the Sint Pieter church in Utrecht. As there have been 
complaints about the fact that we have used the free coffee at the last meeting,
we have been asked to use the entrance at Nieuwegracht 47e. There are also 
coffee automats located near that entrance.

The speakers are


11:15-13:00 Rob van den Berg (CWI):

Absence of phase transition for the monomer-dimer model, with application to random sampling.

14:15-16:00 Heinrich Matzinger (Eurandom):

A few ideas on scenery reconstruction.




Abstract Rob van den Berg:

The monomer-dimer model originates from Statistical Physics, where it 
has been used to study the absorption of oxygen molecules on a surface, 
and the properties of a binary mixture. In the early seventies Heilmann and 
Lieb proved that, in a certain sense, this model has no phase transition. 
Their proof has a strong analytical flavour. We prove a very similar result 
by a probabilistic argument which (in my opinion) is more intuitively appealing. 
Moreover, this approach, in combination with a result of Jerrum and Sinclair, 
can be used to obtain random samples for this model in an (asymptotically) 
more efficient way. Part of the results are based on joint work with 
Rachel Brouwer.



Abstract Heinrich Matzinger:

We present a few idea's on different scenery reconstruction problems. We 
will show some methods based on simple combinatorics as well as some 
ideas which come from ergodic theory. Among others we want to explain 
the principle which leads to: "to prove that one can reconstruct a scenery 
it is enough to be able to show that there is an algorithm which reconstructs 
the scenery with probability strictly bigger than the probability to construct a 
wrong scenery". We will also briefly discuss the two dimensional case.

The basic scenery reconstruction problem can be formulated as follows: 
Assume we have a random colouring of the integer numbers. Assume there is
a random walk which walks around on those coloured integers and observes the 
colours of the colouring. In this way the random walk produces a new
sequence of colours by at each time t signalling which colour he sees at
time t. The question now is: if we are only given the observations by the
random walk can we " reconstruct" the original coloring of the integer
numbers?