- On Whether a Monochromatic Initial State is Optimal for a Monochromatic Final State in a Systematic Scan Order Glauber Dynamics for a Generalized Three-Color Potts Model
- Project Year:
2020
- REU Student (s):
Filip Cermak | Charles University (Prague, Czech Republic)
| David FitzPatrick | Princeton University NJ
- Student 1 Institution:
Princeton University
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Bhargav Narayanan
- Project Mentor Area:
Mathematics
- Project Abstract:
We consider a variant of a problem posed by Lubetzky: given an arbitrary vertex coloring of a graph, if we randomly update the color of each successive vertex in a given sequence, so that at each step, each color has probability proportional to λx with x its count among the neighbors, then what initial coloring maximizes the probability of all vertices being the same color, say blue, at the end? If there are only two colors, there is a trivial proof by coupling that the all blue initial coloring is best. For more colors, we show that this is still true under certain assumptions on the graph, but we construct a counterexample in general. We build our counterexample by first appealing to a generalized setting, where the graph and the update function λx change at each step, and then repeatedly modifying it until it works in the original setting. The techniques we will use include identifying and exploiting ergodic Markov chains within our process and implementing a digraph within a standard graph by ensuring that the neighbors that we want to be the inneighbors vastly outnumber the neighbors that we want to be the outneighbors for every vertex.
