Phase transitions for random structures have been of great interest in the community of discrete mathematics in the last decades. After a brief introduction into parts of this area we shall focus on two such phenomena.

First, we will consider a sharp threshold for van der Waerden’s theorem. A subset $W$ of integers satisfies the property vdW($k$), if any two coloring of $W$ yields a monochromatic arithmetic progression of length $k$.

We consider the binomial random subset of the first $n$ integers and show that as the density increases, it exhibits a swift change from not having the property vdW($k$) to having it.

Second, we discuss the hard-core distribution for finite regular graphs. Given a graph $G$ and an activation parameter $\lambda>0$, this distribution selects a random independent set $J$ of $G$ with probability proportional to $\lambda^{|J|}$. For bipartite graphs $G$ and assuming a mild spectral condition, we show that even for rather small $\lambda$ the random independent set must be essentially contained in one of the partition classes.

The talk will be in large part introductory and non-technical. The first part is based on a joint work with E. Friedgut, M. Schacht and Y. Person and the second on a joint work with P. Tetali.

Pontificia Universidad Católica de Chile (PUC-Chile)

Av. Vicuña Mackenna 4860, Macul,

Santiago – Chile

(+56 2) 2354 5779

Facultad de Ciencias Físicas y Matemáticas (FCFM)

Universidad de Chile

Beauchef 851, Edificio Norte, Piso 7,

Santiago – Chile