1
$\begingroup$

Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with probability $p$. A lot of research has focused on determining $p_C$, the critical threshold probability of having a connected component of size $\Omega(n^2)$.

I am interested in a related problem. Define the width of a subgraph of the grid to be the minimal distance between a vertex on the left side and a vertex on the right side of the grid.

Now, let $p>p_C$. What can be said about the expected width of $G_p$?

I am a newcomer to the field, so I am looking for some expert advice: Is this problem solved, known and open, or neither?

$\endgroup$
  • $\begingroup$ The right keyword seems to be "chemical distance". Perhaps the following references are relevant: Antal, P., & Pisztora, A. (1996). On the Chemical Distance for Supercritical Bernoulli Percolation. The Ann. Prob., 24(2), 1036-1048, and Grimmett, G. R., & Marstrand, J. M. The supercritical phase of percolation is well behaved. Proc. R. Soc. Lond. A, 430(1879), 439-457. $\endgroup$ – Timothy Budd Feb 3 at 19:19
1
$\begingroup$

See Aizenman, M.; Burchard, A. Hölder regularity and dimension bounds for random curves. Duke Math. J. 99 (1999), no. 3, 419--453. https://arxiv.org/abs/math/9801027

$\endgroup$

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.