Probability Seminar
Monday, November 24, 2014 - 4:00pm
Malott 406
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.