Conjecture about crossing paths in $n\times n$ grid: counterexample or ideas

This answer isn't fully rigorous but should illustrate the idea.

If $n = 1$ or $2$ then the result is trivial to check. So let's consider the case when $n \ge 3$. Suppose by contradiction that there exists a unique path going from one edge to the opposite edge such that both ends of the path are not opposite corners.

Let $T$ be the collection of edges that are connected to the path. We have that $T$ is a tree, otherwise if $T$ contains a loop the path is not unique. Also, $T$ touches at most $3$ of the boundaries of the $n \times n$ square. Otherwise, if $T$ were to touch all $4$ edges of the square, there would be two paths between opposite sides.

We now fill in each contiguous area on each side of $T$ with a distinct color, see the diagram below for an example. The dotted edges form $T$ and there are three shaded regions. Since $T$ touches at most $3$ edges there are at most three shaded regions.

There are some important cases to check here such as what happens if the original path goes between adjacent corners and so on. However, it is possible to show that one of these shaded regions must go from one edge to the opposite edge. Then if we look at the boundary of this shaded region we find two path from one edge to the opposite edge, a contradiction. In the example below, we use the green region.

Example of shading construction


enter image description here

This is how I see the diagonals split into two distinct parts $D^*$ and $\bar{D}^*$. If you overlay these two parts onto one grid, you get a configuration of diagonals (in two colours on the right hand side of the diagram).

The part $D^*$ is a subset of the "complete configuration" $D$, and the other part $\bar{D}^*$ is a subset of the complement $\bar{D}$, which I would call the "complementing complete configuration".

The split between the two is driven by the partition $P$ of the grid into black and white tiles.

In this way of looking at it, rotating one diagonal by $45°$ is equivalent to changing the colour of the corresponding tile on the partition $P$.

Tags:

Graph Theory

Combinatorics

Probability Theory

Computational Mathematics

Related

How many whole rectangles can you catch in a grid? Why am I getting the wrong answer when I factor an $i$ out of the integrand? Find all positive integers $n$ such that $\varphi(n)$ divides $n^2 + 3$ Prove that a function between metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ is continuous iff the pre-image of open sets is open Is $\infty=\sqrt[\Omega]{\omega}$ actually a thing? Understanding Fraleigh's proof of: Every finite integral domain is a field Can we find $n$ such that $3061\cdot2^n +1$ is prime? Geometry problem involving a cyclic quadrilateral and power of a point theorem? how would you prove that polynomial functions are not exponential? Is $\frac{\cos(\frac{1}{z})}{z^2}$ meromorphic or Not? Evaluate $\lim_{n\to\infty} \prod_{k=1}^n \frac{2k}{2k-1}\int_{-1}^{\infty} \frac{{\left(\cos{x}\right)}^{2n}}{2^x} \; dx$ What is the reason for the term "zero dimensional" in the context of topology?

Recent Posts