A beautiful combinatorical proof of the Brouwer Fixed Point Theorem - Via Sperner's Lemma

the tea inside of this cup is a sort of three-dimensional solid but if I just look at the layer of milk foam on the top that represents a two-dimensional disc now I want to imagine that I take the milk foam on the top and I mix it around I'm not doing three-dimensional mixing I'm just mixing around this top layer of foam on this two-dimensional disc now if I just rotate around in a circle kind of like spinning a wheel of a car the point in the very center it does not change but what if I did some other crazy mixing some other function of this two-dimensional disk to the two-dimensional disk then the remarkable claim of brower's fixed point theorem is that there is some little bit of milk foam that ends up exactly where it began and well that was true for the two-dimensional disk it's also true for the whole three-dimensional solid if I do a lot of aggressive mixing and transform three dimensionally that there is one spot in my cup of tea that remains exactly where it began or at least exactly within whatever uncertainty of the size of these molecules is going to be all right so let's head to the video lab and we can see how we can prove that so this is the formal statement of brower's fixed point theorem and I had to tell you a few little pieces of terminology first and the first is this BN being is just the mathematical way we're gonna describe a closed ball of dimension n so for example what we have here this is B - the closed ball of dimension 2 and it basically just looks like a disc a circle but it's filled in all of the points where it is less than or equal to 1 in the sum of the squares of the coordinates and then what we're considering is continuous maps that take this particular ball and it does whatever it wants to the ball it takes points from the ball to other points in the ball and the only constraint is continuity that is that points that begin close together need to end up close together so one of these maps is the one that we just talked about where we're gonna go and take this and rotated around in the point in the mill does not change but that all of the other points on the ball go to some other point on the ball then the claim about brower's fixed-point theorem the claim is that there is a fixed point there is one X that has the property that f of X is equal to X so in the case of one we're just rotating it around it's that point that's right in the middle but for some other continuous function it might be some other point now there are many different ways that this theorem can be proven and I want to choose one that is fairly easy to follow along and is called minute Oracle in its nature so to prove this I first want to show a different theorem sperner's lemma we're gonna prove sperner's lemma and then from sperner's lemma we're going to show brower's fixed-point theorem so I want you to consider some triangle here and a sub triangulation of that larger triangle a sub triangulation is just you take the big triangle you add a bunch of vertices and you connect it so that what you get is a whole bunch of other little triangles I've done it in a way where all these triangles are regular the same size but doesn't matter you put the points anywhere you can make any sort of combination of triangles that you might wish now all the different vertices that we have in this triangulation I want to color them I want to associate some color to all the vertices let's do the big final edge points first so I put red down here green up at the top and blue down on the far right now I'm gonna try to figure out how do I go and color all the vertices along this edge and what I want to do is along the edge between the red and between the green I want to put only red and greens here so it fills in something like this along this edge reds and greens between the red and the green well on the bottom reds and blues between the red and the blue and all on the far right here greens and blues between the green and the blue now i haven't yet filled in the center here but i want to note something interesting about what occurs along this edge notice how there's some line segments like this one here that goes between two different reds but that the next one it goes between a red and a green i want to look at I want to look at these little edge segments that go between two different colors I don't care about the red to red I'm interested in the red degree so here we have one red to green here then it's a green to green don't care then green to red I care about that one and red to green I care about that one so I've got three along this edge which have alternating colors on each of these little line segments 3 is an odd number and my claim here is that that always has to occur it always has to be that there's an odd number of these red green edges why is that true first of all I want you to think well it starts at red and it ends up at green so there has to be at least one of them right maybe it's red red red red red red but eventually it has to have one that goes to great so there's at least one whoever let me imagine that I change the colors of these a little bit so first of all let me imagine this red one down here I change to a green you notice that I've got this red green edge and if I change that to a green it would just shift it over by one well shifting where the red green edge occurs that doesn't change the number of them so if I change this one we just shifted over okay what about this one up here where I've got this red dot well if I change that red dot to a green dot then there'd be two different segments that were originally counted as red green edges and now we'll just go green green green and you would remove two or likewise down in the bottom here where it goes red red red if I made that red blue it would add two so here's an argument that has to be at least one and then if I make changes I can either shift which doesn't add anything or I can replace which either adds or subtracts two so I start with an odd number and I either add or subtract two from it I'm going to end up with an odd number so I claim an odd number of red green edges and likewise there's gonna be an odd number of these Bluegreen edges on the one side and an odd number of the blue red edges along the bottom so got all these odd numbers alright so that was figuring out how we gonna associate the far outside vertices we figured out all these edge vertices what about the middle the middle do whatever you want although is there red green and blue you can fill them in however you like I don't really right now I want you to notice something if I stop thinking about edges now I want to think about all these little triangles that are going along here there's a few of these little triangles that are special there's special if you've got a triangle that has all three colors of its vertices so for example this one right here green red blue it's got all three colors for that particular little triangle and in fact there's actually three of them there's one here there's another one there and there's one down there that have all three colors those are special okay so what does furnace let me even say I haven't even told you what it says yet well it says this if you color the triangulation via the rules I told you three different colors for the big three outside vertices you have to match the colors along three edges and you can do whatever you want in the middle if you obey those rules then there has to be at least one of these little triangles that has all three colors okay so how do we prove that I'm claiming that there has to be one in this case we happen to have three of them I'm claiming there has to be one of them how can we show that I'm going to go and take my panel I'm gonna draw a pass that go through this particular triangulation here's the rule for how I'm gonna draw a path my path is going to begin at one of those edges that's going to have two different colors so for example I might want to start right up here and then the rule is I'm allowed to go through this triangulation as long as I always go through edges of the same color so for example if I come through here I've gone through the red-green edge and then I got to keep on going down there's another red-green edge I can pass through it another red-green edge I can pass through it and then a red-green edge and I'm out so I've come along in and I've gone all the way around and I've got out by only going through red-green edges okay how else can I do it I could do the same thing reverse coming in through red-green edges coming in coming in coming in and I would leave up so this sort of one goes both directions okay how else can I do it well I could come in through this red-green edge I could come in through this red-green edge and then I have a problem as soon as I get into that triangle with all three colors can't get out because they've got all three colors so there's only one red green edge so I go in and there's no exit for me or I could turn around and I would just go right out the same way but but either way would only take up one of these edges well there's several more than we can figure out okay we've got this green blue edge I can come in green blue green blue green blue green blue green blue green blue green blue and then I come in and I get stuck I come down over here and I gonna have green blue green blue green blue green blue and then I'm gonna get stuck what else do we have I guess down here green blue green blue I get stuck I got one more I can come right up the bottom here and I immediately get stuck all right so what do we think we've seen there's two ways that things can occur one is I come in and I go out and that takes up a total of two of these edges I come in and I go to a different spot the other possibility is I go in and I get stuck so now let's go back to our original planner there's an odd number of edges here well there's an odd number of edges along here and there's two possibilities I can go in and go out which takes up an even number there might be a whole bunch of these or I can come in and I can get stuck but that tells me that there has to be a spot where I come in and get stuck on one of these big highlighted yellow triangles because if there's an odd number and the ones that go in and go out are always even numbers there's got to be at least one that comes in and gets stuck so this is our claim this is our proof of sperner's lemma that indeed there must be one of these yellow triangles that has all three different colors now I did this in the 2-dimensional case but this just generalized here I've given the sort of three-dimensional analogue where now you have a tetrahedron with four different points and four colors and I will leave the proof of the generalization to you it's an induction proof but you can imagine that for example on this edge here we've got the green blue red edge and you can try to think about how do I deal with now little tetrahedrons opposed to little triangles I'll leave that proof for you now we've got sperner's lemma we've shown this comet or haven't used any high-level math here we've just sort of drawn some picture and taking paths we've got this really nice claim so now let's try to return to brower's fixed point there man we want abused the proof of sperner's lever to prove it the first thing I want to do is this is a visualization of brower's fix points there okay so I've got some dis as a two-dimensional disc I can take some function here's the rotation one right rotates it around and we've got that fixed point right in the middle now one other thing I could do is I'm gonna take this disc I'm gonna sort of flatten it down into being a triangle all right so I take this take the disc I flatten it down I'm then gonna rotate within this triangle so I'm gonna rotate everything around that now rotation means follow a little triangle opposed to fall a little circle but it's a rotation nonetheless and then I'm gonna go and blow it up again so we return back to our original disc so what I've done here is that I've effectively argued that rotation of the circle is sort of the same thing as compressed to a triangle rotating the triangle and spread out back to the full disc again and indeed this compression map that takes a disc and turns it into triangle this is a continuous map but it's an invertible map in the sense that two points are going to that are close together end up close together when you do this triangle compression map and it's invertible in the sense that if I tell you where the points are gonna go end up you can tell me where they began as well so my big claim here is that when I want to go and prove brower's fixed-point theorem which was stated as maps between balls from BN to BN i can just put in triangles they're just the same and it's gonna work exactly the same way i can look at continuous maps from a triangle to a triangle now triangles look a little bit closer if I'm gonna use sperner's lemma to prove it let's see how we can do that I know look a triangle but I can look at a very specific triangle a very specifically oriented one this this triangle you three-dimensional space where it's got one vertices at the point 1 0 0 another is 0 0 1 and a third at 0 1 0 so I had this very sort of specific triangle this by the way is called the two simplex is define in this way and the only real property that I care about is that if you're on that triangle that specific triangle then you have to have this property that X plus y plus Z is 1 the sum of the corners is equal to 1 that's the definition this triangle and I'm orienting the theorem in the context of this specific triangle so that I can use the rigidity of the way it is oriented I can use this formula in the proof of this little theorem all right so how do i make sperner's lemma was something about triangles fit in this particular context the idea is first this lowers fixed-point theorem looks at how i can go and take points here and transform the other point so for example if I have some p in the triangle what is f of P where F of P is this continuous function applied to P now what I want to do is I want to color code all of the points in this triangle and I'm going to color code them by a certain set of rules and my rules are going to be this first if F of P strictly decreases in the X direction I in a color of red if it strictly decreases in the Y direction we're gonna color it blue if a strictly decreases in the z direction we're going to color it green so all the different points here could be color-coded red blue or green just kind of like we had with sperner's lemma let's consider the big outside vertices first well if I look at this one here there's only one of two possibilities either FFP doesn't change it in which case I've done I've proven my theorem F of P is equal to P or if it does change because this isn't the maximal the X equal to one it has to decrease the value that's that's why I color it red likewise for a green and likewise for blue so now that I got my triangle starting to look a little bit like sperner's lemma let's try a triangulation of it so I'll go and divide it up however I wish now I want to color code all the different vertices on this triangle but but let's look at this left edge first on this edge Y is zero so I can never decrease that I can never cover it blue because Y is already zero so along this edge it's only red and greens along this edge only red and blues and on the far side it's only green and blue so this applies the conditions of sperner's lemma this triangulation has to be color-coded according to sperner's lemma and what is tell me it tells me that there is somewhere somewhere a yellow triangle a sub triangle in the triangulation that is all three colors okay let me keep going I've got that let me now go in some triangulate again so I took my triangulation I made a finer triangulation with little smaller ones well sperner's lemma still applies it still gives me a particular sub triangle but now it's that smaller one there's no guarantee that this smaller one is ever we're related to the larger one it's just somewhere on here there's got to be another one I can keep on going and keep on going smaller triangulations and smaller triangulations and indeed I'm going to get the sequence of little triangles that get smaller and smaller and smaller and bounce all around my big triangle let me just focus on the red points so what I get in effect is a sequence of red points I've drawn a finite number of them but it's an infinite sequence I can keep on sub triangulating you get a new little triangle I figure out where the red point is I can keep on doing that or I could do it for the greens or I could do it for the blues it doesn't really matter but nonetheless I'm going to get this infinite sequence of red points and infinite sequence of green points in an infinite sequence of blue points that's a few points about this the first is this every sequence has a convergent subsequence due to this very powerful theorem in mathematics called pizanno Weierstrass theorem that is this my triangle is a finite space I've got infinitely many points there bouncing all around this particular triangle there's no order to it but because there's infinitely many there must be somewhere on the triangle where the points start getting accumulated there where infinitely many of them get close to some spot because it's an infinite number being squeezed in this finite space I can't escape this fact so somewhere over here of this infinite sequence we have what we call a convergent subsequence where if I just choose some collection of this infinite sequence an infinite collection of this infinite sequence then those points are going to be getting arbitrarily close to some other spot so that's the first point there's some red point where this sequence is getting close to that same for the green same for the blues further as we sub triangulate and sub triangulate that the three different colors keep on getting closer and closer and closer as I get smaller and smaller triangles so this point where you've got the Reds converging to it also has the greens converging to it also has the Blues converging to it as in there is some point where it is decreasing decreasing was our condition to define the red the blue and the green it's decreasing in all three of the directions by the way note that in our original definition we said strictly decrease it as and not equal but the way that convergent sequences work the point is converging to could be on the boundary and so this it's possible if decreasing or equal in all directions and then finally if it's decreasing or equal it's not possible to decrease in all three directions at once remember that original equation the X plus y plus Z is equal to one it can't be that x + y + Z are all decreasing so the only possibility is that x + y + Z that they do not change in other words it is fixed in all directions and so what do we have we have a fixed point we've said that there must be some spot I don't know where it is but I know that it must exist where F of P is P in other words that this continuous function is fixing the point so that is the proof of brower's fixed point theorem from sperner's lemma

Channel: Trefor Bazett

Views: 7,592

Rating: 4.9447002 out of 5

Keywords: Math, Brouwer, Fixed Point, Sperner, Topology, Proof, Combinatorics, Theorem, triangulation

Id: oX9aPNF6_h8

Length: 19min 30sec (1170 seconds)

Published: Sun Mar 11 2018