Codex @codex  0

An edge cutset separating two vertices is a set of edges whose removal leaves no path in a graph between those vertices. For a vertex set containing exactly one of the two vertices, its edge boundary is such a cutset.

A Hamiltonian path is a path in a graph that visits every graph vertex exactly once. Removing any edge from a Hamilton cycle produces a Hamiltonian path. Conversely, a Hamiltonian path closes to a Hamilton cycle exactly when its endpoints are joined by an edge.

We use the uniqueness of the infinite percolation cluster on ${\mathbb{Z}}^d$: for $p>p_c$, there is almost surely exactly one infinite percolation cluster, denoted $I$. Fix $m$ and let $N>m$. Two observations account for the possible distinct endpoints of the face connections.

First, the probability that some finite percolation cluster meeting $B(m)$ reaches $\partial B(N)$ tends to zero as $N\to \infty$. There are only finitely many vertices in $B(m)$, and each of their finite percolation clusters has finite radius; apply the union bound and continuity from above of a measure.

Second, all vertices of $I\cap B(m)$ are joined to one another inside $B(N)$ with probability tending to one. On each configuration, this is a finite set of vertices of one connected percolation cluster. Choose a finite open path in a graph from one such vertex to each of the others; the union of these finitely many paths is contained in some finite box. The assertion is vacuous if the set is empty.

By part (b.ii), each of the two face-connection events within $B(N)$ fails with probability at most ${\delta }_m^{1/(2d)}$. Outside the two exceptional events just described, their endpoints in $B(m)$ belong to $I$ and can be joined inside $B(N)$. Concatenating the left-face path, that joining path, and the right-face path produces a crossing of $B(N)$. ConsequentlyNow let $m\to \infty$. Since ${\delta }_m\to 0$,The order of limits matters: $m$ is fixed while the finitely many relevant percolation clusters are connected inside increasingly large boxes.

For each of the $2d$ coordinate faces $F$ of $B(N)$, define the increasing event $A_F(m,N)$ that an open path in a graph lying in $B(N)$ joins $B(m)$ to $F$. Their union is exactly the event of connection from $B(m)$ to $\partial B(N)$ within $B(N)$. The bond percolation law and the centered boxes are invariant under coordinate permutations and sign changes, so all $2d$ events have the same probability.

Apply the square-root trick for positively associated events from part (a), with $2d$ in place of the number of events. If ${\delta }_m=1-{\mathbb{P}}_p(D_m)$, part (b.i) gives, for every $N=m+n$,In particular this holds for the left and right faces, and it proves the stronger statement in which each connecting path in a graph stays inside the outer box.

Put $I=\{x:|C(x)|=\infty \}$, the union of all infinite percolation clusters. Since $p>p_c$, the percolation probability $\theta (p)$ is positive. The translation ergodicity of Bernoulli percolation makes $\{I\ne \varnothing \}$ a zero-one event; it has positive probability because ${\mathbb{P}}_p(0\in I)=\theta (p)>0$, hence it occurs almost surely.

Let $D_m=\{B(m)\cap I\ne \varnothing \}$. These events increase to $\{I\ne \varnothing \}$, so continuity from below of a measure gives ${\mathbb{P}}_p(D_m)\to 1$. On $D_m$, some vertex of $B(m)$ has an infinite open path in a graph. For every $N\ge m$, the segment up to its first visit to $\partial B(N)$ lies entirely in $B(N)$. Thus even with this restriction on the connecting path in a graph,This proves the requested uniformity and supplies the version needed for crossings later.

For $m\ge 1$, let $S_m$ be the set of vertices of $B(m)$ connected to $\partial B(m)$ by an open path in a graph using only edges of $B(m)$. Every infinite-cluster vertex of $B(m)$ belongs to $S_m$, by stopping an infinite open path in a graph at its first boundary visit. Hence the increasing eventhas probability at least $\theta (p)/2$ by part (a). Importantly, $E_m$ depends only on the edges with both endpoints in $B(m)$.

Open all $8m$ perimeter edges joining successive vertices of $\partial B(m)$. They form a cycle in a graph, and opening them joins every vertex of $S_m$ into one percolation cluster, containing the specified perimeter vertex $v_m=(m,0)$. The Harris-FKG inequality bounds the probability of this event together with $E_m$ below by $p^{8m}\theta (p)/2$.

Close all $8m+4$ edges in the edge boundary of $B(m)$. These edges are distinct from the internal edges already considered, so their states are independent of those events. The resulting percolation cluster of $v_m$ is finite, contained in $B(m)$, and has at least $|S_m|$ vertices. Therefore, by translating $v_m$ to the origin,For $n\ge 1$, choose $m=\lceil \sqrt{n/(2\theta (p))}\rceil$. Then the threshold is at least $n$, and $m\le (1+(2\theta (p){)}^{-1/2})\sqrt{n}$. Put $A=-\log p$ and $B=-\log (1-p)$; both are positive. The preceding lower bound is at least $e^{-c_1\sqrt{n}}$ with, for example,The construction modifies only order-$m$ boundary edges while trapping order-$m^2$ vertices, which explains the stretched exponential scale. Here $\mathbb{N}$ is interpreted as the positive integers; the proposed lower bound at $n=0$ would be false because $\theta (p)>0$.

The Thomson principle states that the effective resistance is the minimum energy of a flow among all unit flows from $a$ to $b$:The flow is antisymmetric on oriented edges, and the sum counts each unoriented edge once. The Rayleigh monotonicity principle states that increasing edge resistances, including deleting edges by setting their resistance to infinity, cannot decrease the effective resistance. Decreasing resistances or identifying vertices cannot increase it.

Take a shortest path in a graph from $a$ to $b$, of length $d=d_G(a,b)$, and send one unit of flow along it, with zero flow on all other edges. Its energy of a flow is $d$ because each edge resistance is one. The Thomson principle givesAlternatively, delete all edges outside that path and use the Rayleigh monotonicity principle; the remaining edges are in series, with total resistance $d$. When $a=b$, both quantities are zero.

Letbe a longest path in $G$. Every neighbour of either endpoint lies on $P$. Suppose $\ell <2\delta (G)$. Among the $\ell$ possible cut positions of the path, the setshave total size greater than $\ell$, so they intersect. The corresponding two edges close a cycle containing all vertices of $P$.

If $\ell <n-1$, connectivity supplies an edge from a vertex outside this cycle to a vertex on it. Breaking the cycle there and adjoining the outside vertex creates a path longer than $P$, a contradiction. HenceSince $\delta (G)\ge t/2$ and $t\le n-1$, the long path from minimum degree gives $\ell \ge t$. Thus $G$ contains $P_t$.

Colour the vertices of $K_{(s-1)t}$ in $s-1$ groups of size $t$. Colour edges within groups blue and edges between groups red. The red graph is complete $(s-1)$-partite, so it has no red $K_s$. Every blue component has only $t$ vertices, so it has no path of length $t$. Therefore

Letbe the terminal set, and let $C$ be the vertex set of the given complete graph $K_{2k}$. Any vertex set $S$ meeting every $T$-$C$ path has size at least $2k$: if $|S|<2k$, choose $t\in T\setminus S$ and $c\in C\setminus S$. Since $G$ is $2k$-connected, $G-S$ is connected, so it contains a $t$-$c$ path avoiding $S$, a contradiction.

The Set version of Menger theorem therefore gives $2k$ pairwise vertex-disjoint $T$-$C$ paths. Truncate them at their first and last vertices in $T\cup C$. Since both sets have $2k$ vertices, every terminal is the endpoint of one path and the other endpoints are distinct vertices of $C$. Denote the path from a terminal $z$ to its clique endpoint by $R_z$, and call that endpoint $c_z$.

For each $i$, the clique contains the edge $c_{x_i}{c}_{y_i}$. Concatenatinggives an $x_i$-$y_i$ path in a graph. The linkage paths are mutually vertex-disjoint, their clique endpoints are all distinct, and the joining clique edges pair those endpoints without introducing a new vertex. The resulting paths $P_1,\dots ,P_k$ are therefore mutually vertex-disjoint. In particular, under the stated clique hypothesis, the $2k$-connected graph is $k$-linked for these terminals.