General Information

---

Project Description

The Potts model is a probabilistic process on a graph that comes from statistical mechanics. Given a coloring of the vertices (not necessarily a typical coloring), we randomly select a vertex and recolor it to color $C$ with probability proportional to $\lambda^c$, where $c$ is the number of neighbors with color $C$ and $\lambda > 1$. If we restrict ourselves to three colors, what initial coloring is most likely to end up being all blue, for any $k$ number of steps? Intuition merits that the answer is simply starting with all blue, but it is nontrivial to show this even for $K_n$.

---

Weekly Log

Week 1:

This week I worked on a problem regarding 2-colorings (not necessarily typical colorings) of the edges of an $n$-dimensional hypercube. An antipodal path is a path between two corners in a hypercube, which, more formally speaking, is a path of length $n$ that moves once in every direction. The problem asks: Can we guarantee some upper bound on the fewest number of color changes in an antipodal path for any given 2-coloring? In order to try and break the problem down, I considered how many unique colorings there are, up to automorphisms of the $n$-dimensional hypercube, and wrote a Java program to write $S_2 \wr S_n$ as a group action on the hypercube.

As it turns out, I wasn't able to make much further progress on this, and instead turned to the Potts model as described above. I did some prelimary work on it, learning about what a coupling is, and how to solve the problem for when there are only two colors.

Week 2:

I wrote up a proper solution for the two color case, and decided to write some code. By some, I mean a full 964 lines of code that spat out a complete mess of a transition matrix. Because everything is in terms of $\lambda$, and because all probabilities are only $\textit{proportional}$ to powers of $\lambda$, every entry in the matrix is a rational expression in terms of $\lambda$. Awful. I also tried to do some case bashing to possibly find a coupling, but every such attempt results in several mean looking inequalities. To try and tackle this, I'm going to write more code that iterates through all such ways of creating a coupling, and processes the inequalities for me.

Week 3:

I wrote the code previously mentioned, but it turns out that it is not always easily decidable how to create a coupling. The question is resolved only by creating many, many cases, one for each interval of values that $\lambda$ can take on. I dropped this approach, as even if it completed, it likely wouldn't lead to a proof. Given a nice technique by my mentor, I now have a simpler, more powerful way of checking for the existence of a coupling. The proof is very nice, involving max-flow and min-cut.

In case the reader is wondering, I will define the partial ordering. First, since there is symmetry between reds and greens, we let ``stars'' represent the larger of the two, and ``daggers'' represent the smaller of the two, in terms of how many there are. Then, let $\omega_1 \succ \omega_2$ if $\omega_1$ can be reached from $\omega_2$ by changing stars to blues, daggers to blues, or stars to daggers. The reasoning is simple- first of all, it should always be better to switch to more blues, and second, mixing up the reds and greens should move the coloring away from the ``attractive'' colorings of all red/green. Unfortunately, it turns out that this quickly showed that this partial orderon the colorings does not lead to a coupling. Bad cases occur as early as $K_6$, when trying to change a dagger to a blue. Such cases are not frequent in each graph, but there are infinitely many of them.

Week 4:

I wrote more code - as in, I now have 2500 lines of code - and it turns out everything bad that could happen has happened. The partial ordering we wanted breaks completely, and after I wrote up a funky program to guess what the partial ordering is, everyone was even more confused. And soon after, the program just broke entirely. As I write this at 3:46 AM on the Monday of week 5, I wonder just how many bugs there are scattered in my code. One key aspect of the program is being able to compare polynomials in $\lambda$ to zero, whenever $\lambda > 1$. This is not as easy as one might hope. The first approach, involving numerical root-finding and a lot of hope, failed. Computer science is a scam that never should've happened. It seems silly, given that languages like Mathematica already have this built in. The problem is that the runtime for these programs, in heavily optimized Java, is already close to a whole day. Mathematica is, uh, not well-known for its speed.

Using Sturm's theorem and a home-brew algorithm for dropping all even-multiplicity roots, I think it is possible to fix this. Some proofs should be written to confirm what I'm doing makes sense, but it seems okay.

Week 5:

So it turns out there was absolutely no need for all those complicated algorithms for comparing a polynomial to zero when $x \geq 1$. All you need to do is a simple trick involving the Taylor expansion of the polynomial around $x = 1$, and it turns out that this is sufficient for 99.99% of the cases encountered. For the last few cases (if they occur at all), the user is directly asked to compute the problem. From there one might just ask Wolfram or something.

Shenanigans aside, I am completely stuck now. We were able to show that the simple approach I previously had for finding a valid partial ordering was actually sufficient to converge to one. This means that there is no coupling for any of the cases that failed before, so $K_9$ and larger complete graphs do not have a coupling. There might be a trick along the lines of ``let a pair of states walk one step, then try to couple them'', but programming that might involve yet another backtracking algorithm (for the record, I have written two backtracking algorithms already, and that is two too many).

Week 6:

We tried some more things that our mentor suggested, but each ended in failure (as is normal for this problem). I worked out a very good optimization for finding a correct partial ordering. This gave an exponential speedup that allowed me to check many other graphs, and I determined that every graph with 5 or fewer vertices does not have a monotone coupling. Other than that, not much progress was made as I was sick for a few days. It turns out that eating food and drinking water every day is a necessity, not a suggestion. It is hard to determine if this is more frustrating than research or not.

Week 7:

This week spent a good amount of time on final presentations. We decided to try seeing if some variations on the problem might pose promising results. The most interesting one was seeing if perhaps if we replace $\lambda^x$ with some other function increasing in $x$ and parameterized by $\lambda$. Surprisingly, many other functions return in the \textit{exact} same results! For example, trying varying polynomials in $\lambda$, and indexing a sequence with $x$, gives precisely the same partial orderings on $K_n$ when $n \leq 8$, and fails on precisely the same graphs otherwise.

Week 8:

We decided to write up our previous results to rigorously prove that there is no monotone coupling on the types of graphs we investigated. The paper feels quite odd- the style is simply building up some mathematical framework to tackle the problem, presenting an algorithm, proving correctness, and in a deadpan manner, declaring the output of the program. It is almost like the meat of the proof isn't there. Nevertheless, it is a proof, and there is some (unfortunate) result in there.

On suggestion from our mentor, we also tried another approach to see if there is some way of dealing with the problem by hand. If we analyze what happens in just two steps of the process, it might follow that we can generalize some types of inequalities that can prove what we're dealing with. But it looks like this again does not lead anywhere, just because the inspection of inequalities is so complex it does not seem to generalize to a pattern.

Week 9:

The last week of the REU. Feebly tried a few more related questions, but nothing worked. I also looked up some papers regarding the model, but unfortunately no one has considered this type of question, or at least published something on it. Goodbyes were said, the REU was wrapped up.

---

Additional Information

• My Mentor
  • Professor Bhargav Narayanan