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

549 Views Asked by At

enter image description here

This asks for ideas or suggestions regarding a conjecture about crossing paths in a grid, or a counterexample.

For background, I am starting with a known result, and will articulate the conjecture based on it (the picture gives an example for the conjecture).

Definition: Given an $n\times n$ grid, where exactly 1 diagonal is randomly placed in each unit square.

Existence Lemma: Going along the diagonals, there is always a path crossing the grid from one side to the opposite side (top-down or left-right).

There are several proofs of this lemma. One goes by exploration; one uses a separation theorem from topological dimension theory; one is based on a dual graph approach. They are presented in the original post (https://mathoverflow.net/q/112067/156936). There is another proof making iterated use of the Lemma of Sperner (https://math.stackexchange.com/a/3677664/782412).

Definition to cover a special case just to keep the formulation of the conjecture simple:

(1) The top left corner of the grid is defined to belong to the top side and to the left side, and similarly for the other three corners of the grid.

(2) In light of this corner definition, a path going from the top left corner to the bottom right corner is seen as two paths, i.e. one from top to bottom and one from left to right. Similarly for a path crossing from top right corner to bottom left corner.

Conjecture: For $n>1$, there are at least two paths along the diagonals crossing the grid.

Remark: Using the picture above to illustrate the definition of what counts as different paths:

Clearly, the paths A-B, A-C, B-C and x-y are no crossing paths, as they don't cross the grid from one side to the opposite side. For the same reason, A-y is not a crossing path.

The paths A-x, B-y, and C-y count as three different paths that are crossing the grid.

Finally, B-x also counts as a crossing path because it contains A-x, and A-x is a crossing path. (This is consistent with the definition of the special case connecting opposite corners.)

In summary, the picture is an example with 4 crossing paths A-x, B-x, B-y, C-y.

More generally, two paths can have common diagonals. If we have a crossing path that branches in two paths right before the grid border, it counts as two paths. Two paths can both cross in the same direction, for example left to right crossing for both paths.

Question

This conjecture is based on samples for $n<10$. I have tried to extend the proofs of the Existence Lemma, but with no success. Do have any ideas or suggestions for alternative proof approaches, or maybe a counterexample?

Maybe as a starting point, does someone have the computing power to check a complete set of examples for small $n$?

2

There are 2 best solutions below

4
On BEST ANSWER

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

10
On

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