On the effect of randomness on planted 3-coloring models

The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic edges). For a sufficiently large constant $c$, Alon and Kahale [SICOMP 1997] presented a spectral algorithm that finds (with high probability) the planted 3-coloring of such graphs whenever $d > c\log n$. Perhaps more surprisingly, they also extend this algorithm to handle the case $d > c$, where in this regime it finds a legal 3-coloring (not necessarily the planted one). It is natural to ask whether the algorithm of Alon and Kahale works whenever the host graph $H$ is a $d$-regular spectral expander (chosen by an adversary). Likewise, one may ask whether the planted 3-coloring needs to be random, or may we allow an adversary to plant a balanced 3-coloring of his choice after seeing $H$. In this talk we shall review the algorithm of Alon and Kahale, while addressing questions of the above nature. Joint work with Roee David.