\chapter{Convex geometry}
\section{Dehn-Sommerville relations}
In this section we will talk about finite convex polytopes. To define a bounded convex polytope we will proceed in stages.

A closed half-space in $R^n$ is the set of points lying on the same side of some hyperplane. Alternatively it is the set of points $x=(x_1,...,x_n)\in R^n$ satisfying the inequality $a_1 x_1 + ... a_n\cdot x_n \le c$ for given numbers $a_1,...,a_n,c\in R$.

A closed convex figure is a figure obtained by intersecting (finitely or infinitely many) closed half-spaces. Later in this chapter we will show that this definition is equivalent to saying that the figure is convex if it is closed (in the sense of topology of subsets of $R^n$) and along with any two points in it, it contains the whole segment connecting them.

A polytope is a closed convex figure that can be represented as intersection of finitely many closed half-spaces.

A bounded convex polytope is a polytope, which is in addition bounded (i.e. there is some number $c$ that bounds the distance between any two points of the polytope from above).

We will refer to bounded convex polytopes in this section just as polytopes.
Space for figure
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 $R^n$. In particular only $n$ edges meet at every vertex.
Exercise: prove that any face of a simple polytope is a simple polytope (in the affine space spanned by it).
With any polytope we will associate an $n$-tuple of numbers $(f_0,...,f_n)$ that describe some of its combinatorics. Namely $f_0$ will be the number of vertices of the polytope, $f_1$ - the number of edges, $f_2$ - the number of $2$-dimensional faces, $f_k$ - the number of $k$-dimensional faces. For example $f_n$ is always just $1$ - a polytope has only one $n$-dimensional face.
At first sight it might seem that these numbers $f_0,...,f_n$ might be more or less arbitrary. However there are some relations that they always satisfy. For example Euler has noticed that $f_0-f_1+f_2-...+(-1)^n f_n$ is always equal to one.
In fact we will see below that in case of a simple polytope, the numbers $f_0,...,f_n$ possess a hidden and marvelous symmetry. Let's now build the tools to uncover it.
It is convenient to package the number $f_0,...,f_n$ into one polynomial $f(t)=f_0+f_1 t+ ... + f_n t^n$. We will also need the polynomial $h$ defined by $h(t)=f(t-1)$.
It turns out that the beautiful properties of the numbers $f_0,...,f_n$ are most easily expressed in terms of the coefficients $h_0,...,h_n$ of this last polynomial $h(t)=h_0+h_1 t+...+h_n t^n$. For instance Euler's observation $f_0-f_1+f_2-...+(-1)^n f_n=1$ translates into the statement that $h_0=f(-1)=1$.
Now we will state the main result presented in this section, the Dehn-Sommerville relations.
Theorem: the numbers $h_0,...,h_n$ associated to a simple polyhedron satisfy

$h_i=h_{n-i}$ (symmetry)

$h_i\ge 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 definitions will be crucial for the proof.

A linear functional $L$ on $R^n$ is a linear function $L:R^n->R$. A linear functional always has the form $L(x_1,...,x_n)=a_1 x_1+...+a_n x_n$ for some real numbers $a_1,...,a_n$. We will abbreviate this by writing $L(x)=<a,x>$.

*The functional $L$ is generic with respect to a given polyhedron if it assumes different values at all the vertices.
It is clear that if $v_1,...,v_k$ are the vertices of the polytope, then the functional $L(x)=<a,x>$ is non-generic with respect to the polytope if and only if $<a,v_i>=<a,v_j>$ for some pair of indices $i,j$, or, equivalently $a$ belongs to the hyperplane defined by the equation $<a,v_i-v_j>=0$. Since the number of vectors of the form $v_i-v_j$ is finite, the generic functionals are abundant - except for some vectors $a$ in a finite union of hyperplanes, all the functionals are generic.
*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 figure.
Now we will present the main lemma needed for the proof:
For every functional $l$ generic with respect to the polytope $P$, the number $\tilde{h}_i$ of vertices of index $i$ is equal to the number $h_i$ - the $i$-th coefficient of the $h$-polynomial of the polytope $P$.
Proof: We will call a vertex $v$ maximal for the face $F$ if the functional $L$ (considered as a function on the face $F$) attains its maximum on the face $F$ at the vertex $v$. The assumption of genericity of the functional $L$ 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 $f_m$ of $m$-dimensional faces of the polytope $P$.
We can compute this number in a different way - counting the number of relevant faces for each vertex first and then summing up the results over all vertices. So let $v$ be some vertex. Suppose that it has index $i$. Then the number of $m$-dimensional faces for which $v$ is the maximal vertex is $i \choose m$ - there are $i$ edges going out of $v$ along $L$ is decreasing and choice of an $m$-dimensional face for which $v$ is the maximal vertex is equivalent to a choice of $m$ of these edges.
Note that here we use strongly the assumption that $P$ was simple - if $P$ is not simple, then different choices of $m$ edges may lead to the same choice of $m$-dimensional face.
Space for figure.
So to find the number of pairs $(F,v)$ of $m$-dimensional faces $F$ for which the vertex $v$ is maximal, we should sum the numbers $i \choose m$ over all vertices of index $i$ and over all indices $i$. So the number of such pairs is equal to $\sum_{i\ge m}{i\choose m \tilde{h}_i}$ (recall that $\tilde{h}_i$ denotes the number of vertices of index $i$).
Comparing the two ways of counting we can conclude that $f_i=\sum_{i\ge m}{i\choose m \tilde{h}_i}$. But this means that $$f(t)=\sum_{i=0}^n{f_i t^i}=\sum_{i=0}^n{\sum_{i\ge m}{i\choose m \tilde{h}_i} t^i}=\sum_{0\le m \le i \le n}{i\choose m \tilde{h}_i t^i}=\sum_{i=0}^n{(\sum_{m=0}^i{i \choose m t^m})\tilde{h}_i}=\sum_{i=0}^n{\tilde{h}_i(1+t)^i}$$.
Thus $f(t-1)=\sum_{i=0}^n{\tilde{h}_i t^i}$, or $h_i=\tilde{h}_i$.
To conclude, we just showed that $\tilde{h}_i$, the number of vertices of index $i$ with respect to the linear functional $L$ is equal to $h_i$, 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 $h_i$ of vertices of index $i$ with respect to functional $L$ is equal to the number $h_{n-i}$ of the vertices of index $n-i$ for the functional $-L$. This proves the first part of the theorem: $h_i=h_{n-i}$.
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 $h_i$ of index $i$ vertices will be at least $1$.
This proves the final assertion of Dehn-Sommerville theorem.
Exercise: find all $h$ and $f$ polynomials for 3-dimensional polytopes (usually referred to as polyhedra). For each one of the polynomials find an example of polyhedron that realizes this polynomial.
\section{Convex closed sets}
In this section we will focus on properties of mare general convex sets.
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.
A subset $\delta$ of an Euclidean space is called \textbf{convex} if along with any two points $a$ and $b$ in $\delta$, the whole line segment joining $a$ and $b$ is contained in $\delta$.
Space for figure.
Note that an intersection of an arbitrary collection of convex sets is convex again.
Also note that a half-space $\{x|<a,x>\leq c\}$ is an example of a convex set. Intersections of half-spaces provide us a lot of additional examples of convex sets.
One should note however, that all examples obtained in this way have to be closed\footnote{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.}.
Our first 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:
Separation theorem: Let $p$ be a point located outside a closed convex set $\delta$. Then there exists a hyperplane that separates them, i.e. a hyperplane with the property that the point $p$ and the set $\delta$ lie on different sides of it.
\begin{proof}
First we will prove that there exists a point $q$ in $\delta$ that realizes the distance between the point $p$ and the set $\delta$. Indeed, by definition the distance $d$ between the point $p$ and the set $\delta$ is the infimum of distances between $p$ and points in $\delta$. Let $q_i$ denote a sequence of points of $\delta$ such that $lim_{i->\infty}{dist(p,q_i)}=dist(p,\delta)$ ($dist$ denotes the Euclidean distance). The sequence $q_i$ is bounded (starting from some index $i_0$ all $q_i$'s satisfy $dist(p,q_i)<dist(p,\delta)+1$, hence $norm(q_i)<norm(p)+dist(p,\delta)+1$) and hence there exists a converging subsequence of it. Let $q$ denote the limit of this subsequence. By closedness assumption on the set $\delta$ the point $q$ belongs to it and by continuity of the distance, $dist(p,q)=dist(p,\delta)$.
Now let $H$ be the hyperplane orthogonal to the segment $p q$ and such that $p$ and $q$ lie on different sides of it. We claim that $H$ separates $p$ from $\delta$. Indeed, if $r$ is any point in $\delta$, then the segment from $q$ to $r$ must be contained in $\delta$. Since the distance from $p$ to any point on this segment must be greater that the distance from $p$ to $q$, the angle $p q r$ must be obtuse (greater than 90 degrees). This implies that $r$ is on the same side of $H$ as $q$ is.
\end{proof}
Now we can prove that a convex closed set is an intersection of half-spaces: let $\delta$ be any closed convex set and $\tilde{\delta}$ be the convex closed set obtained as the intersection of all half-spaces that contain $\delta$. Clearly the set $\delta$ is contained in $\tilde{\delta}$. If a point $p$ does not belong to $\delta$, then there is a hyperplane that separates $p$ from $\delta$, so p does not belong to the half-space determined by this hyperplane and containing $\delta$. Thus $p$ doesn't belong to $\tilde{delta}$ - the intersection of all half-spaces that contain $\delta$. This way we showed that $\delta=\tilde{delta}$.
\section{Convex hull}
We will study now the minimal convex set that contains a given one.
Definition: the convex hull $\delta(S)$ of the set $S$ is the smallest convex closed set that contains $S$. It can be desribed 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 half-spaces that contain $S$.
For example the sonvex hull of a finite 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: a point $p$ belongs to the convex hull of the set $S$ if and only if there exist points $x_1,...,x_m\in S$ and numbers $\lambda_1,...,\lambda_m\ge0$ such that $\lambda_1+...+\lambda_m=1$ and $p=\lambda_1 x_1+...+\lambda_m x_m$.
\begin{proof} first we show the implication that if $x_1,...,x_n$ belong to $S$ and $\lambda_1,...,\lambda_m$ are positive numbers such that $\lambda_1+...+\lambda_m=1$, then $\lambda_1 x_1+...+\lambda_m x_m$ belongs to the convex hull of $S$. We show this by induction on $m$. If $m=1$, then $\lambda_1=1$ and the claim is obvious. Suppose we proved the claim for $m$ and want to show it for $m+1$. The point $\lambda_1 x_1+...+\lambda_m x_m+\lambda_{m+1} x_{m+1}$ is the center of mass of the system of positive masses $\lambda_1,...,\lambda_{m+1}$ located at points $x_1,...,x_{m+1}$. By the properties of center of mass, it must be located on the segment connecting the point $x_{m+1}$ to the center of mass of the system $C$ of masses $\lambda_1,...,\lambda_m$ located at the points $x_1,...,x_m$. By inductive assumption, this center of mass $C$ lies in the convex hull. Clearly $x_{m+1}$ lies in the convex hull as well. Since the convex hull of any set is convex, the entire segment connecting $x_{m+1}$ to $C$ must lie in the convex hull, hence in particular the point $\lambda_1 x_1+...+\lambda_m x_m+\lambda_{m+1} x_{m+1}$ lies in the convex hull.
For the converse direction let $\tilde{\delta}$ be the set of linear combinations $\lambda_1 x_1+...+\lambda_m x_m$ of points in $S$ such that $\lambda_i\ge 0$ and $\lambda_1+...+\lambda_m=1$. This set is convex. Indeed, if $p$ is the center of mass of points $x_1,...,x_m$ with positive masses $\lambda_1,...,\lambda_m$ and $q$ is the center of masses of points $y_1,...,y_k$ with positive masses $\mu_1,...,\mu_k$, then any point $t p+(1-t) q$ on the segment connecting $p$ to $q$ is the center of mass of the system of masses $t\lambda_1,...,t\lambda_m,(1-t)\mu_1,...,(1-t)\mu_{k}$. Hence $\tilde{delta}$ contains the convex hull of $S$. But the first part of the proof shows that the convex hull is contained in $\tilde{\delta}$.
\end{proof}
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.
\begin{theorem}
If $S$ is a subset of $R^d$, then any point in the convex hull of $S$ can be written as $\lambda_1 x_1+...+\lambda_{d+1} x_{d+1}$ for some points $x_1,...,x_{d+1}$ in $S$ and numbers $\lambda_i\ge0$, $\lambda_1+...+\lambda_{d+1} =1$.
\end{theorem}
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$.
\begin{proof}
We already proved that any point $x$ can be written as the center of mass of some collection $\lambda_1,...,\lambda_m$ of positive masses of sum $1$ of points $x_1,...,x_n$. 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 making one of the masses in the end of the process equal to zero.
Here's how we do it: the $n-1$ vectors $x_2-x_1,...,x_n-x_1$ must be linearly dependent (since $n-1>d$). Hence there are some numbers $\mu_2,...,\mu_n$, not all zero, such that $\mu_2(x_2-x_1)+...+\mu_n(x_n-x_1)=0$. Let $\mu_1=-(\mu_2+...+\mu_n)$, so that $\mu_1+...+\mu_n=0$ and $\mu_1 x_1+...+\mu_n x_n=0$. These two equalities show that if we will add to the mass $\lambda_i$ at point $x_i$ the mass $k \mu_i$ for some $k\geq 0$ (the same $k$ for all points $x_i$), then the total mass of the system won't change and the location of the center of mass won't change as well. Since $\lambda_i$'s are all positive and at least one of the $\mu_i$'s is negative, there is some maximal $k$ so that $\lambda_i+k \mu_i$ is still non-negative for all $i$. For such $k$ one of the masses $\lambda_i+k \mu_i$ must vanish (otherwise, if all these masses are strictly positive, we can increase $k$ a little bit more).
\end{proof}
\section{Helly's theorem}
In this section we will prove the following remarkable theorem: if in a collection of convex subsets of $R^d$ 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 figure - three convex planar sets, each two intersect, but the three don't
Space for figure - 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 finite set of at least $d+2$ points in $R^d$, 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$.
Radon's lemma for the plane: Suppose we have a set $S$ that contains at least $4$ points on the plane $R^2$. 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 nondegenerate triangle. We will refer to the halfspaces defined by the lines $pq$,$qr$ and $rs$ and containing the triangle $pqr$ as $H_1,H_2$ and $H_3$. Take now any other point $s$ from $S$ (i.e. a point different 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 $H_1,H_2,H_3$. 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 $H_1$, the half-plane defined 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 $H_1$ and $H_2$, and outside the other one. Then the segments $pq$ (the one that defines 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 figure 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.
\begin{theorem}
If in a finite collection of convex sets every three intersect, then the intersection of all the sets in the collection is not empty.
\end{theorem}
\begin{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 verify the case $n=4$ separately, to give the reader a feeling for the general argument.
Let $G_1,G_2,G_3$ and $G_4$ be the four convex sets. Suppose that the intersection of every triple of them is non-empty. Let $A_1,A_2,A_3,A_4$ be points in these intersections, i.e. $A_1\in G_2\cap G_3 \cap G_4$, $A_2 \in G_1\cap G_3 \cap G_4$, $A_3 \in G_1\cap G_2 \cap G_4$ and $A_4 \in G_1\cap G_2 \cap G_3$. Radon's theorem tells us that we can subdivide the collection $A_1,A_2,A_3$ and $A_4$ to two subsets, whose convex hulls intersect. If one of the four points, say $A_1$ belongs to the convex hull of the other three, then $A_1$ must belong to $G_1$ - all three of the points $A_2,A_3,A_4$ belong to $G_1$ by their definition, hence any point in their convex hull belongs to $G_1$ as well. Since by its definition $A_1$ 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 $[A_1,A_2]$ and $[A_3,A_4]$ intersect at a point $P$. Since both $A_1$ and $A_2$ belong to $G_3$ and $G_4$, every point in their convex hull also belong both to $G_3$ and $G_4$. In particular the point $P$ lies in $G_3\cap G_4$. A similar argument about the points $A_3$ and $A_4$ and the sets $G_1$ and $G_2$ implies that $P$ belongs to $G_1\cap G_2$ as well. Hence $P$ belongs to the intersection of the four sets $G_1,G_2,G_3$ and $G_4$.
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 $A_i$ 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 $A_1,...,A_{n+1}$ to two subsets, whose convex hulls intersect. By renaming the sets if necessary,we can assume that the two subsets are $\{A_1,...,A_k\}$ and $\{A_{k+1}...,A_{n+1}\}$. Let $P$ be a point in the intersection of their convex hulls. Since all the points $A_1,...,A_k$ belong to $G_{k+1}\cap...\cap G_{n+1}$, all points in their convex hull also lie in this intersection. In particular the point $P$ lies there. Similarly, considering the points $A_{k+1},...,A_{n+1}$, we deduce that the point $P$ must lie in the intersection of the first $k$ sets, $G_1\cap...\cap G_k$. This shows that the point $P$ lies in the intersection of all the sets in the collection we started with.
\end{proof}
Let's see how we can apply Helly's theorem to a problem from geometry.
Problem: prove that if every three points of a finite collection of points in a plane lie inside some circle of radius one, then all the points of this 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 $p_1,p_2,p_3$ do not intersect is the same as saying that there is no point in the plane, whose distance from the three points $p_1,p_2,p_3$ is smaller than one. But this means also that there is no circle of radius one containing the three points $p_1,p_2,p_3$.
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.
Exercises about Helly's and Radon's theorems:
In the $d$-dimensional space $R^d$ Radon's theorem tells that if $S$ is a set of $n$ points in $R^d$ and $n\ge 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-1$-dimensional 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 $p_1,...,p_{d+2}$ and every collection of $d+1$ of them doesn't lie on one hyperplane. Show that we can find non-zero numbers $\lambda_1,...,\lambda_{n+1}$ with sum $1$, so that $p_{d+2}=\lambda_1 p_1+...+\lambda_{d+1} p_{d+1}$.
4. Suppose the numbers $\lambda_1,...,\lambda_k$ in the above representation $p_{d+2}=\lambda_1 p_1+...+\lambda_{d+1} p_{d+1}$ are positive and the other $\lambda$'s are negative. Show that there exist positive numbers $\mu_1,...,\mu_{d+2}$ such that $\mu_1+...+\mu_k=\mu_{k+1}+...+\mu_{d+2}$ and $$\frac{\mu_1 p_1 + ... +\mu_k p_k}{\mu_1+...+\mu_{k}}=\frac{\mu_{k+1} p_{k+1}+...+\mu_{d+2} p_{d+2}}{\mu_{k+1}+...+\mu_{d+2}}$$.
Hint: why the choice $\mu_1=\lambda_1,...,\mu_k=\lambda_k$,$\mu_{k+1}=-\lambda_{k+1},...,\mu_{d+1}=-\lambda_{d+1}$,$\mu_{d+2}=1$ works?
5. Deduce Radon's theorem from the result of step 4.
Exercise: deduce Helly's theorem in $d$-dimensional space $R^d$ from Radon's theorem proved in the exercise above. Namely show that if every $d+1$ sets in a finite 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.
\input{./chapter4/exercises4.tex}

\section{Dehn-Sommerville relations}

In this section we will talk about finite convex polytopes. To define a bounded convex polytope we will proceed in stages.

- A closed half-space in $R^n$ is the set of points lying on the same side of some hyperplane. Alternatively it is the set of points $x=(x_1,...,x_n)\in R^n$ satisfying the inequality $a_1 x_1 + ... a_n\cdot x_n \le c$ for given numbers $a_1,...,a_n,c\in R$.
- A closed convex figure is a figure obtained by intersecting (finitely or infinitely many) closed half-spaces. Later in this chapter we will show that this definition is equivalent to saying that the figure is convex if it is closed (in the sense of topology of subsets of $R^n$) and along with any two points in it, it contains the whole segment connecting them.
- A polytope is a closed convex figure that can be represented as intersection of finitely many closed half-spaces.
- A bounded convex polytope is a polytope, which is in addition bounded (i.e. there is some number $c$ that bounds the distance between any two points of the polytope from above).

We will refer to bounded convex polytopes in this section just as polytopes.Space for figure

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 $R^n$. In particular only $n$ edges meet at every vertex.

Exercise: prove that any face of a simple polytope is a simple polytope (in the affine space spanned by it).

With any polytope we will associate an $n$-tuple of numbers $(f_0,...,f_n)$ that describe some of its combinatorics. Namely $f_0$ will be the number of vertices of the polytope, $f_1$ - the number of edges, $f_2$ - the number of $2$-dimensional faces, $f_k$ - the number of $k$-dimensional faces. For example $f_n$ is always just $1$ - a polytope has only one $n$-dimensional face.

At first sight it might seem that these numbers $f_0,...,f_n$ might be more or less arbitrary. However there are some relations that they always satisfy. For example Euler has noticed that $f_0-f_1+f_2-...+(-1)^n f_n$ is always equal to one.

In fact we will see below that in case of a simple polytope, the numbers $f_0,...,f_n$ possess a hidden and marvelous symmetry. Let's now build the tools to uncover it.

It is convenient to package the number $f_0,...,f_n$ into one polynomial $f(t)=f_0+f_1 t+ ... + f_n t^n$. We will also need the polynomial $h$ defined by $h(t)=f(t-1)$.

It turns out that the beautiful properties of the numbers $f_0,...,f_n$ are most easily expressed in terms of the coefficients $h_0,...,h_n$ of this last polynomial $h(t)=h_0+h_1 t+...+h_n t^n$. For instance Euler's observation $f_0-f_1+f_2-...+(-1)^n f_n=1$ translates into the statement that $h_0=f(-1)=1$.

Now we will state the main result presented in this section, the Dehn-Sommerville relations.

Theorem: the numbers $h_0,...,h_n$ associated to a simple polyhedron satisfy

- $h_i=h_{n-i}$ (symmetry)
- $h_i\ge 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 definitions will be crucial for the proof.

- A linear functional $L$ on $R^n$ is a linear function $L:R^n->R$. A linear functional always has the form $L(x_1,...,x_n)=a_1 x_1+...+a_n x_n$ for some real numbers $a_1,...,a_n$. We will abbreviate this by writing $L(x)=<a,x>$.

*The functional $L$ is generic with respect to a given polyhedron if it assumes different values at all the vertices.It is clear that if $v_1,...,v_k$ are the vertices of the polytope, then the functional $L(x)=<a,x>$ is non-generic with respect to the polytope if and only if $<a,v_i>=<a,v_j>$ for some pair of indices $i,j$, or, equivalently $a$ belongs to the hyperplane defined by the equation $<a,v_i-v_j>=0$. Since the number of vectors of the form $v_i-v_j$ is finite, the generic functionals are abundant - except for some vectors $a$ in a finite union of hyperplanes, all the functionals are generic.

*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 figure.

Now we will present the main lemma needed for the proof:

For every functional $l$ generic with respect to the polytope $P$, the number $\tilde{h}_i$ of vertices of index $i$ is equal to the number $h_i$ - the $i$-th coefficient of the $h$-polynomial of the polytope $P$.

Proof: We will call a vertex $v$ maximal for the face $F$ if the functional $L$ (considered as a function on the face $F$) attains its maximum on the face $F$ at the vertex $v$. The assumption of genericity of the functional $L$ 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 $f_m$ of $m$-dimensional faces of the polytope $P$.

We can compute this number in a different way - counting the number of relevant faces for each vertex first and then summing up the results over all vertices. So let $v$ be some vertex. Suppose that it has index $i$. Then the number of $m$-dimensional faces for which $v$ is the maximal vertex is $i \choose m$ - there are $i$ edges going out of $v$ along $L$ is decreasing and choice of an $m$-dimensional face for which $v$ is the maximal vertex is equivalent to a choice of $m$ of these edges.

Note that here we use strongly the assumption that $P$ was simple - if $P$ is not simple, then different choices of $m$ edges may lead to the same choice of $m$-dimensional face.

Space for figure.

So to find the number of pairs $(F,v)$ of $m$-dimensional faces $F$ for which the vertex $v$ is maximal, we should sum the numbers $i \choose m$ over all vertices of index $i$ and over all indices $i$. So the number of such pairs is equal to $\sum_{i\ge m}{i\choose m \tilde{h}_i}$ (recall that $\tilde{h}_i$ denotes the number of vertices of index $i$).

Comparing the two ways of counting we can conclude that $f_i=\sum_{i\ge m}{i\choose m \tilde{h}_i}$. But this means that $$f(t)=\sum_{i=0}^n{f_i t^i}=\sum_{i=0}^n{\sum_{i\ge m}{i\choose m \tilde{h}_i} t^i}=\sum_{0\le m \le i \le n}{i\choose m \tilde{h}_i t^i}=\sum_{i=0}^n{(\sum_{m=0}^i{i \choose m t^m})\tilde{h}_i}=\sum_{i=0}^n{\tilde{h}_i(1+t)^i}$$.

Thus $f(t-1)=\sum_{i=0}^n{\tilde{h}_i t^i}$, or $h_i=\tilde{h}_i$.

To conclude, we just showed that $\tilde{h}_i$, the number of vertices of index $i$ with respect to the linear functional $L$ is equal to $h_i$, 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 $h_i$ of vertices of index $i$ with respect to functional $L$ is equal to the number $h_{n-i}$ of the vertices of index $n-i$ for the functional $-L$. This proves the first part of the theorem: $h_i=h_{n-i}$.

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 $h_i$ of index $i$ vertices will be at least $1$.

This proves the final assertion of Dehn-Sommerville theorem.

Exercise: find all $h$ and $f$ polynomials for 3-dimensional polytopes (usually referred to as polyhedra). For each one of the polynomials find an example of polyhedron that realizes this polynomial.

\section{Convex closed sets}

In this section we will focus on properties of mare general convex sets.

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.

A subset $\delta$ of an Euclidean space is called \textbf{convex} if along with any two points $a$ and $b$ in $\delta$, the whole line segment joining $a$ and $b$ is contained in $\delta$.

Space for figure.

Note that an intersection of an arbitrary collection of convex sets is convex again.

Also note that a half-space $\{x|<a,x>\leq c\}$ is an example of a convex set. Intersections of half-spaces provide us a lot of additional examples of convex sets.

One should note however, that all examples obtained in this way have to be closed\footnote{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.}.

Our first 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:

Separation theorem: Let $p$ be a point located outside a closed convex set $\delta$. Then there exists a hyperplane that separates them, i.e. a hyperplane with the property that the point $p$ and the set $\delta$ lie on different sides of it.

\begin{proof}

First we will prove that there exists a point $q$ in $\delta$ that realizes the distance between the point $p$ and the set $\delta$. Indeed, by definition the distance $d$ between the point $p$ and the set $\delta$ is the infimum of distances between $p$ and points in $\delta$. Let $q_i$ denote a sequence of points of $\delta$ such that $lim_{i->\infty}{dist(p,q_i)}=dist(p,\delta)$ ($dist$ denotes the Euclidean distance). The sequence $q_i$ is bounded (starting from some index $i_0$ all $q_i$'s satisfy $dist(p,q_i)<dist(p,\delta)+1$, hence $norm(q_i)<norm(p)+dist(p,\delta)+1$) and hence there exists a converging subsequence of it. Let $q$ denote the limit of this subsequence. By closedness assumption on the set $\delta$ the point $q$ belongs to it and by continuity of the distance, $dist(p,q)=dist(p,\delta)$.

Now let $H$ be the hyperplane orthogonal to the segment $p q$ and such that $p$ and $q$ lie on different sides of it. We claim that $H$ separates $p$ from $\delta$. Indeed, if $r$ is any point in $\delta$, then the segment from $q$ to $r$ must be contained in $\delta$. Since the distance from $p$ to any point on this segment must be greater that the distance from $p$ to $q$, the angle $p q r$ must be obtuse (greater than 90 degrees). This implies that $r$ is on the same side of $H$ as $q$ is.

\end{proof}

Now we can prove that a convex closed set is an intersection of half-spaces: let $\delta$ be any closed convex set and $\tilde{\delta}$ be the convex closed set obtained as the intersection of all half-spaces that contain $\delta$. Clearly the set $\delta$ is contained in $\tilde{\delta}$. If a point $p$ does not belong to $\delta$, then there is a hyperplane that separates $p$ from $\delta$, so p does not belong to the half-space determined by this hyperplane and containing $\delta$. Thus $p$ doesn't belong to $\tilde{delta}$ - the intersection of all half-spaces that contain $\delta$. This way we showed that $\delta=\tilde{delta}$.

\section{Convex hull}

We will study now the minimal convex set that contains a given one.

Definition: the convex hull $\delta(S)$ of the set $S$ is the smallest convex closed set that contains $S$. It can be desribed 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 half-spaces that contain $S$.

For example the sonvex hull of a finite 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: a point $p$ belongs to the convex hull of the set $S$ if and only if there exist points $x_1,...,x_m\in S$ and numbers $\lambda_1,...,\lambda_m\ge0$ such that $\lambda_1+...+\lambda_m=1$ and $p=\lambda_1 x_1+...+\lambda_m x_m$.

\begin{proof} first we show the implication that if $x_1,...,x_n$ belong to $S$ and $\lambda_1,...,\lambda_m$ are positive numbers such that $\lambda_1+...+\lambda_m=1$, then $\lambda_1 x_1+...+\lambda_m x_m$ belongs to the convex hull of $S$. We show this by induction on $m$. If $m=1$, then $\lambda_1=1$ and the claim is obvious. Suppose we proved the claim for $m$ and want to show it for $m+1$. The point $\lambda_1 x_1+...+\lambda_m x_m+\lambda_{m+1} x_{m+1}$ is the center of mass of the system of positive masses $\lambda_1,...,\lambda_{m+1}$ located at points $x_1,...,x_{m+1}$. By the properties of center of mass, it must be located on the segment connecting the point $x_{m+1}$ to the center of mass of the system $C$ of masses $\lambda_1,...,\lambda_m$ located at the points $x_1,...,x_m$. By inductive assumption, this center of mass $C$ lies in the convex hull. Clearly $x_{m+1}$ lies in the convex hull as well. Since the convex hull of any set is convex, the entire segment connecting $x_{m+1}$ to $C$ must lie in the convex hull, hence in particular the point $\lambda_1 x_1+...+\lambda_m x_m+\lambda_{m+1} x_{m+1}$ lies in the convex hull.

For the converse direction let $\tilde{\delta}$ be the set of linear combinations $\lambda_1 x_1+...+\lambda_m x_m$ of points in $S$ such that $\lambda_i\ge 0$ and $\lambda_1+...+\lambda_m=1$. This set is convex. Indeed, if $p$ is the center of mass of points $x_1,...,x_m$ with positive masses $\lambda_1,...,\lambda_m$ and $q$ is the center of masses of points $y_1,...,y_k$ with positive masses $\mu_1,...,\mu_k$, then any point $t p+(1-t) q$ on the segment connecting $p$ to $q$ is the center of mass of the system of masses $t\lambda_1,...,t\lambda_m,(1-t)\mu_1,...,(1-t)\mu_{k}$. Hence $\tilde{delta}$ contains the convex hull of $S$. But the first part of the proof shows that the convex hull is contained in $\tilde{\delta}$.

\end{proof}

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.

\begin{theorem}

If $S$ is a subset of $R^d$, then any point in the convex hull of $S$ can be written as $\lambda_1 x_1+...+\lambda_{d+1} x_{d+1}$ for some points $x_1,...,x_{d+1}$ in $S$ and numbers $\lambda_i\ge0$, $\lambda_1+...+\lambda_{d+1} =1$.

\end{theorem}

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

\begin{proof}

We already proved that any point $x$ can be written as the center of mass of some collection $\lambda_1,...,\lambda_m$ of positive masses of sum $1$ of points $x_1,...,x_n$. 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 making one of the masses in the end of the process equal to zero.

Here's how we do it: the $n-1$ vectors $x_2-x_1,...,x_n-x_1$ must be linearly dependent (since $n-1>d$). Hence there are some numbers $\mu_2,...,\mu_n$, not all zero, such that $\mu_2(x_2-x_1)+...+\mu_n(x_n-x_1)=0$. Let $\mu_1=-(\mu_2+...+\mu_n)$, so that $\mu_1+...+\mu_n=0$ and $\mu_1 x_1+...+\mu_n x_n=0$. These two equalities show that if we will add to the mass $\lambda_i$ at point $x_i$ the mass $k \mu_i$ for some $k\geq 0$ (the same $k$ for all points $x_i$), then the total mass of the system won't change and the location of the center of mass won't change as well. Since $\lambda_i$'s are all positive and at least one of the $\mu_i$'s is negative, there is some maximal $k$ so that $\lambda_i+k \mu_i$ is still non-negative for all $i$. For such $k$ one of the masses $\lambda_i+k \mu_i$ must vanish (otherwise, if all these masses are strictly positive, we can increase $k$ a little bit more).

\end{proof}

\section{Helly's theorem}

In this section we will prove the following remarkable theorem: if in a collection of convex subsets of $R^d$ 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 figure - three convex planar sets, each two intersect, but the three don't

Space for figure - 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 finite set of at least $d+2$ points in $R^d$, 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$.

Radon's lemma for the plane: Suppose we have a set $S$ that contains at least $4$ points on the plane $R^2$. 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 nondegenerate triangle. We will refer to the halfspaces defined by the lines $pq$,$qr$ and $rs$ and containing the triangle $pqr$ as $H_1,H_2$ and $H_3$. Take now any other point $s$ from $S$ (i.e. a point different 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 $H_1,H_2,H_3$. 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 $H_1$, the half-plane defined 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 $H_1$ and $H_2$, and outside the other one. Then the segments $pq$ (the one that defines 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 figure 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.

\begin{theorem}

If in a finite collection of convex sets every three intersect, then the intersection of all the sets in the collection is not empty.

\end{theorem}

\begin{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 verify the case $n=4$ separately, to give the reader a feeling for the general argument.

Let $G_1,G_2,G_3$ and $G_4$ be the four convex sets. Suppose that the intersection of every triple of them is non-empty. Let $A_1,A_2,A_3,A_4$ be points in these intersections, i.e. $A_1\in G_2\cap G_3 \cap G_4$, $A_2 \in G_1\cap G_3 \cap G_4$, $A_3 \in G_1\cap G_2 \cap G_4$ and $A_4 \in G_1\cap G_2 \cap G_3$. Radon's theorem tells us that we can subdivide the collection $A_1,A_2,A_3$ and $A_4$ to two subsets, whose convex hulls intersect. If one of the four points, say $A_1$ belongs to the convex hull of the other three, then $A_1$ must belong to $G_1$ - all three of the points $A_2,A_3,A_4$ belong to $G_1$ by their definition, hence any point in their convex hull belongs to $G_1$ as well. Since by its definition $A_1$ 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 $[A_1,A_2]$ and $[A_3,A_4]$ intersect at a point $P$. Since both $A_1$ and $A_2$ belong to $G_3$ and $G_4$, every point in their convex hull also belong both to $G_3$ and $G_4$. In particular the point $P$ lies in $G_3\cap G_4$. A similar argument about the points $A_3$ and $A_4$ and the sets $G_1$ and $G_2$ implies that $P$ belongs to $G_1\cap G_2$ as well. Hence $P$ belongs to the intersection of the four sets $G_1,G_2,G_3$ and $G_4$.

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 $A_i$ 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 $A_1,...,A_{n+1}$ to two subsets, whose convex hulls intersect. By renaming the sets if necessary,we can assume that the two subsets are $\{A_1,...,A_k\}$ and $\{A_{k+1}...,A_{n+1}\}$. Let $P$ be a point in the intersection of their convex hulls. Since all the points $A_1,...,A_k$ belong to $G_{k+1}\cap...\cap G_{n+1}$, all points in their convex hull also lie in this intersection. In particular the point $P$ lies there. Similarly, considering the points $A_{k+1},...,A_{n+1}$, we deduce that the point $P$ must lie in the intersection of the first $k$ sets, $G_1\cap...\cap G_k$. This shows that the point $P$ lies in the intersection of all the sets in the collection we started with.

\end{proof}

Let's see how we can apply Helly's theorem to a problem from geometry.

Problem: prove that if every three points of a finite collection of points in a plane lie inside some circle of radius one, then all the points of this 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 $p_1,p_2,p_3$ do not intersect is the same as saying that there is no point in the plane, whose distance from the three points $p_1,p_2,p_3$ is smaller than one. But this means also that there is no circle of radius one containing the three points $p_1,p_2,p_3$.

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.

Exercises about Helly's and Radon's theorems:

In the $d$-dimensional space $R^d$ Radon's theorem tells that if $S$ is a set of $n$ points in $R^d$ and $n\ge 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-1$-dimensional 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 $p_1,...,p_{d+2}$ and every collection of $d+1$ of them doesn't lie on one hyperplane. Show that we can find non-zero numbers $\lambda_1,...,\lambda_{n+1}$ with sum $1$, so that $p_{d+2}=\lambda_1 p_1+...+\lambda_{d+1} p_{d+1}$.

4. Suppose the numbers $\lambda_1,...,\lambda_k$ in the above representation $p_{d+2}=\lambda_1 p_1+...+\lambda_{d+1} p_{d+1}$ are positive and the other $\lambda$'s are negative. Show that there exist positive numbers $\mu_1,...,\mu_{d+2}$ such that $\mu_1+...+\mu_k=\mu_{k+1}+...+\mu_{d+2}$ and $$\frac{\mu_1 p_1 + ... +\mu_k p_k}{\mu_1+...+\mu_{k}}=\frac{\mu_{k+1} p_{k+1}+...+\mu_{d+2} p_{d+2}}{\mu_{k+1}+...+\mu_{d+2}}$$.

Hint: why the choice $\mu_1=\lambda_1,...,\mu_k=\lambda_k$,$\mu_{k+1}=-\lambda_{k+1},...,\mu_{d+1}=-\lambda_{d+1}$,$\mu_{d+2}=1$ works?

5. Deduce Radon's theorem from the result of step 4.

Exercise: deduce Helly's theorem in $d$-dimensional space $R^d$ from Radon's theorem proved in the exercise above. Namely show that if every $d+1$ sets in a finite 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.

\input{./chapter4/exercises4.tex}