Jeff Kahn - Rutgers University, NJ

Random independent sets

Uniform and more general "hard-core" distributions on the collection of independent sets of a large graph are of interest in their own right (in statistical physics as well as combinatorics), and have also found some combinatorial uses. We will discuss some questions, results and connections involving such distributions. Possible key words and phrases: phase transition, chromatic index, entropy, Dedekind's Problem.

Colloquium - 16 Uhr s.t.

Manuel Bodirsky - Humboldt-Universität zu Berlin

Algorithms for period problems and applications to the analysis of Markov chains

Abstract: Stable state distributions play an important role for the theory of Markov chains, since they are related with long-run properties of probabilistic systems. However, there are Markov chains where the probability to be in a certain set of states converges, but the Markov chain has no stable state distribution.

In this talk I present how to reduce convergence problems on non- ergodic Marcov chains to equivalent combinatorial period problems, and show how number theory helps to solve these problems.