UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Extremality of Gibbs Measure for Colorings on Trees

Mathematical Physics & Probability

Speaker: Nayantara Bhatnagar, UC Berkeley
Location: 1147 MSB
Start time: Wed, Apr 2 2008, 4:10PM

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>(2+\epsilon)D/\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. It was previously known that reconstruction is solvable (that is, in the limit, the bias at the root is non-zero) when k<(1-epsilon)D/ln(D). This is joint work with Juan Vera and Eric Vigoda.