Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.