An elementary question in bond percolation

Question

Consider a locally finite, connected graph and "bond (edge) percolation" on this graph. Each edge is open with probability $p.$ There is a parameter $\alpha$, $0<\alpha<1.$

The question: Is it possible to divide the set of nodes into "sources" and "receivers" so that the following two conditions are fulfilled?

(i) For any "receiver", the probability that it ends up in a connected component with a "source" is larger or equal than $\alpha$;

(ii) For any "source", the probability that it ends up in a connected component with another "source" is smaller than $\alpha$.

I can prove, by elementary methods, that this is true for linear graphs, finite or infinite, complete graphs, and star graphs (graphs, in which $n-1$ nodes have degree $1$ and one node has degree $n-1$).

Also, there are many other situations in which existence is trivial. In a finite graph, when $p$ is close to zero, the solution is that every node is a source, and the set of receivers is empty. If the graph is $\mathbb{Z}^2,$ then, if percolation function $\theta(p)>\sqrt{\alpha},$ then making one node a source and all other nodes receivers is a solution. (The case of an infinite graph might be very different. Interestingly, it is possible to have $p>\frac{1}{2}$ and a solution with an infinite number of sources on $\mathbb{Z}^2$.)

I wonder if this is true for any finite (and locally finite) graph?

Answer 1

Here is an outline of a counterexample if the graph is the infinite lattice (say, $\mathbb Z^2$) and $p$ is sufficiently close to one.

Here, the meaning of "sufficiently close" will be clear from the below, as we will need some assumptions to hold, and for $p$ in an appropriate range all those assumptions can be checked by variations of the Peierls argument.

Provided that $p$ is sufficiently close to 1, it holds almost surely that, if the edges are sampled independently with probability $p$, there is a unique infinite connected component, and that there is $0 < \theta(p) < 1$ such that every (deterministic) vertex belongs to that infinite component with probability $\theta(p)$.

Now set $\alpha := \theta(p)$. Then there are two cases.

Case 1. Suppose we chose infinitely many sources. Let $A$ be one of those sources. If $A$ belongs to the infinite component (which, by definition, happens with probability $\alpha$), it does so almost surely along with infinitely many other sources (technically, this requires a proof, which nevertheless is perfectly standard). Additionally, if $B$ is a source distinct from $A$, there is a positive probability that $A$ and $B$ belong to the same connected component. To conclude, the probability that $A$ is not the only source in its component, is strictly greater than $\alpha$, which is not what we want to achieve.

Case 2. Suppose we chose finitely many sources. In that case, we can capture all these sources into a finite square, say, $Q$. For each positive integer $r$ take a sink $X_r$ at distance $r$ from $Q$. There are two events to consider: $E_1(r)$ - that the component of $X_r$ is finite and does not intersect with $Q$, and $E_2(r)$ - that the component of $X_r$ is infinite, while at the same time all edges on the boundary of $Q$ are absent. The probability of $E_1(r)$ tends to $1 - \alpha$ as $r \to \infty$, while the probability of $E_2(r)$ is uniformly positive. It means that for large enough $r$ the probability of $X_r$ having no source in its component is strictly greater than $1 - \alpha$. Correspondingly, the probability that the sink $X_r$ has a source in its component is strictly less than $\alpha$, which is not what we want.

However, I could not make a similar argument work on a finite graph.

Answer 2

To indicate the non-triviality of this problem, consider a symmetric star graph with 3 rays (X,Y, and Z), each having 2 vertices (thus the graph has in total 7 vertices, including the center $C$, let us denote them $X_1,X_2,Y_1,Y_2,Z_1,Z_2$,and $C$). For this graph, the answer is "yes" for all possible values of $\alpha$ and $p$.

Star graph with 3 rays

One of the following SEVEN possible configurations will work (I indicate which vertices are sources):

(i) $\{C\}$

(ii) $\{X_2,Y_2,Z_2\}$

(iii) $\{X_2,Y_2,Z_2,C\}$

(iv) $\{X_1,X_2,Y_2,Z_2\}$

(v) $\{X_1,X_2,Y_1,Y_2,Z_2\}$

(vi) $\{X_1,X_2,Y_1,Y_2,Z_1,Z_2\}$

(vii) $\{X_1,X_2,Y_1,Y_2,Z_1,Z_2,C\}$

It turns out that this is the minimal number of configurations needed to cover all possible values of the parameters. Especially difficult cases, requiring non-symmetric (!) configurations are $p=0.8, \alpha=0.95$ and $p=0.74, \alpha=0.9$.

The plot below indicates areas of possible pairs $(p,\alpha)$ covered by the seven configurations above. Phase diagram for the pair $(p,\alpha)$