Student: Tony Zeng
Office: CoRE 446
School: Yale University
E-mail: tony.zeng@yale.edu
Suppose we start with a colouring of a graph \(G\) (not necessarily proper) with three colours, red, blue and green and a parameter \(C > 1\). We update this colouring a fixed number of times as follows. Pick a vertex at random and resample its colour based on its neighbours: if it has t blue neighbours, then the probability that its new colour is blue is proportional to \(C^t\), and similarly for the two other colours. Since \(C > 1\), notice that vertices prefer to be coloured similarly to the majority of their neighbours. We're interested in how likely the graph is to be coloured entirely blue at the end. What's the starting state that makes this most likely? Surely: colour everything blue! But we don't know this. If we only have two colours instead of three, we can show this and it's not very hard.
5/29 - 5/31
Beginning investigations into the Potts Model. Established basic intuitions for \(K_1\) and \(K_2\) with regards to their respective state graphs and transition matrices. I also began reading into simple coupling schemes in preparation for application to the 2-color variant of the Potts Model.
6/3 - 6/7
I bashed out transition matrices for relatively simple graphs such as \(K_n\), \(C_n\), and \(S_n\) for small \(n\). All of these turned out to be much messier than I would have liked. Worked on some coupling schemes for small \(C_n\) and \(S_n\), but this didn't go anywhere fruitful. Everything resulted in certain crucial inequalities not always being in the necessary direction.
6/10 - 6/14
We have decided to focus our attentions on \(K_n\). Some supplemental reading has revealed to us that a coupling is possible iff for some partial ordering of states, any \(S_1 \geq S_2\) satisfies \(P(S_1 \rightarrow U) \geq P(S_2 \rightarrow U)\) for all up-sets \(U\). This led us to manually check several inequalities corresponding to different cases of states and up-sets. We unfortunately found cases, the smallest of which was in \(K_6\) where this was not true.
6/17 - 6/21
Addressing bad cases. Specifically, adjusting the poset structure to circumvent the problematic inequaities. This involves either adjusting the shape of posets or simply removing relations between problematic states. Beginning work on a C++ port of Adam's code to speed up computations.
6/24 - 6/28
Reconsidering different types of graphs. The most promising other type of graph of the star graph \(S_n\). Unfortunately the states are nowhere near as nice as \(K_n\), and establishing a partial order is tricky.
7/1 - 7/5
Learned and used Mathematica to generate all connected non-isomorphic graphs of \(n\) vertices for \(3 \leq n \leq 7\). Also considered the partial ordering generated by testing for coefficient positivity of the state comparison polynomial. This partial ordering is reminiscent of our original but without horizontal relations, i.e. states with the same number of blues are incomparable.
7/8 - 7/12
Began changing perspective to consider fixed sequences of vertex updates. Hopefully this will allow us to understand general sequences of vertex updates as well. Worked on final presentations.
7/15 - 7/19
Decided to write up all results in paper format. In particular, that the conjecture is true for \(K_n\) for \(1 \leq n \leq 8\) and that there is no monotone coupling for certain other graphs. We would guess that there is no monotone coupling for any other graphs. We tried to take another look at isolating the problem to 2 updates, but the probabilities and associated inequalities don't seem to reveal anything particularly enlightening.