Theorems With Balls - Giovanni Viglietta

Theorems with BallsCarleton Algorithms SeminarGiovanni VigliettaOttawa – May 9, 2014Theorems with Balls

Combinatorial proofs for topological theoremsBrouwer’s fixed point theoremProof: Sperner’s lemmaHairy ball theoremProof: generalized Sperner’s lemmaCorollary: fixed points on spheresBorsuk–Ulam theoremProof: Tucker’s lemmaCorollary: Lusternik–Schnirelmann theoremCorollary: ham sandwich theoremTheorems with Balls

Brouwer’s fixed point theoremTheorem (Brouwer, 1910)Every continuous mapping from an n-dimensional ball into itselfhas a fixed point.Theorems with Balls

Brouwer’s fixed point theoremTheorem (Brouwer, 1910)Every continuous mapping from an n-dimensional ball into itselfhas a fixed point.For n 1, it easily follows from the intermediate value theorem.Theorems with Balls

Brouwer’s fixed point theoremTheorem (Brouwer, 1910)Every continuous mapping from an n-dimensional ball into itselfhas a fixed point.n 2: if we crumple up the tablecloth and put it back on thetable, one point ends up in its original position.Theorems with Balls

Brouwer’s fixed point theoremTheorem (Brouwer, 1910)Every continuous mapping from an n-dimensional ball into itselfhas a fixed point.n 3: if we stir a cocktail and let it rest, one point in the liquidends up in its initial position.Theorems with Balls

Sperner’s lemmaStart from a triangulated triangle.Theorems with Balls

Sperner’s lemmaColor the vertices red, green and blue.Theorems with Balls

Sperner’s lemmaColor each vertex on an edge with one of the two colors of theendpoints of that edge.Theorems with Balls

Sperner’s lemmaColor the internal vertices red, green or blue, arbitrarily.Theorems with Balls

Sperner’s lemmaLemma (Sperner, 1928)There exists at least a triangle with vertices of all three colors.Theorems with Balls

Sperner’s lemma: proofThe red-green edges are permeable.Theorems with Balls

Sperner’s lemma: proofLet us enter the triangulation from a red-green edge. We may exitfrom another red-green edge.Theorems with Balls

Sperner’s lemma: proof.But, because the external red-green edges are odd, an oddnumber of paths end inside the triangle.Theorems with Balls

Sperner’s lemma: proofWhen the path ends, a 3-colored triangle has been found.Theorems with Balls

Sperner’s lemma: proofThere may be other 3-colored triangles, which are endpoints ofinternal paths. In total, the 3-colored triangles are odd.Theorems with Balls

Sperner’s lemma: proofAnother example.Theorems with Balls

Sperner’s lemma: proofThe proof generalizes to n-dimensional simplices and n 1 colors.Theorems with Balls

Sperner’s lemma: proofBy inductive hypothesis, a face contains an odd number of3-colored simplices.Theorems with Balls

Sperner’s lemma: proofWe enter from one of them, and we keep walking through 3-coloredtriangles. We either exit from another 3-colored triangle.Theorems with Balls

Sperner’s lemma: proof.Or we end up in a 4-colored tetrahedron. The 4-coloredtetrahedra are again odd.Theorems with Balls

Brouwer’s fixed point theorem: proofzpf ( p)yxConsider the convex hull of (1, 0, 0), (0, 1, 0), (0, 0, 1), and acontinuous function f from this set to itself.Theorems with Balls

Brouwer’s fixed point theorem: proofzp.x f (p).xpf ( p)yxIf f strictly decreases the x-coordinate of p, color p red.Theorems with Balls

Brouwer’s fixed point theorem: proofzf ( p)p.y f( p) .ypyxOtherwise, if f strictly decreases the y -coordinate of p, color pgreen.Theorems with Balls

Brouwer’s fixed point theorem: proofzpp.z f (p).zxf ( p)yOtherwise, if f strictly decreases the z-coordinate of p, color pblue.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxSuppose that f has no fixed points. Then (1, 0, 0) is red, (0, 1, 0)is green, and (0, 0, 1) is blue.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxTriangulate the triangle.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxThe points with x 0 cannot be colored red, and similarly for yand z.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxThe coloring of the vertices satisfies the hypotheses of Sperner’slemma.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxHence there is a 3-colored triangle.Theorems with Balls

Brouwer’s fixed point theorem: proofzx1z1y1yxHence there is a 3-colored triangle.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxConstruct a finer triangulation.Theorems with Balls

Brouwer’s fixed point theorem: proofzyxAgain, Sperner’s lemma yields a smaller 3-colored triangle.Theorems with Balls

Brouwer’s fixed point theorem: proofzx2xz2y2Again, Sperner’s lemma yields a smaller 3-colored triangle.Theorems with Ballsy

Brouwer’s fixed point theorem: proofzx1z1y1x2xz2y2Again, Sperner’s lemma yields a smaller 3-colored triangle.Theorems with Ballsy

Brouwer’s fixed point theorem: proofzx1z1y1x2z2y3z3xx3y2x4z4y4yProceeding in this fashion, we obtain a sequence of 3-coloredtriangles with vanishing edge lengths.Theorems with Balls

Brouwer’s fixed point theorem: proofzx1x8x7x5x9x2x3xx4x6Consider the sequence of the red vertices of such triangles.Theorems with Ballsy

Brouwer’s fixed point theorem: proofzxi3xi2xi1xi4xi 5xi 6xi7xixi98pyxBy the Bolzano–Weierstrass theorem, this sequence has asubsequence that converges to a point p in the triangle.Theorems with Balls

Brouwer’s fixed point theorem: proofzf ( p)pyxSince p is a limit of red points and f is continuous, f (p).x 6 p.x.Theorems with Balls

Brouwer’s fixed point theorem: proofzf ( p)xyi 1yi 2yi 3yi 4yyi 5 yi6 i7y i 8 yi 9pyThe corresponding subsequence of green vertices must alsoconverge to p, because their distances to the red vertices vanish.Theorems with Balls

Brouwer’s fixed point theorem: proofzf ( p)pyxHence f (p).y 6 p.y .Theorems with Balls

Brouwer’s fixed point theorem: proofzf ( p)zi 3zi 2xzi4 zi5 zi z6 i 7 z i 8 zi9pyzi 1The sub-sequence of blue vertices also converges to p.Theorems with Balls

Brouwer’s fixed point theorem: proofzpyxHence f (p).z 6 p.z.Theorems with Balls

Brouwer’s fixed point theorem: proofzp f ( p)yxBecause x y z 1 for every point in the triangle, it followsthat p is a fixed point of f .Theorems with Balls

Hairy ball theoremTheorem (Brouwer, 1912)An even-dimensional sphere does not admit any continuous field ofnon-zero tangent vectors.Theorems with Balls

Hairy ball theoremTheorem (Brouwer, 1912)An even-dimensional sphere does not admit any continuous field ofnon-zero tangent vectors.It is impossible to comb a hairy ball flat without creating cowlicks.Theorems with Balls

Hairy ball theoremTheorem (Brouwer, 1912)An even-dimensional sphere does not admit any continuous field ofnon-zero tangent vectors.Given at least some wind on Earth, there must at all times be acyclone somewhere.Theorems with Balls

Generalized Sperner’s lemmaLemmaIn any 3-colored triangulation with a different number of red-greenand green-red outer edges, there is a 3-colored triangle.Theorems with Balls

Hairy ball theorem: proofpf ( p)Assume that f (x) is continuous and nowhere zero. Let p be anypoint on the sphere.Theorems with Balls

Hairy ball theorem: proofg (x)pOverlay the vector field g (x), which is continuous everywhereexcept in p.Theorems with Balls

Hairy ball theorem: prooff ( x)pBy the continuity of f in p, there is a neighborhood of p in whichf varies by at most 1 from f (p).Theorems with Balls

Hairy ball theorem: proofpThe angle between f (x) and g (x) makes two complete turns as xmoves around the circle.Theorems with Balls

Hairy ball theorem: proof3-color the sphere (minus p) according to the angle between f (x)and g (x).Theorems with Balls

Hairy ball theorem: proofpBecause f (x) is almost constant, the colors of the points aroundthe circle must follow a precise order.Theorems with Balls

Hairy ball theorem: proofpIf we pick enough points on the circle and follow them ccw, wehave more red-green transitions than green-red transitions.Theorems with Balls

Hairy ball theorem: proofpTriangulate the part of the sphere not containing p.Theorems with Balls

Hairy ball theorem: proofpTriangulate the part of the sphere not containing p.Theorems with Balls

Hairy ball theorem: proofpThe generalized Sperner’s lemma applies, and a 3-colored triangleis found.Theorems with Balls

Hairy ball theorem: proofqpThere exists a vanishing sequence of 3-colored triangles. By theBolzano–Weierstrass theorem, we can extract sequences of allthree colors that converge to the same point q.Theorems with Balls

Hairy ball theorem: proofqpThe angle between f (q) and g (q) belongs to the intersection of[0 , 120 ], [120 , 240 ] and [240 , 360 ], which is empty.Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.pf ( p) 6 p pSuppose that f (x) is continuous and no point is mapped onto itsantipodal point.Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.pf ( p) 6 p pThen there is a unique geodesic between p and f (p).Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.pg ( p)f ( p) 6 p pIf f (p) 6 p, let g (p) be the vector tangent to the geodesic at p.Otherwise, let g (p) 0.Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.pg ( p)f ( p) 6 pqg (q ) 0 pg (x) is a continuous field tangent to the sphere, hence it has azero in q due to the hairy ball theorem.Theorems with Balls

Hairy ball theorem: corollaryCorollary (Brouwer, 1912)Any continuous function that maps an even-dimensional sphereinto itself has either a fixed point or a point that is mapped ontoits own antipodal point.pg ( p)f ( p) 6 pq f (q )g (q ) 0 pTherefore q is a fixed point of f .Theorems with Balls

Borsuk–Ulam theoremTheorem (Borsuk–Ulam, 1933)Every continuous function from an n-dimensional sphere into Rnmaps some pair of antipodal points into the same point.Theorems with Balls

Borsuk–Ulam theoremTheorem (Borsuk–Ulam, 1933)Every continuous function from an n-dimensional sphere into Rnmaps some pair of antipodal points into the same point.At any moment there is a pair of antipodal points on the Earth’ssurface with equal temperature and pressure.Theorems with Balls

Tucker’s lemmaStart from a triangulated polygon with a centrally symmetricboundary.Theorems with Balls

Tucker’s lemmaColor the external vertices so that opposite vertices have the samecolor and opposite sign.Theorems with Balls

Tucker’s lemmaColor the internal vertices arbitrarily.Theorems with Balls

Tucker’s lemmaLemma (Tucker, 1946)There are adjacent vertices with the same color and opposite sign.Theorems with Balls

Tucker’s lemma: proofOn the boundary, there is either a monochromatic edge, orthere is an odd number of bi-chromatic edges.Theorems with Balls

Tucker’s lemma: proofThe bi-chromatic edges are permeable.Theorems with Balls

Tucker’s lemma: proofIf we enter from a bi-chromatic edge, we may exit fromanother bi-chromatic edge.Theorems with Balls

Tucker’s lemma: proof.Or we get stuck in a triangle with a monochromatic edge.This happens at least once, because the entrances/exits are odd.Theorems with Balls

Borsuk–Ulam theorem: proofxx′ xProject x on the horizontal disk, and let g (x 0 ) f (x) f ( x).Theorems with Balls