4
$\begingroup$

Suppose that I am given the graph $G = (V,E)$ where $V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $ and there is an edge between two vertices $(n,m)$ and $(n',m')$ if and only if $\vert n-n'\vert + \vert m-m'\vert = 1$.

Suppose that we remove some arbitrary edges between vertices $(n,m)$ and $(n',m')$ with $n, n' \leq N$.

Now, on the remaining graph, consider Bernoulli edge percolation with parameter $p \in [0,1]$. That is that we delete each of the remaining edges with probability $1-p$. Prove or disprove that, no matter what edges I deleted in the beginning, then the probability that there is a path from $(N+1,N+1)$ to a vertex of the form $(2N+1, m)$ for $m \in \{ 1, 2, \dots 2N+1 \}$ is larger or equal than the probability that there is a path to a vertex of the form $(1, m)$ for $m \in \{ 1, 2, \dots 2N+1 \}$.

See here for a related counterexample: Are there more paths exiting a box in $\mathbb{Z}^2$ to the right if I remove some edges to the left.

$\endgroup$
7
  • $\begingroup$ Nice problem, so $G$ is just like a lattice on a square of sides $2N + 1$ if i understand correctly? There is an edge from $v$ to $w$ iff $w$ lies immediately to the top/left/right/bottom of $v$. $\endgroup$
    – Nate River
    Commented Oct 14 at 22:55
  • $\begingroup$ What does it mean to remove arbitrary edges between two vertices? $\endgroup$
    – Nate River
    Commented Oct 14 at 22:57
  • $\begingroup$ It means that you delete the edges from the beginning before sampling additional edges to remove. $\endgroup$ Commented Oct 15 at 7:43
  • $\begingroup$ Can it be thought of in terms of some effective probability of open edges ($p_e$) on the left side which is less than $p$? $\endgroup$
    – Alapan Das
    Commented Oct 15 at 8:20
  • $\begingroup$ @AlapanDas: No, instead I ask if you can carefully remove some edges on the left so that the probability of getting a path to the left side increases. $\endgroup$ Commented Oct 15 at 14:51

0

You must log in to answer this question.

Browse other questions tagged .