A problem on chains of squares — can one find an easy combinatorial proof?

Consider the unit square $S = [0,1] \times [0,1]$. For each $n \in \mathbb{N}$, we can tessellate $S$ by the collection $$A = \left\{ \left[ \frac{i}{n},\frac{i + 1}{n} \right] \times \left[ \frac{j}{n},\frac{j + 1}{n} \right] ~ \Bigg| ~ i,j \in \{ 0,\ldots,n - 1 \} \right\}$$ of $n^{2}$ smaller squares whose sides have length $\dfrac{1}{n}$.

Let $C_{1}$ be a finite sequence $(S_{k})_{k = 1}^{M}$ of squares in $A$ such that

• $S_{1} = \left[ 0,\dfrac{1}{n} \right] \times \left[ 0,\dfrac{1}{n} \right]$;
• $S_{M} = \left[ \dfrac{n - 1}{n},1 \right] \times \left[ \dfrac{n - 1}{n},1 \right]$;
• $S_{k}$ and $S_{k + 1}$ share a common side for each $k \in \{ 1,\ldots,M - 1 \}$.

Similarly, let $C_{2}$ be a finite sequence $(T_{k})_{k = 1}^{N}$ of squares in $A$ such that

• $T_{1} = \left[ 0,\dfrac{1}{n} \right] \times \left[ \dfrac{n - 1}{n},1 \right]$;
• $T_{N} = \left[ \dfrac{n - 1}{n},1 \right] \times \left[ 0,\dfrac{1}{n} \right]$;
• $T_{k}$ and $T_{k + 1}$ share a common side for each $k \in \{ 1,\ldots,N - 1 \}$.

Geometrically speaking, $C_{1}$ is a chain of side-touching squares in $A$ from the bottom leftmost corner of $S$ to its upper rightmost corner, and $C_{2}$ is a chain of side-touching squares from the upper leftmost corner of $S$ to its bottom rightmost corner.

Combinatorial problem. Find a combinatorial proof that $C_{1}$ and $C_{2}$ contain a common square in $A$. (It is intuitively obvious that the chains contain a common square in $A$.)

If we let $n \to \infty$, then we obtain a

Continuous version of the problem. Let $\gamma_{1}$ be a continuous path in $S$ from $(0,0)$ to $(1,1)$ and $\gamma_{2}$ a continuous path in $S$ from $(0,1)$ to $(1,0)$. Then prove that $\gamma_{1}$ and $\gamma_{2}$ intersect, i.e., ${\gamma_{1}}(a) = {\gamma_{2}}(b)$ for some $a,b$ in the interval $]0,1[$.

The continuous version of the problem has a well-known solution via Brouwer’s Fixed Point Theorem, but most proofs of Brouwer’s Fixed Point Theorem require algebraic topology. Even Sperner’s combinatorial proof requires some effort to understand. If, however, we can solve the combinatorial problem above, then by a limiting argument, we can solve the continuous version rather easily, thus avoiding Brouwer.

There are certain similarities between this problem and the Game of Hex, where elementary properties of the game are a consequence of non-trivial topological arguments, as first demonstrated by John Nash.

• This strikes me as roughly equivalent to the PL Jordan separation theorem. – Jim Conant Oct 21 '14 at 19:55
• The two problems are quite easily seen to be equivalent: To go from combinatorial to continuous, form the corresponding sequences of squares and let $n\to\infty$. The sequence of common squares has a subsequence converging to the intersection of the curves. To go the other way, form the curve $\gamma_i$ from $C_i$ by connecting the midpoints of the sides touching adjacent squares (and corners in endpoints). The intersection of these two curves gives you a common square. Proving either version is less trivial. – Joonas Ilmavirta Oct 21 '14 at 20:04
• @Joonas, how do you prove that such a sequence is a chain? – The Masked Avenger Oct 21 '14 at 21:23
• @TheMaskedAvenger: I want to choose all the (closed) squares that are visited by the curve. This collection contains a finite number of squares including the ones in corners and every square in the collection has at least one neighbor in the collection. This collection is also connected, which is a nontrivial point. Then there is a chain going through all these squares, possibly visiting some squares several times. The chain doesn't have to visit the squares in the same order as the curve. – Joonas Ilmavirta Oct 21 '14 at 21:57
• Thank you all for the lively discussion. Just to make sure that everybody is on the same page, I’m using the word ‘chain’ in the literal sense here with no connotations whatsoever of the theory of posets. I just couldn’t find a better word to convey the geometrical nature of the problem. – Transcendental Oct 21 '14 at 23:40

I used to think that Sperner's proof is simple enough, but if you don't like it, maybe it's because what you're really looking for is an algorithm. I can show that there is no fast algorithm for your problem, at least not something faster than for Sperner's lemma. This is because your question, if defined appropriately, becomes PPAD-complete. This means that if there was a fast algorithm for your problem, then one could convert it into a fast algorithm for finding a solution to a large class of other problems, like finding a Brouwer like fixed point or a a Nash equilibrium (if defined appropriately). I really don't think that you are interested in the details, the proof is quite straightforward and similar to showing the PPAD-completeness of 2D-SPERNER or 2D-TUCKER. In case you are, here is a list of papers: http://www.cs.princeton.edu/~kintali/ppad.html

If you don't like complexity theory, then here is the draft of a paper from whose proofs it follows that you can find a common square in O(n) steps, where one step is to ask of any one square whether it belongs to $C_1$ or $C_2$: http://arxiv.org/abs/1211.3000

• “I can show that there is no simple algorithm for your problem” — the complexity argument shows there can be no quick algorithm for the problem, but it doesn’t show there can’t be a simple one. Many problems have naïve exponential-time algorithms, which aren’t good for practical computation but can be great for understanding existence proofs easily. – Peter LeFanu Lumsdaine Oct 25 '14 at 23:05
• @Peter Agreed, fixed. – domotorp Oct 26 '14 at 10:27
• Hi domotorp. It’s not that I don’t like Sperner’s Lemma. In fact, I greatly admire it for its absolute beauty. However, because the claim that $C_{1}$ and $C_{2}$ intersect in a common square is so intuitively true, I thought that there might be a proof that requires something even simpler than Sperner’s Lemma. Anyway, I appreciate your response very much. – Transcendental Oct 28 '14 at 3:42

You could google digital Jordan curve theorem and you could also add some of the following names in your search: Khalimsky, Kiselman, Kopperman, Rosenfeld, Slapal. The papers you get are likely to be along the lines of what you are looking for, I hope.

In particular see several papers in a Special issue on digital topology, Topology and its Applications http://www.sciencedirect.com/science/article/pii/016686419290013P

or a recent paper by J Šlapal, [Jordan Curves in the Digital Plane, http://www.emis.de/journals/BMMSS/pdf/acceptedpapers/2011-06-033_R1.pdf

or an older survey, T. Yung Kong, Ralph Kopperman, Paul R. Meyer, A topological approach to digital topology. Amer. Math. Monthly 98 (1991), no. 10, 901–917. http://www.jstor.org/discover/10.2307/2324147

• The name ‘Digital Jordan Curve Theorem’ resonates with me. It seems to be the thing I need. Thanks, Mirko! – Transcendental Oct 28 '14 at 3:33