Return to Answer

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected. This is equivalent to saying that there is a (planar) subgraph, shaped like a polyomino, whose perimeter consists of broken edges.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Therefore, $$q\le n^2\sum_{k=4}^{2n^2}3^kp^k\le n^2 (3p)^4/(1-3p).$$ If we assume that $p=o(1)$, then we may estimate $q\le n^2 \cdot 82p^4$.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/2$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/2}\ge 1-e^{-n^2p^4/2}\ge n^2p^4/4$$ for $n$ sufficiently large.

If we still assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{16}{n^4p^7}\le \frac{16n^{10}}{c^7}.$$

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected.

Edit: According to the comments below, a disconnected subgraph of the torus grid has a component with at most two boundary components. Moreover, the boundary is either a contractible curve, in which case the component is shaped like a polyomino, or, the boundary consist of two parallel noncontractible curves, each of lenght at least $n$.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Similarly, up to translation, there are at most $3^k$ noncontractible curves of length $k$, and a pair of such curves may be placed in at most $n^4$ different ways. Therefore,

$$q\le n^2\sum_{k=4}^{2n^2}3^kp^k + n^4\sum_{k=2n}^{2n^2}3^kp^k \le n^2 (3p)^4/(1-3p) + n^4 (3p)^{2n}/(1-3p).$$ If we assume that $p=o(1)$, then for $n$ sufficiently large, we have $q\le n^2 \cdot 82p^4$; the contribution of noncontractible separators is exponentially small.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/2$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/2}\ge 1-e^{-n^2p^4/2}\ge n^2p^4/4$$ for $n$ sufficiently large.

If we still assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{16}{n^4p^7}\le \frac{16n^{10}}{c^7}.$$

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected. This is equivalent to saying that there is a (planar) subgraph, shaped like a polyomino, whose perimeter consists of broken edges.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Therefore, $$q\le n^2\sum_{k=4}^{2n^2}3^kp^k\le n^2 (3p)^4/(1-3p).$$ If we assume that $p=o(1)$, then we may estimate $q\le n^2 \cdot 82p^4$.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/4$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/4}\ge 1-e^{-4n^2p^4}\ge 2n^2p^4$$ for $n$ sufficiently large.

If we stil assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{1}{4n^4p^7}\le \frac{n^{10}}{4c^7}.$$

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected. This is equivalent to saying that there is a (planar) subgraph, shaped like a polyomino, whose perimeter consists of broken edges.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Therefore, $$q\le n^2\sum_{k=4}^{2n^2}3^kp^k\le n^2 (3p)^4/(1-3p).$$ If we assume that $p=o(1)$, then we may estimate $q\le n^2 \cdot 82p^4$.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/2$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/2}\ge 1-e^{-n^2p^4/2}\ge n^2p^4/4$$ for $n$ sufficiently large.

If we still assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{16}{n^4p^7}\le \frac{16n^{10}}{c^7}.$$

This is an approximation of the answer.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected. This is equivalent to saying that there is a (planar) subgraph, shaped like a polyomino, whose perimeter consists of broken edges.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Therefore, $$q\le n^2\sum_{k=4}^{2n^2}3^kp^k\le n^2 (3p)^4/(1-3p).$$ If we assume that $p=o(1)$, then we may estimate $q\le n^2 \cdot 82p^4$.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/4$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/4}\ge 1-e^{-4n^2p^4}\ge 2n^2p^4$$ for $n$ sufficiently large.

If we stil assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{1}{4n^4p^7}\le \frac{n^{10}}{4c^7}.$$

This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.

I will assume that $\delta=1/m$, for some large positive integer $m$. I will also assume a discrete model, where in each basic interval $[i/m, (i+1)/m]$, every edge breaks independently with probability $p=\delta=1/m$.

Now I estimate the probability $q$ that at one basic interval, the graph gets disconnected. This is equivalent to saying that there is a (planar) subgraph, shaped like a polyomino, whose perimeter consists of broken edges.

For every $k$, there are at most $3^k$ fixed polyominoes with perimeter of length $k$, and each can be positioned in $n^2$ ways. Also, every polyomino has perimeter of length at least $4$. Therefore, $$q\le n^2\sum_{k=4}^{2n^2}3^kp^k\le n^2 (3p)^4/(1-3p).$$ If we assume that $p=o(1)$, then we may estimate $q\le n^2 \cdot 82p^4$.

Now we may estimate the expected time when the graph is connected as follows: $$T\ge\frac{1}{m}\sum_{i=1}^{\infty}i(1-q)^i=p\frac{1-q}{q^2}\ge\frac{1-q}{82^2n^4p^7}.$$

If $q$ is very small, that is, if $p\le c/n^2$ for a very small constant $c$, then we may write $$T\ge\frac{1}{6725n^4p^7}\ge\frac{n^{10}}{6725c^7}.$$

For the lower bound on $q$, we may consider $n^2/4$ independent vertices (if $n$ is even). Each gets separated with probability $p^4$, so $$q\ge 1-(1-p^4)^{n^2/4}\ge 1-e^{-4n^2p^4}\ge 2n^2p^4$$ for $n$ sufficiently large.

If we stil assume that $p\le c/n^2$, then $$T\le\frac{p}{q^2}\le\frac{1}{4n^4p^7}\le \frac{n^{10}}{4c^7}.$$