Wednesday, November 19th, 2014
3:30pm - 4:30pm, in Science 2-066

Sukhada Fadnavis

Harvard University

The shameful conjecture and related results

Abstract: Consider a random coloring c_q of the vertices of a graph G on n vertices obtained by coloring each node independently and uniformly with one of q colors. Let p(q) denote the probability that c_q is a proper coloring of G. The shameful conjecture (now a theorem due to FM Dong) concerns the monotonicity of p(q) as a function of q. In this talk I will discuss some complementary results, related coloring problems and also generalizations involving non-uniform distributions.