skip to content

Extremality of Gibbs measure for colorings on trees

Friday 28th March 2008 - 14:35 to 15:05
INI Seminar Room 1

We consider the problem of extremality of the free boundary Gibbs measure for k-colorings on the tree of branching factor D. Extremality of the measure is equivalent to reconstruction non-solvability, that is, in expectation, over random colorings of the leaves, the conditional probability at the root for any color tends to 1/k as the height of the tree goes to infinity. We show that when k>2D/ln(D), with high probability, conditioned on a random coloring of the leaves, the bias at the root decays exponentially in the height of the tree. This is joint work with Juan Vera and Eric Vigoda.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons