Probabilistic combinatorics
Organizer and Chair: Amin Coja-Oghlan (Goethe University Frankfurt/Main, Germany)
[PDF]

NIKOLAOS FOUNTOULAKIS, School of Mathematics, University of Birmingham
Random graphs on the hyperbolic plane  [PDF]

We will give an overview on random geometric graphs on the hyperbolic plane. We argue that the hyperbolic geometry essentially makes such random graphs a dependent version of the well-known Chung-Lu model. Thus, the degree distribution has a power law tail. We will focus on the component structure of these graphs as well as on the distance between two random vertices. Our results imply that for the regime where the exponent of the power law is between 2 and 3, the random graph has a giant component which forms an ultra-small world.

(This is joint work with M.Bode and T.M\"uller.)

Tree packings and graceful tree labelings via semirandom method  [PDF]

Using the semirandom method, we prove asymptotic versions of the Tree packing conjecture of Gyarfas from 1976 and of Ringel from 1963, and of the graceful tree labeling conjecture of Rosa from 1966. The work on the tree packing conjecture is joint with Julia BÃ¶ttcher, Diana Piguet, and Anusch Taraz. The work on the graceful tree conjecture is joint with Anna Adamaszek, Michal Adamaszek, Peter Allen, and Codrut Grosu.

MIKE MOLLOY, University of Toronto
Solution clusters for locked constraint satisfaction problems  [PDF]

Mezard and Zdeborova introduced the class of locked Constraint Satisfaction Problems, and studied random instances with a truncated Poisson degree sequence. Using nonrigorous techniques from statistical physics, they discovered a threshold density: Below it, every solution can be transformed into any other solution changing only a few (polylog) variables at a time. Above it, every solution differs from all but O(1) other solutions on a linear number of variables. This is an example of the clustering phenomenon. We provide a rigorous proof for k-XORSAT; i.e. a system of linear boolean equations.

Joint work with Lenka Zdeborova.

DANIEL REICHMAN, Cornell University
Contagious sets in pseudorandom and random graphs  [PDF]

In bootstrap percolation, a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors, where $r>1$ is the activation threshold.

A contagious set is a set whose activation results with the entire graph being active. Given a graph $G$, let $m(G,r)$ be the minimal size of a contagious set.

We review bounds on $m(G,2)$ in $d$-regular graphs with pseudorandom properties as well as the random graph $G(n,p)$ and mention some open problems.

Based on works with Amin Coja Oghlan, Uriel Feige and Michael krivelevich.

LUTZ WARNKE, University of Cambridge
The phase transition in Achlioptas processes  [PDF]

We consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges. Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We shall discuss why, for a large class of rules, the percolation phase transition (with respect to the growth of the largest component) is qualitatively comparable to the classical ErdÅ‘s-RÃ©nyi process.

Based on joint work with Oliver Riordan.