Are there more paths exiting a box in $\mathbb{Z}^2$ to the right if I remove some edges to the left

Question

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$. Prove or disprove that there are more edge-self-avoiding paths from the midpoint $(N+1,N+1)$ to a vertex of the form $(2N+1, m)$ for $m \in \{ 1, 2, \dots 2N+1 \}$ than paths to a vertex of the form $(1, m)$ for $m \in \{ 1, 2, \dots 2N+1 \}$.

Answer 1

Expanding on Anthony Quas' comments above, it is indeed possible to show that there are cases when there are more paths to the left than to the right.

Let $H$ be the graph obtained from $G$ by removing all edges from $(N-1,i)$ to $(N,i)$ except one (which then clearly is a bridge in $H$).

Any walk in $H$ that ends on the right cannot cross the bridge and thus uses at most $2N^2 + O(N)$ vertices. One way to encode such a walk is to store its length and remember the behavior (turn left/turn right/continue straight) every time we encounter a previously unvisited vertex; the behavior at previously visited vertices is determined by this encoding since we are not allowed to use any edge twice. This shows that there are at most $3^{2N^2 + O(N)}$ walks that end on the right.

For a lower bound on the number of walks in $H$ ending on the left, we observe that there is a connected subgraph of $H$ with $4N^2-O(N)$ vertices of degree $4$ in which $(N+1,N+1)$ and $(1,1)$ are the only vertices of odd degree. Starting with a Eulerian walk from $(N+1,N+1)$ to $(1,1)$ we can obtain $2^{4N^2-O(N)}$ different such Eulerian walks by iteratively performing local modifications at each vertex. Indeed, observe that if we fix how the walk traverses every vertex apart from one vertex of degree $4$, then there are always two options at this last vertex completing it to a Eulerian walk.

Answer 2

This question nagged at me. It ends up the simplest case, $N=1$ with one edge removed, disproves the claim! In the figure, a number in a vertex $v$ gives the number of self-avoiding paths from the center $c$ to $v$ that avoid the edge marked X. The forbidden edge is on the left-hand side of the grid, yet there are more self-avoiding paths ending on the left-hand side (18) than on the right-hand side (17).

(There's nothing incorrect in my original incomplete answer, but neglecting the paths that include $e$ and end on the right-hand side can skew your intuition.)

---

Original post:

An incomplete answer but too long for a comment.

Consider the case of just one edge $e$ being removed from the left-hand half of the grid. There are many self-avoiding paths strictly in the left-hand half of the grid that include $e$ and end on the left-hand side. The 180 degree rotations of these will end on the right-hand side and, by construction, not include $e$. (The same holds for their horizontal reflections, too.) Then removing $e$ eliminates the paths ending on the left-hand side but not the corresponding paths ending on the right-hand side.

That argument supports your claim, but neglects the paths including $e$ that end on the right-hand side. Their rotations & reflections end on the left-hand side and, unless they include the symmetrically located edge, survive removing $e$.