Pair of curves joining opposite corners of a square must intersect---proof? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:27:51Z http://mathoverflow.net/feeds/question/35514 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof Pair of curves joining opposite corners of a square must intersect---proof? Jyotirmoy Bhattacharya 2010-08-13T18:02:52Z 2011-10-01T00:15:19Z <p>Reposting something I posted a while back to Google Groups.</p> <p>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".</p> <p>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.</p> <p>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)$$</p> <p>The two curves will intersect if there are numbers $a$ and $b$ in $[0,1]$ such that</p> <p>$$p(a,b) = x_2(b) - x_1(a) = 0$$ $$q(a,b) = y_1(a) - y_2(b) = 0$$</p> <p>We define the two functions</p> <p>$$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)$$</p> <p>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.</p> <p>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? </p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/35515#35515 Answer by Robin Chapman for Pair of curves joining opposite corners of a square must intersect---proof? Robin Chapman 2010-08-13T18:12:34Z 2010-08-13T18:12:34Z <p>See</p> <p>R. Maehara, The Jordan Curve Theorem via the Brouwer Fixed Point Theorem, <em>Amer. Math. Monthly</em> <strong>91</strong>, 641--643 (1984) </p> <p>which is availiable on <a href="http://www.maths.ed.ac.uk/~aar/jordan/" rel="nofollow">Andrew Ranicki's website</a>.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/35517#35517 Answer by Will Jagy for Pair of curves joining opposite corners of a square must intersect---proof? Will Jagy 2010-08-13T18:27:42Z 2010-08-14T03:25:09Z <p>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.</p> <p>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 <em>Introduction to Graph Theory,</em> 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.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/35527#35527 Answer by George Lowther for Pair of curves joining opposite corners of a square must intersect---proof? George Lowther 2010-08-13T19:28:14Z 2010-08-13T19:55:19Z <p>There is a simple proof that a game of <a href="http://en.wikipedia.org/wiki/Hex_%28board_game%29" rel="nofollow">Hex</a> must have a winner, which implies the result you want.See here: <a href="http://www.math.auckland.ac.nz/class750/section5.pdf" rel="nofollow">Brouwer's Fixed Point Theorem and the Jordan Curve Theorem</a>, Lemma 5.5. The Brouwer fixed point theorem and the Jordan Curve theorem follow from this.</p> <p>This proof is based on the paper <a href="http://www.math.pitt.edu/~gartside/hex_Browuer.pdf" rel="nofollow">The Game of Hex and the Brouwer Fixed-Point Theorem</a> (by David Gale. The American Mathematical Monthly, Vol. 86, No. 10. (Dec., 1979), pp. 818-827). </p> <p>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.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/35544#35544 Answer by Anton Lukyanenko for Pair of curves joining opposite corners of a square must intersect---proof? Anton Lukyanenko 2010-08-13T21:11:38Z 2010-08-13T21:11:38Z <p>You could use Brouwer degree for a more intuitive proof:</p> <p>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.</p> <p>Alternately, you could artificially avoid the phrase "Brouwer degree" and directly track what happens to the intersection point under the homotopy.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/35555#35555 Answer by John Stillwell for Pair of curves joining opposite corners of a square must intersect---proof? John Stillwell 2010-08-14T03:09:39Z 2010-08-14T04:15:15Z <p>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.</p> <p>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 $&lt;\varepsilon/3$. Then, by a homotopy inside each disk we can replace $A,B$ by <em>polygonal paths</em> $A',B'$ that join the opposite corners of the square and are still disjoint. </p> <p>Also, we can replace $A',B'$ by <em>simple</em> 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.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/37484#37484 Answer by Ryan Mickler for Pair of curves joining opposite corners of a square must intersect---proof? Ryan Mickler 2010-09-02T10:35:41Z 2010-09-02T11:41:49Z <p>Hi all, This is really interesting qn. But it only involves basic homotopy theory, not anything as subtle as the jordan curve theorem.</p> <p>Proof:</p> <p>Let the paths be parameterized as v(t), and w(s). t,s in I := [0,1]</p> <p>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.</p> <p>Think of I x I as being a homotopy between the paths, </p> <p>$a1(t) = { (0,2t) : 0&lt; t &lt;1/2<br> { (2t-1,1) : 1/2 &lt; t&lt;1$</p> <p>and </p> <p>$a2(t) = { (2t,0) : 0 &lt; t&lt;1/2 { (1,2t-1) : 1/2 &lt; t &lt; 1$</p> <p>(i.e. the two boundary components of IxI, as paths from (0,0) -> (1,1) )</p> <p>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.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/37486#37486 Answer by Ryan Mickler for Pair of curves joining opposite corners of a square must intersect---proof? Ryan Mickler 2010-09-02T10:43:25Z 2010-09-02T11:45:49Z <p>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</p> <p>Q(v,w) = (1,1)(0 1; -1 0)(1,-1)^t = 2</p> <p>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.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/37493#37493 Answer by Gerald Edgar for Pair of curves joining opposite corners of a square must intersect---proof? Gerald Edgar 2010-09-02T12:51:34Z 2010-09-03T12:19:33Z <p>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 <em>Measure, Topology, and Fractal Geometry</em>. In particular, no previous knowledge of algebraic topology is required.</p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/54283#54283 Answer by Steven Frankel for Pair of curves joining opposite corners of a square must intersect---proof? Steven Frankel 2011-02-04T03:26:58Z 2011-02-04T03:26:58Z <p>This should probably go in a comment, but I don't have enough reputation points.</p> <p>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.</p> <p>Robert J. MacG. Dawson, <em>Paradoxical Connections</em>. The American Mathematical Monthly Vol. 96, No. 1 (Jan., 1989), pp. 31-33. <a href="http://www.jstor.org/stable/2323252" rel="nofollow">http://www.jstor.org/stable/2323252</a></p> http://mathoverflow.net/questions/35514/pair-of-curves-joining-opposite-corners-of-a-square-must-intersect-proof/76896#76896 Answer by auniket for Pair of curves joining opposite corners of a square must intersect---proof? auniket 2011-10-01T00:08:35Z 2011-10-01T00:15:19Z <p>How about the following, using the <i> Nested Intervals Theorem </i> (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:</p> <p>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$). </p> <p>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)$.</p>