CanaDAM 2013
Université Memorial de Terre-Neuve, 10 - 13 juin 2013

Probabilistic Combinatorics
Responsable et président: Mike Molloy (University of Toronto)

TOM BOHMAN, Carnegie Mellon
Self-correcting estimates for the triangle free process  [PDF]

The triangle-free process begins with an empty graph on $n$ vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. In this talk we discuss how the graph produced by $i$ steps of the triangle-free process resembles a graph chosen uniformly at random from the collection of all graphs on $n$ vertices with $i$ edges. As a Corollary we get an improved lower bound on the Ramsey number $R(3,t)$.

Joint work with Peter Keevash. Similar results were obtained simultaneously and independently by Fiz Pontiveros, Griffiths and Morris.

AMIN COJA-OGHLAN, Goethe University
Chasing the k-SAT threshold  [PDF]

Let F be a random Boolean formula in conjunctive normal form over n Boolean variables with m clauses of length k. The existence of a (non-uniform) sharp threshold for the satisfiability of such formulas is well known [Friedgut 1999]. However, despite considerable effort the precise location of this phase transition remains unknown for any $k>2$. The best previous upper and lower bounds differ by an additive $k\ln 2/2$ [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.

DAVID GALVIN, University of Notre Dame
Colouring regular bipartite graphs, cubes and grids  [PDF]

What can we say about a uniform $q$-colouring of a regular bipartite graph? Quite a bit, it transpires, despite the question's vagueness. For example, if $q$ is even then with high probability all colour classes are (essentially) the same size.

Given more structure, we can say more. For example, we have a precise description of the colour classes in a random colouring of the hypercube.

Beyond the hypercube is the integer lattice, and a decades old conjecture of Kotecky that has only recently seen progress.

In part joint work with J. Engbers, J. Kahn, D. Randall and G. Sorkin

MIKE MOLLOY, University of Toronto
Clusters of solutions to random linear equations  [PDF] [SLIDES]

Strong evidence from statistical physics indicates that for many models of random constraint satisfaction problems (eg. random k-SAT, random graph colouring) the set of solutions partitions into {\em clusters}. We can move throughout the solutions of a cluster by making small local changes, but moving to another cluster requires a large global change.

Clustering is best understood, rigorously, for a random system of boolean linear equations, each on exactly k variables. We discuss this model, including when the density is within the clustering window.

This includes joint work with Dimitris Achlioptas and with Jane Gao.

BRUCE REED, McGill University
Variants of the Erdos-Sos Conjecture  [PDF]

The Erdos-Sos Conjecture states that if a graph has average degree exceeding t-2 then it contains every tree with t vertices as a subgraph. This result was proved by Simonovitz and Szemeredi for large t. We discuss some variants of the conjecture which replace average degree with minimum degree and/or replace subgraph with minor.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Memorial de Terre-Neuve