5
$\begingroup$

"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation threshold of this graph?"

Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $<\pm1,\pm2>$ or $<\pm2,\pm1>$ for the eight cases.

In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.

$\endgroup$
  • $\begingroup$ You can try using [Sagemath][1]. [Here][2] is some sample code that might get you started. [1]: cloud.sagemath.com [2]: sagecell.sagemath.org/… $\endgroup$ – fidbc Oct 8 '15 at 15:34
  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Oct 8 '15 at 17:27
  • $\begingroup$ Thanks @D.W. I was not aware of that rule. I have now deleted the question on the other site. $\endgroup$ – Math Man Oct 9 '15 at 18:40
4
$\begingroup$

First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what event signifies that percolation happens. One common option is that the top of the board is connected to the bottom of the board. For each probability $p$, you estimate the probability that this happens by doing many samplings. You then use binary search to estimate the probability $p_c$.

Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.

$\endgroup$
  • $\begingroup$ That's helpful but there are so many parameters. Board size, number of samples, test probability, which should I iterate over first to most quickly reach an accurate p value. For instance, how do I know how many samples I need to know that my p value is accurately above or below the threshold. How do I know when I need a bigger board size for a more accurate reading? $\endgroup$ – Math Man Oct 9 '15 at 20:46
  • $\begingroup$ @MathMan You're not going to get anything more detailed. Work it out on your own. $\endgroup$ – Yuval Filmus Oct 9 '15 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.