A little random graph theory

If I have a finite connected graph, and I imagine a bug walking about randomly from one node to some connected node then we may ask where the bug is likely to be found. If the bug chooses among the available arcs randomly and independently, then the probability of a bug being at a node is proportional to how many nodes are connected to that node—to the degree of the node.

Imagine the immense graph of all 10 by 10 bit arrays restricted to some local rule, as above. Two nodes on this graph are connected if the two corresponding bit arrays differ by just one bit. We can imagine a bug wandering about this graph. Surprisingly this is a more tractable computing problem, even though it is conceptually farther out. To designate a node on the graph we just construct a bit array. To visit a random connected node we merely select a random bit from the array and see if we can flip it without violating the array restriction. Eventually we will have selected a random point on the graph. When this is done with the “no adjacent 1’s” rule, the resulting bit array has significant patches of checker board patterns; the checker board being the most dense pattern that conforms to the rule. I don’t know if these patches grow indefinitely. I think not.

Alas there is a serious bug already at this point. I noted that the bug’s average dwell time at a node was proportional to the node’s degree. Not all 10 by 10 patterns are of the same degree! It is easy to compute the degree of a node but not yet clear how how to exploit this to select nodes randomly. Perhaps it is possible to bias the bug’s choice towards nodes with lesser degree. That may make it unlikely to get to the truly random part of the graph.

Such techniques work in many cases of interest but not for the ice case, for the graph is not even locally connected; each configuration is a long way, Hamming wise, from the next nearest valid configuration. For ice it might suffice to find a more generous concept of “connected”. For instance it might work to find some small number of neighboring molecules that can be simultaneously turned without breaking the rules. The bug remains to compensate somehow for the fact that these available transitions are not equinumerous from each valid configuration.

These techniques do not yet answer the question of how many valid configurations there are. Some physics questions can be answered, however, with a random sample of the total set.


I think I know how to compute a good estimate of the number of constrained patterns. In the hyper graph of patterns, observe how many neighbors each pattern has on the average. As you pick a bit to see if it can be flipped, note how often it can be. If the probability is 1 then the number of conforming patterns of an area with n points is 2n. I conjecture that if a randomly selected bit from a randomly selected conforming pattern can be flipped with probability p to a still conforming pattern, then the number of conforming patterns is approximately 2pn n bit arrays. This is clearly true for p=0 or p=1.

This little program tests the conjecture for the fibonacci case mentioned above. In this case a selected bit can be flipped with p = .55 . 2(0.55)*200 = 2110 whereas F110 = 1.618200. log(2110) = 69.31 and log(F110) = 96.24. This is in fair agreement with the conjecture.


See this for some exact solutions.