November 7, 2014
Location: Janskerkhof 15a (Utrecht), room 101
The contact process: recent results on finite-volume phase transitions
The contact process is a model for the spread of an infection in a population. At any given point in time, vertices of a graph (interpreted as individuals) can be either healthy or infected; infected individuals recover at rate 1 and transmit the infection to neighbours at rate lambda. On finite graphs, the infection eventually disappears with probability one. In many cases, the time it takes for this to occur depends sensitively on the value of the parameter lambda, and this finite-volume phase transition can be linked to a phase transition of the contact process on a related infinite graph. We will survey recent works in this direction, including some general results which hold on large classes of graphs, as well as results on specific graphs, such as finite d-ary trees and the random graph known as the configuration model.
This talk includes joint work with M. Cranston, T. Mountford, J.C. Mourrat and Q. Yao.
Probabilistic cellular automata: density classification problem
Cellular automata are dynamical systems with incredibly complex behavior, generated by very simple local interaction rules. Applications range from theoretical computer science and computational complexity, to distributed computing, statistical physics and biology. Analyzing CA is difficult and until now very little is known, despite the fact that CA have been studied since the 1940's. Many open questions are related to distributed computing and resistance to noise (in the initial configuration or in the dynamics).
The main focus will be on the density classification problem. Consider an infinite graph with nodes initially labeled by independent Bernoulli random variables of parameter p. We want to design a deterministic or probabilistic CA that evolves on this graph and decides whether p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p<1/2, and only 1's if p>1/2. The difficulty is twofold: 1) it is impossible to centralize the information (nodes are indistinguishable); 2) it is impossible to use classical counting techniques (labels contain only binary information). We will present solutions to the problem in some particular cases and discuss related open problems.
This talk includes joint work with N. Fatès, J. Mairesse and I. Marcovici.