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

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

2010-08-13T18:02:52Z

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?

Answer by Robin Chapman for Pair of curves joining opposite corners of a square must intersect---proof?

2010-08-13T18:12:34Z

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.

Answer by Will Jagy for Pair of curves joining opposite corners of a square must intersect---proof?

2010-08-13T18:27:42Z

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.

Answer by George Lowther for Pair of curves joining opposite corners of a square must intersect---proof?

2010-08-13T19:28:14Z

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.

Answer by Anton Lukyanenko for Pair of curves joining opposite corners of a square must intersect---proof?

2010-08-13T21:11:38Z

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.

Answer by John Stillwell for Pair of curves joining opposite corners of a square must intersect---proof?

2010-08-14T03:09:39Z

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.

Answer by Ryan Mickler for Pair of curves joining opposite corners of a square must intersect---proof?

2010-09-02T10:35:41Z

Hi all, This is really interesting qn. 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 x I -> S^1, given by f(s,t) = (v(t)-w(s))/|v(t)-w(s)| is well defined.

Think of I x I as being a homotopy between the paths,

$a1(t) = { (0,2t) : 0< t <1/2
{ (2t-1,1) : 1/2 < t<1$

and

$a2(t) = { (2t,0) : 0 < t<1/2 { (1,2t-1) : 1/2 < t < 1$

(i.e. the two boundary components of IxI, as paths from (0,0) -> (1,1) )

Then, we see that f(a1(t)) is a path that starts at the north pole of the circle, and ends at the south pole, and traverses clockwise, whereas f(a2(t)) starts and ends the same, but traverses counterclockwise. Now f(I x I) provides a homotopy between these paths, however they are not homotopic as paths in the circle, this give a contradiction. and hence the paths must intersect.

Answer by Ryan Mickler for Pair of curves joining opposite corners of a square must intersect---proof?

2010-09-02T10:43:25Z

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.

Answer by Gerald Edgar for Pair of curves joining opposite corners of a square must intersect---proof?

2010-09-02T12:51:34Z

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.

Answer by Steven Frankel for Pair of curves joining opposite corners of a square must intersect---proof?

2011-02-04T03:26:58Z

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

Answer by auniket for Pair of curves joining opposite corners of a square must intersect---proof?

2011-10-01T00:08:35Z

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