Name: | Davey FitzPatrick |
---|---|

Email: | davidbf@princeton.edu |

Home Institution: | Princeton University |

Project: | Three Color Potts Model |

Mentor: | Professor Bhargav Narayanan |

Consider a graph $G$ and a fixed sequence of vertices $v_1, ..., v_n$ in $G$, and fix a constant $C > 1$. Start with some coloring $\omega$ of the vertices of $G$ with three colors (red, blue, green) and perform the following procedure: update the color of $v_1$ to red, blue, or green with probabilities proportional to $C^a, C^b, C^c$, respectively, where $a, b, c$ are its numbers of red, blue, green neighbors (so a color is more likely if it is more popular among the neighbors, but every color has nonzero probability, because $C^0 = 1$). Then do the same thing for $v_2$ and so on up to $v_n$. Let $\text{Pr}_{\omega}$ be the probability that all vertices will be colored blue at the end of this process. What choice of $\omega$ maximizes $\text{Pr}_{\omega}$? We might think it obvious that it's the all blue coloring, but this is not known! When there are only two colors, red and blue, we do know that, since every time we modify $\omega$ by changing a red vertex to a blue vertex, we can see by induction that $\Pr_{\omega}$ can only be improved (call this "monotonicity"). It's also trivial when all the vertices in the sequence are distinct. But when the vertices repeat and we have three colors, we might plausibly want to make some vertices in $\omega$ red and green to hedge against large clusters of red or green that could occur later, on the basis that $C^b + C^c$ is generally much smaller than $C^{b + c}$. Some easy results in this direction are that monotonicity fails with three colors and that all blue need not be best if instead of using the function $C^x$ for the updates we use a general positive increasing function $F_{v_i}$ for each update. So what assumptions on the update functions do ensure that all blue is best, and how can we prove anything without appealing to monotonicity?

I met Professor Narayanan and learned of an approach that involved building a certain class of functions on the color space and computing their expectations as rational functions of certain parameters. If we can show that these rational functions are always positive when given appropriate inputs, then we can show that the all blue coloring is always the optimal initial coloring for the end states that we care about. We are trying to show this not just for an exponential updating function but for any family of convex functions. After clarifying a few aspects of this approach, I studied some basic Mathematica commands and started trying to understand Professor Narayanan's code. I also thought a bit more about the coin problem, in case I ended up switching to that.

I gave an initial presentation on the Potts problem. I also thought unsuccessfully about approaches to the coin problem and eventually decided to work on the Potts problem along with some other students. I studied Professor Narayanan's code but was not yet able to understand exactly what it was doing.