Convex geometry 0.1 Dehn-Sommerville relations In this section we will talk about convex polytopes. One possible denition of a convex polytope uses the notion of a half-space: A closed half-space in Rn is the set of points lying on the same side of some hyperplane (this hyperplane is included in the set as well to make it \"closed\"). A little bit more precisely it is the set of points x = (x1 , ..., xn ) Rn satisfying the inequality a1 x1 + ...an xn c for given numbers a1 , ..., an , c R. A closed convex gure is an intersection of nitely or innitely many closed half-spaces. Thus a closed convex gure is the set of solutions of a system of inequalities of the type a1 x1 + ...an xn c. Later in this chapter we will discuss another way to dene a convex gure it can be dened as a closed set (in the sense of topology of subsets of Rn ) which along with any two points in it contains the whole segment connecting them. A polytope is a closed convex gure that can be represented as intersection of nitely many closed half-spaces. Note that in general a polytope may be unbounded. A convex polytope is called bounded if the distance between any two points of this polytope is bounded by some a priori chosen number. In this section the word \"polytope\" will be reserved only for closed bounded polytopes. Space for gure We will single out a special class of polytopes - that of simple polytopes. A polytope is called simple if the vectors along the edges of every vertex form a basis of Rn . In particular only n edges meet at every vertex. Exercise: prove that any face of a simple polytope is a simple polytope (in the ane space spanned by it). 1 2 With any polytope we will associate an n-tuple of numbers (f0 , ..., fn ) that describe some of its combinatorics. Namely f0 will be the number of vertices of the polytope, f1 - the number of edges, f2 - the number of 2dimensional faces, fk - the number of k-dimensional faces. For example fn is always just 1 a polytope has only one n-dimensional face. At rst sight it might seem that these numbers f0 , ..., fn might be more or less arbitrary. However there are some relations that they always satisfy. For example Euler has noticed that f0 f1 + f2 ... + (1)n fn is always equal to one. In fact we will see below that in case of a simple polytope, the numbers f0 , ..., fn possess a hidden and marvelous symmetry. Let's now build the tools to uncover it. It is convenient to package the numbers f0 , ..., fn into one polynomial f (t) = f0 + f1 t + ... + fn tn . We will also need the polynomial h dened by h(t) = f (t 1). It turns out that the beautiful properties of the numbers f0 , ..., fn are most easily expressed in terms of the coecients h0 , ..., hn of this polynomial h(t) = h0 + h1 t + ... + hn tn . For instance Euler's observation f0 f1 + f2 ... + (1)n fn = 1 translates into the statement that h0 = f (1) = 1. Now we will state the main result presented in this section, the DehnSommerville relations. Theorem 1. The numbers h0 , ..., hn associated to a simple polytope satisfy hi = hni (symmetry) hi 1 (positivity) Add exercises and comments on non-simple polytopes. The proof of this theorem will occupy us to the end of this section. The following denitions will be crucial for the proof. 1. A linear functional L on Rn is a linear function L : Rn R. A linear functional always has the form L(x1 , ..., xn ) = a1 x1 + ... + an xn for some real numbers a1 , ..., an . We will abbreviate this by writing L(x) = a, x . We say that a functional L is generic with respect to a given polytope if its values at dierent vertices are all dierent. It is clear that a functional chosen at random will be generic with probability one. Indeed, if v1 , ..., vk are the vertices of the polytope, 0.1. DEHN-SOMMERVILLE RELATIONS 3 then the functional L(x) = a, x is non-generic with respect to the polytope if and only if a, vi = a, vj for some pair of indices i, j. Equivalently a belongs to the hyperplane a, vi vj = 0. Since the number of vectors of the form vi vj is nite, the generic functionals are abundant except for vectors a in a nite union of hyperplanes, all vectors a dene generic functionals. 2. A vertex v has index i with respect to the functional L if there are exactly i edges going out of v along which L is decreasing. Space for gure. The main statement that is needed for the proof is the following: Lemma 2. For every functional l generic with respect to the polytope P , the number hi of vertices of index i is equal to the number hi the i-th coecient of the h-polynomial of the polytope P . Proof. We will call a vertex v \"maximal\" for the face F if the the maximum of the restriction of functional L to the face F is attained at it. The assumption that the functional L is generic implies that every face of P has exactly one maximal vertex. Thus if we count the number of pairs (F, v) such that v is the maximal vertex of the m-dimensional face F , we get just the number fm of m-dimensional faces of the polytope P . We can compute the same number in a dierent way counting the number of relevant faces for each vertex rst and then summing up the results over all vertices. Suppose that a vertex v has index i. Then the number of m-dimensional i faces for which v is maximal is m there are i edges going out of v along which L is decreasing and the choice of an m-dimensional face for which v is maximal is equivalent to a choice of m of these edges. Note that here we strongly use the assumption that P is simple if P is not simple, then dierent choices of m edges may lead to the same choice of m-dimensional face. Space for gure. So to nd the number of pairs (F, v) of m-dimensional faces F for which i the vertex v is maximal, we should sum the numbers m over all vertices of index i and over all indices i. The number of such pairs is equal to i im m hi (recall that hi denotes the number of vertices of index i). 4 Comparing the two ways of counting we can conclude that fi = But this means that n n i f (t) = fi t = i=0 i=0 im Thus f (t 1) = n i=0 i i i i hi t = hi t = m m 0min n i ( i=0 m=0 i im m hi . i m t )hi = m hi ti , or hi = hi . To conclude, we just showed that hi , the number of vertices of index i with respect to the linear functional L is equal to hi , a number that can be expressed in terms of combinatorics of the polytope alone! In particular the number of vertices of index i does not depend on the choice of the generic linear functional L. Now we will exploit this last result to prove Dehn-Sommerville relations. If v has index i with respect to the functional L, then its index with respect to the functional L is n i (here we use simplicity of the polytope P once again). Thus the number hi of vertices of index i with respect to functional L is equal to the number hni of the vertices of index ni for the functional L. This proves the rst part of the theorem: hi = hni . For the second part, choose a vertex of the polyhedron and choose the generic linear functional L so that this vertex will have index i with respect to it. Then the number hi of index i vertices will be at least 1. This proves the nal assertion of Dehn-Sommerville theorem. Exercise: nd all h and f polynomials for 3-dimensional polytopes (usually referred to as polyhedra). For each one of the polynomials nd an example of polyhedron that realizes this polynomial. 0.2 Convex closed sets In this section we will focus on properties of more general convex sets - not necessarily bounded polytopes. Large parts of the theory of convex sets can be developed in a general context of topological vector spaces, and such generality is indeed useful for purposes of functional analysis. We, however, will focus on more geometric parts of the story and restrict ourselves to studying convex set in Euclidean spaces. n hi (1 + t)i i=0 0.2. CONVEX CLOSED SETS 5 A subset of an Euclidean space is called convex if along with any two points a and b in , the whole line segment joining a and b is contained in . Space for gure. Note that an intersection of an arbitrary collection of convex sets is convex again. Also note that a half-space {x| a, x c} is an example of a convex set. Intersections of half-spaces provide us with a lot of additional examples of convex sets. One should note however, that all examples obtained in this way have to be closed1 . Our rst goal will be to show that in fact every closed convex set can be obtained in this way - a set is closed and convex if and only if it can be represented as the intersection of some collection of half-spaces. Before we prove this result, we will formulate a very closely related result: Theorem 3 (Separation theorem). Let p be a point located outside a closed convex set . Then there exists a hyperplane that separates them, i.e. a hyperplane with the property that the point p and the set lie on dierent sides of it. Proof. First we will prove that there exists a point q such that the distance from p to q is the same as the distance between p and the set 2 . Since the distance between the point p and the set is the inmum of distances between p and points in , we can nd a sequence of point qi such that limi dist(p, qi ) = dist(p, ) (dist denotes the Euclidean distance). The sequence qi is bounded (starting from some index i0 all qi 's satisfy dist(p, qi ) < dist(p, ) + 1, hence |qi | < |p| + dist(p, ) + 1) and hence there exists a converging subsequence of it. Let q denote the limit of this subsequence. By the assumption that the set is closed, the point q belongs to it and by continuity of the distance, dist(p, q) = dist(p, ). Now let H be the hyperplane orthogonal to the segment pq and such that p and q lie on dierent sides of it. We claim that H separates p from . Indeed, if r is any point in , then the segment from q to r must be contained 1 Recall that a set is called closed if for any converging sequence of points in the set, the limit of the sequence also belongs to the set. One can easily check that an arbitrary intersection of closed sets is a closed set. 2 The distance between a point p and a set is dened as the inmum of distances between p and points in . One can easily check that if the set is not closed, this distance might be strictly smaller than all the distances between p and points of 6 in . Since the distance from p to any point on this segment must be greater that the distance from p to q, the angle pqr must be obtuse (greater than 90 degrees). This implies that r is on the same side of H as q is. Now we can prove that a convex closed set is an intersection of half-spaces: let be any closed convex set and be the convex closed set obtained as the intersection of all half-spaces that contain . Clearly the set is contained in . If a point p does not belong to , then there is a hyperplane that separates p from . Thus p does not belong to the half-space determined by this hyperplane and containing . Thus p doesn't belong to the intersection of all half-spaces that contain . This way we showed that = . 0.3 Convex Hull We will study now the minimal convex set that contains a given one. Denition 1. The convex hull (S) of the set S is the smallest convex closed set that contains S. It can be described also as the intersection of all convex closed sets that contain S, or, as we showed in the last section, as the intersection of all the closed half-spaces that contain S. For example the convex hull of a nite collection of points in a plane is the smallest convex polygon containing all of them. We will now give an alternative description of the convex hull of the set S: Claim 1. A point p belongs to the convex hull of the set S if and only if there exist points x1 , ..., xm S and numbers 1 , ..., m 0 such that 1 + ... + m = 1 and p = 1 x1 + ... + m xm . Proof. First we show that if x1 , ..., xn belong to S and 1 , ..., m are positive numbers such that 1 + ... + m = 1, then 1 x1 + ... + m xm belongs to the convex hull of S. We show this by induction on m. If m = 1, then 1 = 1 and the claim is obvious. Suppose we proved the claim for m and want to show it for m + 1. The point 1 x1 + ... + m xm + m+1 xm+1 is the center of mass of the system of positive masses 1 , ..., m+1 located at points x1 , ..., xm+1 . By the properties of center of mass, it must be located on the 0.3. CONVEX HULL 7 segment connecting the point xm+1 to the center of mass of the system C of masses 1 , ..., m located at the points x1 , ..., xm . By inductive assumption, the center of mass of C lies in the convex hull. Clearly xm+1 lies in the convex hull as well. Since the convex hull of any set is convex, the entire segment connecting xm+1 to C must lie in the convex hull. In particular it contains the point 1 x1 + ... + m xm + m+1 xm+1 . For the other direction let be the set of linear combinations 1 x1 + ... + m xm of points in S such that i 0 and 1 + ... + m = 1. This set is convex. Indeed, if p is the center of mass of points x1 , ..., xm with positive masses 1 , ..., m and q is the center of masses of points y1 , ..., yk with positive masses 1 , ..., k , then any point tp+(1t)q on the segment connecting p to q is the center of mass of the system of masses t1 , ..., tm , (1t)1 , ..., (1t)k . Hence Delta contains the convex hull of S. But the rst part of the proof shows that the convex hull is contained in , hence they coincide. Now we will prove an explicit bound on the number of points one needs in order to represent any point in the convex hull of the set S as a convex linear combination. The bound is known under the name of Caratheodory theorem. Theorem 4 (Caratheodory). If S is a subset of Rd , then any point in the convex hull of S can be written as 1 x1 + ... + d+1 xd+1 for some points x1 , ..., xd+1 in S and numbers i 0, 1 + ... + d+1 = 1. Alternatively we can formulate the theorem as saying that any point in the convex hull of the set S is in the convex hull of at most d + 1 points of S. Proof. We already proved that any point x can be written as the center of mass of some collection 1 , ..., n of positive masses with total mass 1 of points x1 , ..., xn . Now we will show that if n > d + 1, then we can do without one of the masses. By repeating this argument, we will end up with a system of at most d + 1 positive masses with the same center of mass. To show we can get rid of one of the masses in case n > d + 1 we will \"slide\" the masses without changing the center of mass and make one of the masses in the end of the process equal to zero. Here's how we do it: the n 1 vectors x2 x1 , ..., xn x1 must be linearly dependent (since n 1 > d). Hence there are some numbers 2 , ..., n , not all zero, such that 2 (x2 x1 ) + ... + n (xn x1 ) = 0. Let 1 = (2 + ... + n ), 8 so that 1 + ... + n = 0 and 1 x1 + ... + n xn = 0. These two equalities show that if we will add to the mass i at point xi the mass ki for some k 0 (the same k for all points xi ), then the total mass of the system won't change and the location of the center of mass won't change as well. Since i 's are all positive and at least one of the i 's is negative, there is some maximal k so that i + ki is still non-negative for all i. For such k one of the masses i + ki must vanish (otherwise, if all these masses are strictly positive, we can increase k a little bit more). 0.4 Helly's theorem In this section we will prove the following remarkable theorem: if in a collection of convex subsets of Rd every d + 1 sets intersect, then all the sets of the collection intersect. Because the theorem is extremely beautiful, we will repeat it once again for the case d = 2: if in a collection of convex sets in the plane every three have a point in common, then all the sets in the collection have some point in common. To appreciate the theorem we should see that the assumptions are really necessary. Space for gure - three convex planar sets, each two intersect, but the three don't Space for gure - four non-convex planar sets, each three intersect, but the four don't. To prove this theorem we will rely on a lemma by Radon. The lemma claims that if S is a nite set of at least d + 2 points in Rd , then the set S can be partitioned as a union of two subsets, A and B such that the convex hulls of A and B intersect non-trivially. We will prove both Radon's and Helly's theorem on line and in plane and leave the more general case as a series of exercises for the reader. Radon's lemma for the line: Suppose we have a set S that contains at least 3 points on the real line R. We want to show that S can be partitioned as a union of two subsets A and B such that their convex hulls intersect. Let A consist of the smallest and largest points in S (we order the points as if they are just numbers in R). Let B consist of all other points. Clearly the convex hull of A coincides with the convex hull of S, hence in particular intersects (in fact contains) the convex hull of B. 0.4. HELLY'S THEOREM 9 Radon's lemma for the plane: Suppose we have a set S that contains at least 4 points on the plane R2 . We want to show that S can be partitioned as a union of two subsets A and B such that their convex hulls intersect. We can assume that no three points in S are collinear, for if they were, we could use Radon't theorem for the line that contains at least three points and we would be done. So take any 3 points p, q, r in S. They form a non-degenerate triangle. We will refer to the half-spaces dened by the lines pq,qr and rs and containing the triangle pqr as H1 , H2 and H3 . Take now any other point s from S (i.e. a point dierent from p, q and r). The point s can lie in one of the seven regions to which the lines pq,qr,pr subdivide the plane. There are three possible cases: one case is that the point s lies inside the triangle pqr, i.e. inside all three half-planes H1 , H2 , H3 . Then we will take A to be the set of three points p, q, r and let B be the compliment of A in S. With this choice the point s will lie in the intersection of the convex hulls of A and B. Another possibility is that the point s lies inside one of the half-planes and in the outside of the other two. For instance we will consider the case that it lies inside H1 , the half-plane dened by pq, and outside the other two half-spaces. Then the point r must lie inside the triangle pqs and we can take A to consist of the points p, q and s and B be the compliment of A. The intersection of the convex hulls of A and B contains the point r. The last option is that the point s lies inside two half-planes, say H1 and H2 , and outside the other one. Then the segments pq (the one that denes the half-space to which s doesn't belong) and rs must intersect. We will take in this case A to consist of p and q and B be the compliment. The intersection of the convex hulls of A and B will contain the intersection point of pq and rs. Remark: there is no fourth case, where the point s doesn't belong to any of the half-planes: their union covers all the plane. Space for gure describing the three cases. Radon's lemma, while it is quite simple, allows us to prove a much deeper result, Helly's theorem, which otherwise is not very easy to prove. We will now recall what Helly's theorem (in the plane) tells us and prove it. Theorem 5. If in a nite collection of convex sets every three intersect, then the intersection of all the sets in the collection is not empty. Proof. We will prove the theorem by induction on the number n of sets in the collection. The case n = 3 is clear. Even though we don't have to, we will 10 verify the case n = 4 separately, to give the reader a feeling for the general argument. Let G1 , G2 , G3 and G4 be the four convex sets. Suppose that the intersection of every triple of them is non-empty. Let A1 , A2 , A3 , A4 be points in these intersections, i.e. A1 G2 G3 G4 , A2 G1 G3 G4 , A3 G1 G2 G4 and A4 G1 G2 G3 . Radon's theorem tells us that we can subdivide the collection A1 , A2 , A3 and A4 to two subsets, whose convex hulls intersect. If one of the four points, say A1 belongs to the convex hull of the other three, then A1 must belong to G1 - all three of the points A2 , A3 , A4 belong to G1 by their denition, hence any point in their convex hull belongs to G1 as well. Since by its denition A1 belongs to the other three convex sets, it belongs to the intersection of all four. Similar argument applies if the Radon's theorem gives us that the two sets, whose convex hulls intersect, consist of two points each. Suppose for instance that the segments [A1 , A2 ] and [A3 , A4 ] intersect at a point P . Since both A1 and A2 belong to G3 and G4 , every point in their convex hull also belong both to G3 and G4 . In particular the point P lies in G3 G4 . A similar argument about the points A3 and A4 and the sets G1 and G2 implies that P belongs to G1 G2 as well. Hence P belongs to the intersection of the four sets G1 , G2 , G3 and G4 . Now suppose we have proved the theorem for every collection of n planar sets and want to prove it for a collection of n + 1 sets. By induction hypothesis the intersection of every n-tuple of sets in our collection is non-empty. Let Ai be a point in the intersection of all the sets, except the i-th one. Radon's theorem guarantees us that we can subdivide the set A1 , ..., An+1 to two subsets, whose convex hulls intersect. By renaming the sets if necessary,we can assume that the two subsets are {A1 , ..., Ak } and {Ak+1 ..., An+1 }. Let P be a point in the intersection of their convex hulls. Since all the points A1 , ..., Ak belong to Gk+1 ... Gn+1 , all points in their convex hull also lie in this intersection. In particular the point P lies there. Similarly, considering the points Ak+1 , ..., An+1 , we deduce that the point P must lie in the intersection of the rst k sets, G1 ... Gk . This shows that the point P lies in the intersection of all the sets in the collection we started with. Let's see how we can apply Helly's theorem to a problem from geometry. Problem: prove that if every three points of a nite collection of points in a plane lie inside some circle of radius one, then all the points of this 0.5. THEORETICAL EXERCISES ABOUT HELLY'S AND RADON'S THEOREMS11 collection lie inside some circle of radius one. Solution: Consider the set of circles of radius one with centers at the points from our collection of points. Every three circles in this set must intersect. Indeed, saying that the three circles of radius one centered at points p1 , p2 , p3 do not intersect is the same as saying that there is no point in the plane, whose distance from the three points p1 , p2 , p3 is smaller than one. But this means also that there is no circle of radius one containing the three points p1 , p2 , p3 . Now Helly's theorem implies that the intersection of all the circles in the set we considered is non-empty, i.e. there is some point P , whose distance from all the points in our collection is smaller than one. This is exactly what we wanted to prove. 0.5 Theoretical exercises about Helly's and Radon's theorems In the d-dimensional space Rd Radon's theorem tells that if S is a set of n points in Rd and n d + 2, then we can subdivide S to two subsets so that their convex hulls intersect. Prove the theorem following the outlined steps: 1. If there is a collection of d + 1 points from S that lie on a d 1dimensional hyperplane, reduce the problem to d 1-dimensional Radon theorem. 2. Show it is enough to prove the theorem for n = d + 2. 3. Suppose that S consists of d + 2 points p1 , ..., pd+2 and every collection of d+1 of them doesn't lie on one hyperplane. Show that we can nd non-zero numbers 1 , ..., n+1 with sum 1, so that pd+2 = 1 p1 + ... + d+1 pd+1 . 4. Suppose the numbers 1 , ..., k in the above representation pd+2 = 1 p1 + ... + d+1 pd+1 are positive and the other 's are negative. Show that there exist positive numbers 1 , ..., d+2 such that 1 + ... + k = k+1 + ... + d+2 and k+1 pk+1 + ... + d+2 pd+2 1 p1 + ... + k pk = 1 + ... + k k+1 + ... + d+2 . Hint: why the choice 1 = 1 , ..., k = k ,k+1 = k+1 , ..., d+1 = d+1 ,d+2 = 1 works? 5. Deduce Radon's theorem from the result of step 4. 12 Exercise: deduce Helly's theorem in d-dimensional space Rd from Radon's theorem proved in the exercise above. Namely show that if every d + 1 sets in a nite collection of convex sets intersect, then all the sets in this collection intersect. Hint: the arguments are very close to those used in the deduction of planar Helly's theorem from planar Radon's theorem