8
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ What exactly do you count as two paths crossing the grid? E.g., does the orange structure in your image constitute two paths crossing the grid? If so, how much of a path can be reused? Do we have two paths crossing the grid if we have one crossing path and it branches in two right before the border? Does one of the two paths have to be vertical and the other horizontal, or could they both cross in the same direction? $\endgroup$
    – joriki
    May 24, 2020 at 10:33
  • 1
    $\begingroup$ It seems that this conjecture includes cases when: two paths start on the same side and finish on the same side, one path is a strict subset of another path. Perhaps the reformulation of this conjecture could be tackled by Spener's Lemma: there is not a unique path from a non-corner to a non-corner on the opposite side. $\endgroup$
    – Oliver Clarke
    May 24, 2020 at 11:00
  • $\begingroup$ @joriki thanks a lot for your good comments. Very much appreciated. Let me include clarifying answers in my question $\endgroup$
    – Claus
    May 24, 2020 at 11:25
  • 1
    $\begingroup$ Isn't there a fourth crossing path from the point 2 steps to the right of $B$ to the point $d$? $\endgroup$
    – celtschk
    May 25, 2020 at 5:55
  • $\begingroup$ @celtschk Thanks a lot for your good comment, you are perfectly right! I will update the diagram and include also in the text. Thanks for highlighting! $\endgroup$
    – Claus
    May 25, 2020 at 8:06

2 Answers 2

Reset to default
8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ thank you for a great answer. This is a compelling argument! Great idea to work with the colour-shaded regions which solve the case. Thanks again! $\endgroup$
    – Claus
    May 24, 2020 at 12:11
  • $\begingroup$ I saw that you specialise in Algebra. May I ask you one more question on this grid path topic. I have looked at it from a combinatiorial, topological, and graph theory point of view. But I keep having the feeling there is something strongly ALGEBRAIC in it (and mod 2) which I am not able to define properly. When you look at it, do you have a similar impression, I wonder? I think it has to do with: what happens when you just rotate 1 diagonal. I keep wondering is this a group with a topological property (existence of path property) $\endgroup$
    – Claus
    May 24, 2020 at 12:15
  • 1
    $\begingroup$ I noticed that you can color the vertices of this grid with two colours (in a alternating / checkerboard pattern) and paths only visit vertices of a single color. I think this might give the impression of 'two' kinds of paths in these grids. Other than that I didn't see much more 'algebraic' stuff here when I tried to problem. Just for the record, I originally tried topological methods (see the game hex and Brouwer fixed point theorem) but couldn't get anywhere. $\endgroup$
    – Oliver Clarke
    May 24, 2020 at 12:24
  • 1
    $\begingroup$ I have the impression there are really two kinds of paths in the grid. I have drawn a picture to show these two parts in separate colour, please see in the "answer" below (technically, I had to put it as an answer) $\endgroup$
    – Claus
    May 24, 2020 at 13:36
4
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ Nice diagram! Perhaps the answer to your original conjecture can come from understanding the partition $P$ in a way similar to the game of hex $\endgroup$
    – Oliver Clarke
    May 24, 2020 at 15:01
  • 1
    $\begingroup$ I agree, I think there could be something interested there. I drew the diagram in draw.io, which I think has now moved to diagrams.net, app.diagrams.net $\endgroup$
    – Oliver Clarke
    May 24, 2020 at 20:16
  • 1
    $\begingroup$ One thought: You could mark on $P$ the corners reached by lines in $D$ with white dots and those reached by lines in $\overline D$ with black dots. Then you can see the final image directly from the initial: A black square causes the black corners to be connected, a white square causes the white corners to be connected. That is, you can pass from one black (white) point to the next via a black (white) square. Conversely, you can move from a black (white) square to the next if they share a black (white) point. That is, you don't even need to draw the lines to see the connections. $\endgroup$
    – celtschk
    May 25, 2020 at 9:45
  • 1
    $\begingroup$ BTW, the overlay image doesn't match the image in the question. $\endgroup$
    – celtschk
    May 25, 2020 at 9:48
  • 1
    $\begingroup$ Shouldn't this also be four connecting paths? I mean, looking at the orange path that connects top and bottom, I see three further paths connecting left and right that you can produce from it: One by removing only the top diagonal, one you get by only removing the bottom diagonal, and one you get by removing both diagonals. Together with the full path (that is both a connecting path for left-right and for up-down), that's four paths. $\endgroup$
    – celtschk
    May 25, 2020 at 10:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .