# Pair of curves joining opposite corners of a square must intersect---proof?

Reposting something I posted a while back to Google Groups.

In his 'Ordinary Differential Equations' (sec. 1.2) V.I. Arnold says "... every pair of curves in the square joining different pairs of opposite corners must intersect".

This is obvious geometrically but I was wondering how one could go about proving this rigorously. I have thought of a proof using Brouwer's Fixed Point Theorem which I describe below. I would greatly appreciate the group's comments on whether this proof is right and if a simpler proof is possible.

We take a square with side of length 1. Let the two curves be $(x_1(t),y_1(t))$ and $(x_2(t),y_2(t))$ where the $x_i$ and $y_i$ are continuous functions from $[0,1]$ to $[0,1]$. The condition that the curves join different pairs of opposite corners implies, $$(x_1(0),y_1(0)) = (0,0)$$ $$(x_2(0),y_2(0)) = (1,0)$$ $$(x_1(1),y_1(1)) = (1,1)$$ $$(x_2(1),y_2(1)) = (0,1)$$

The two curves will intersect if there are numbers $a$ and $b$ in $[0,1]$ such that

$$p(a,b) = x_2(b) - x_1(a) = 0$$ $$q(a,b) = y_1(a) - y_2(b) = 0$$

We define the two functions

$$f(a,b) = a + p(a,b)/2 + |p(a,b)| (1/2 - a)$$ $$g(a,b) = b + q(a,b)/2 + |q(a,b)| (1/2 - b)$$

Then $(f,g)$ is a continuous function from $[0,1]\times [0,1]$ into itself and hence must have a fixed point by Brouwer's Fixed Point Theorem. But at a fixed point of $(f,g)$ it must be the case that $p(a,b)=0$ and $q(a,b)=0$ so the two curves intersect.

Figuring out what $f$ and $g$ to use and checking the conditions in the last para is a tedious. Can there be a simpler proof?

-
My guess is you need to appeal to some form of the Jordan curve theorem. –  Qiaochu Yuan Aug 13 '10 at 18:05
I second the Jordan Curve Theorem suggestion. –  Thierry Zell Aug 13 '10 at 18:15
I am looking for any rigorous proof, the more elementary the better. –  Jyotirmoy Bhattacharya Aug 13 '10 at 18:23
See John Stillwell's answer below, which explains how you can reduce to the case where the curves are piecewise linear, which certainly makes things simpler! –  Emerton Aug 14 '10 at 3:52
I like the proofs based on $K_5$ and the polygonal Jordan curve theorem, but if all of them are unwound, the Brouwer fixed point theorem proof is the most direct and transparent. –  Victor Protsak Aug 14 '10 at 6:27

Since the full Jordan curve theorem is quite subtle, it might be worth pointing out that theorem in question reduces to the Jordan curve theorem for polygons, which is easier.

Suppose on the contrary that the curves $A,B$ joining opposite corners do not meet. Since $A,B$ are closed sets, their minimum distance apart is some $\varepsilon>0$. By compactness, each of $A,B$ can be partitioned into finitely many arcs, each of which lies in a disk of diameter $<\varepsilon/3$. Then, by a homotopy inside each disk we can replace $A,B$ by polygonal paths $A',B'$ that join the opposite corners of the square and are still disjoint.

Also, we can replace $A',B'$ by simple polygonal paths $A'',B''$ by omitting loops. Now we can close $A''$ to a polygon, and $B''$ goes from its "inside" to "outside" without meeting it, contrary to the Jordan curve theorem for polygons.

-
This is a great argument! –  Victor Protsak Aug 14 '10 at 6:14
This is gorgeous! It's possibly worth pointing out quite how elementary the Jordan curve theorem for polygons is, to show how little is being black-boxed here. Fix some point $x_0$ not on $C$, and for any (other) point $x$ not on $C$, look at the line segment from $x$ to $x_0$; count the parity of how many times it crosses $C$ (counting double/none if it hits vertices of $C$). This is well-defined and locally constant on $\mathbb{R}\setminus C$ (this is where we use that $C$ is a polygon); so as a locally constant, surjective function to $\{0,1\}$, it disconnects $\mathbb{R}^2$. –  Peter LeFanu Lumsdaine Aug 14 '10 at 6:47
Dear Peter: Your line segment may cross $C$ infinitely many times. [You probably mean $\mathbb{R}^2\setminus C$, not $\mathbb{R}\setminus C$.] –  Pierre-Yves Gaillard Aug 14 '10 at 11:18
Peter: That proof goes through even when the polygon isn't simple, e.g. a polygonal figure-eight, where the parity function disconnects the plane into more than two components. So, there's a bit more work to do. –  Per Vognsen Aug 14 '10 at 14:49
@Pierre: thanks, yes, I did mean $\mathbb{R}^2$; and while the segment can't cross $C$ infinitely often (a polygon has finitely many edges by definition, at least in the conventions I know) it could contain an edge of $C$ as a subsegment, in which case we do have to look at what directions the adjacent edges of $C$ go off in. @Per: you're right, of course; this doesn't establish the full Jordan curve theorem; I was just thinking of what was necessary for the application at hand (which just needs disconnectedness plus the fact that the second curve's endpoints are in opposite components). –  Peter LeFanu Lumsdaine Aug 14 '10 at 17:34

ORIGINAL: This follows from the fact that the complete graph $K_5$ on five vertices cannot be imbedded in $\mathbb S^2,$ in itself an application of Jordan Curve. If your two square curvy diagonals stay inside the square without intersecting, a fifth point outside the square can be joined to the four vertices by disjoint arcs, thus creating a complete graph on five vertices. Very nice book by James Munkres, "Topology: a first course" where, on page 386 exercise 5, he does the graph on five vertices. Note that the concept of inside for the square uses elementary ideas such as convexity.

EDIT: As mentioned by Henry Wilton in comment below, there may be other routes here. In particular, I have a book by Robin J. Wilson just called Introduction to Graph Theory, second edition, and in section 13, pages 64-67, in which he develops Euler's formula for planar graphs and as a quick corollary shows that $K_5$ and $K_{3,3}$ are nonplanar, these being Theorem 13A and Corollary 13E. It is anybody's guess whether JCT is used implicitly in defining "faces" properly for Euler's formula. I don't know.

-
That's a neat idea! –  Somnath Basu Aug 13 '10 at 18:43
Do you really need the Jordan Curve Theorem to see that $K_5$ is non-planar? I ask because Thomason gives a proof of the JCT using the fact that $K_{3,3}$ is non-planar. –  HJRW Aug 14 '10 at 1:41
very nice proof! –  Kerry Aug 14 '10 at 2:24
Henry, I don't think I know how to sort out first principles here. The Munkres book, same page, in exercise 4, has the reader use JCT to show that $K{3,3}$ is non-planar. I'm going to guess that the three facts are roughly equivalent in the sense of quick proofs in both directions for any pair. So the questions become, does the nonplanarity of the complete graph on five vertices imply JCT quickly, and is there some trickery where each nonplanar graph gives the other, all "quickly." –  Will Jagy Aug 14 '10 at 2:45
Just to clarify slightly, Thomason quickly observes that if a graph is planar then it has a polygonal embedding in the plane; so you can talk about faces before you've proved the JCT. –  HJRW Aug 14 '10 at 5:07

This should probably go in a comment, but I don't have enough reputation points.

Note that there is a pair of connected sets in the square containing opposite pairs of corners that don't intersect. There are pictures in the reference below.

Robert J. MacG. Dawson, Paradoxical Connections. The American Mathematical Monthly Vol. 96, No. 1 (Jan., 1989), pp. 31-33. http://www.jstor.org/stable/2323252

-
+1 for retaining something from one of our conversations . . . –  Danny Calegari Oct 1 '11 at 12:15

There is a simple proof that a game of Hex must have a winner, which implies the result you want.See here: Brouwer's Fixed Point Theorem and the Jordan Curve Theorem, Lemma 5.5. The Brouwer fixed point theorem and the Jordan Curve theorem follow from this.

This proof is based on the paper The Game of Hex and the Brouwer Fixed-Point Theorem (by David Gale. The American Mathematical Monthly, Vol. 86, No. 10. (Dec., 1979), pp. 818-827).

Edit: Actually the reference shows that the Game of Hex always has a winner => Brouwer Fixed Point theorem => a pair of curves in the square joining opposite corners must intersect. So it does use Brouwer's fixed point theorem, but gives an elementary proof of it.

-
As much as I like the connection with Hex, Gale comments on, but doesn't give the proof of, the additional statement "not both" in the Hex theorem, which is the Hex analogue of the intersection property. Thus for the purposes of this question, Hex is a distraction. –  Victor Protsak Aug 14 '10 at 6:09
Yes, at first I thought that they proved it directly from the game of Hex. The result asked for would follow from the result that you can't have a state in which both players have a winning line, but the references only show directly that at least one person must win. However, the first link does have a short proof of the result asked for, albeit using the fixed point theorem (and a proof of that). So, it's not as direct and elementary as I thought at first. Still, it answers the question. –  George Lowther Aug 14 '10 at 12:19

You could use Brouwer degree for a more intuitive proof:

The degree of the usual diagonals intersecting each other is 1. One at a time, deform the diagonals via straight-line homotopies to the desired curves. This should preserve Brouwer degree. Lastly, Brouwer degree is well-defined even for continuous functions (using a smooth approximation), and non-zero Brouwer degree implies an intersection.

Alternately, you could artificially avoid the phrase "Brouwer degree" and directly track what happens to the intersection point under the homotopy.

-
+1 for the name, a combination of "Anton Gorodetsky" and "Sergei Lukyanenko" -- any relation? –  Pete L. Clark Aug 13 '10 at 21:27
:) No, not as far as I know. –  Anton Lukyanenko Aug 13 '10 at 22:10
I'm not sure that the last paragraph avoiding the degrees works: the curves may intersect in more than one point, so it's challenging to "directly track what happens to the intersection point". –  Victor Protsak Aug 14 '10 at 6:19

A homological proof would use the intersection form of the torus. if you consider these paths as based loops on the torus, you see that they are represented as (1,1), and (1,-1), in terms of the standard homology generators. knowing that the intersection form is (0 1; -1 0), we find that the intersection index

Q(v,w) = (1,1)(0 1; -1 0)(1,-1)^t = 2

they already intersect once at the origin, so they must intersect somewhere else in the square. However, you must already have had to compute the intersection form.

-

How about the following, using the Nested Intervals Theorem (which was in my 2nd year Calculus text) which says the intersection of a nested sequence of closed intervals in $\mathbb{R}$ is non-empty. Here goes the proof:

We construct recursively a nested sequence $I_j := [a_j, b_j]$ of closed intervals for $j \geq 0$. Let $I_0 := [0,1]$. For every $j \geq 0$, construct $I_{j+1}$ as follows: let $m_j$ be the midpoint of $I_j$. If the curves intersect at $t = m_j$, then we are done, so stop the sequence. Otherwise set $I_{j+1}$ to be $[a_j, m_j]$ or $[m_j, b_j]$ depending on whether the curves "switch from left to right" on the first sub-interval or the 2nd (let's say you always make sure that $c_1$ is to the "left" of $c_2$ at $t = a_j$ and to the "right" of $c_2$ at $t = b_j$).

If the sequence is finite, then the curves must intersect, as noted above. So assume the sequence is infinite. The Nested Intervals Theorem and the fact that the length decreases by a factor of 2 at every step implies that $\cap_{j=0}^\infty I_j = \lbrace t\rbrace$ for some $t \in [0,1]$. Then we must have $c_1(t) = c_2(t)$.

-
I seems that your proof is valid for funtions graphs and no generalized curves: when write "switch from left to right" I guess that you to consider the intersetion of the two curves by the line parallel to a cartesian axis $t$: $t=m_j$, and you suppose to have only two intesection (one for curve) . But this isn't true for general curves. ANyway your proof is adaptable: curves are compact and intesection by a interval is a closed, you have anyway a first point at lest and a first point at right..the rest is the some. –  Buschi Sergio Jul 26 '13 at 8:46

This is a really interesting question. But it only involves basic homotopy theory, not anything as subtle as the Jordan curve theorem.

Proof:

Let the paths be parameterized as $v(t)$, and $w(s)$, $t,s \in I := [0,1]$.

Assume the paths never intersect. Then the map $f : I \times I \to S^1$, given by $f(s,t) = \dfrac{v(t)-w(s)}{|v(t)-w(s)|}$, is well defined.

Think of $I \times I$ as being a homotopy between the paths

$a_1(t) = \begin{cases} (0, 2t) & 0 \leq t \leq \frac{1}{2}\\ (2t-1, 1) & \frac{1}{2} < t \leq 1 \end{cases}$

and

$a_2(t) = \begin{cases} (2t, 0) & 0 \leq t \leq \frac{1}{2}\\ (1, 2t-1) & \frac{1}{2} < t \leq 1 \end{cases}$

i.e. the two boundary components of $I \times I$, as paths from $(0,0) \to (1,1)$.

Then we see that $f(a_1(t))$ is a path that starts at the north pole of the circle, and ends at the south pole, and traverses clockwise, whereas $f(a_2(t))$ starts and ends the same, but traverses counterclockwise. Now $f(I \times I)$ provides a homotopy between these paths. However, they are not homotopic as paths in the circle. This gives a contradiction, and hence the paths must intersect.

-
Isn't a path in $S^1$ contractible to a point? –  Piero D'Ancona Sep 2 '10 at 12:24
By 'paths', i mean paths starting at the top of the circle, and ending at the bottom. –  Ryan Mickler Sep 2 '10 at 13:29
Perhaps i should have been more clear. f(IxI) is a homotopy 'of paths that start at the top of the circle and end at the bottom'. –  Ryan Mickler Sep 2 '10 at 13:34
I guess a more elegant way to see it, is to consider again, the map f: I x I -> S^1, when restricted to the boundary, d(IxI) ~= S^1, we find (from the argument above) that f_d(IxI) : S^1 -> S^1 winds once, but f_IxI gives a homotopy from this map to the constant map, hence a contradiction. –  Ryan Mickler Sep 2 '10 at 14:01
After thinking about it some more. This question is really a generalization of the intermediate value theory. The IVT is really a homotopy theory question, where you are detecting pi_0(R-{0}), in this case, we are detecting pi_1(R^2-{0}). –  Ryan Mickler Sep 3 '10 at 4:50

See

R. Maehara, The Jordan Curve Theorem via the Brouwer Fixed Point Theorem, Amer. Math. Monthly 91, 641--643 (1984)

which is availiable on Andrew Ranicki's website.

-

This is the main step of the proof that the plane (in this case, the square) has topological dimension 2. You can find a proof (as elementary as I could make it) in my text Measure, Topology, and Fractal Geometry. In particular, no previous knowledge of algebraic topology is required.

-
Did you mean to say that no previous knowledge of algebraic topology is required? –  Victor Protsak Sep 2 '10 at 15:21
thanks, corrected. –  Gerald Edgar Sep 3 '10 at 12:19