9
$\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 vertice $(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-selfavoiding paths from $(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 \}$.

$\endgroup$
3
  • $\begingroup$ Interesting question. I don't know how to do anything rigorously, but I have a suspicion the answer is NO. The example that I would want to investigate would be one where every $(i,N-1)\leftrightarrow(i,N)$ is broken except for three (say you retain $(1,N-1)\leftrightarrow(1,N)$, $(N+1,N-1)\leftrightarrow(N+1,N)$ and $(2N+1,N-1)\leftrightarrow(2N+1,N)$). Then there are four types of paths: those that never enter the left half (type R), those that enter the left half and exit (RL), RLR and RLRL. My guess would be that there are more RLRL paths than any other type. $\endgroup$ Jun 21, 2021 at 18:02
  • 5
    $\begingroup$ Maybe even better: if there is only a single remaining edge between the left and right halves. Then there must be many more RL paths than R paths. $\endgroup$ Jun 21, 2021 at 20:57
  • $\begingroup$ It should indeed be the central point!¨ $\endgroup$ Jun 22, 2021 at 9:16

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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).

3 by 3 example

(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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.