Csaba Vincze (2013)

University of Debrecen

**Tartalom**

Kirchberger's theorem (1902) gives a combinatorial criteria for the existence of a separating hyperplane between compact sets in the space. To prove the theorem we need the notion of extreme points of a convex set and Krein-Milman's theorem related to the convex hull of the extreme points.

Let K be a convex subset in the space. Recall that the point p in K is called an extreme point if the punctured set K - {p} is also convex. Krein-Milman's theorem 7.2.1 states that each compact convex set K is the convex hull of its extreme points.

**Definition **Let D be a subset of the coordinate space of dimension n. The point q has the k-point simplicial
property[8] with respect to D if there exists a simplex spanned by the elements p(1), ..., p(r) such that r is at most k and q is in the convex hull of p(1), ..., p(r).

**Remark **In what follows D(k) denotes the elements of the convex hull having the k-point simplicial property with respect to D.

**Lemma 8.1.1 **
*Let D and E be compact subsets in the coordinate space of dimensionn such that *

$convD\cap convE\ne \mathrm{\varnothing}.$ |

If v is an extreme point of the intersection of the convex hulls, i and j are the smallest integers such that

$v\in {D}_{i}\cap {E}_{j}$ |

then i+j is at most n+2.

**Proof **According to Carathéodory's theorem 2.2.1 we have that

$convD={D}_{n+1}\text{}and\text{}convE={E}_{n+1}.$ |

Therefore

$i\le n+1\text{}and\text{}j\le n+1.$ |
(8.1) |

If (for example) i=1 then inequalities 8.1 say that

$i+j=1+j\le 1+n+1=n+2$ |

and the situation is similar in case of j=1. In what follows suppose that both i and j have values at least 2. Since v is in D(i) we have a simplex spanned by some elements p(1), ..., p(i) such that v is in their convex hull. Using that i cannot be reduced we have that there are no vanishing coefficients in the convex combination presenting v.

Therefore v can be included in a ball Γ(D) of dimension i - 1 in conv D; especially the inclusion is in the affine hull of p(1), ..., p(i). Similarly, there exists a ball Γ(E) of dimension j - 1 in conv E such that Γ(E) contains v. But v is an extremal point of the intersection of the convex hulls.

This means that the intersection of the balls must be a singleton containing only v and, consequently,

$n\ge \mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma}}_{D}\cup {\mathrm{\Gamma}}_{E}=\mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma}}_{D}+\mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Gamma}}_{E}=i-1+j-1=i+j-2$ |

showing that

$i+j\le n+2$ |

as was to be proved. ▮

**Theorem 8.1.2 **
*(Kirchberger, Paul). Let D and E be compact sets in the coordinate space of dimension n. They can be strictly separated by a hyperplane if and only if for each subset T of at most n+2 elements in D U E the sets *

$T\cap D\text{}and\text{}T\cap E$ |

can be strictly separated by a hyperplane.

**Proof **If D and E can be strictly separated by a hyperplane then of course their subsets can be strictly separated. Suppose that D and E can not be strictly separated and, consequently, their convex hulls have a non-empty intersection. If v is an extreme point of the intersection of the convex hulls then, by the previous lemma,

$v\in {D}_{i}\cap {E}_{j},$ |

where i+j is at most n+2. For the sake of definiteness suppose that

$v\in conv\{{p}_{1},\mathrm{\dots},{p}_{i}\}\cap conv\{{q}_{1},\mathrm{\dots},{q}_{j}\}$ |

for some elements p(1), ..., p(i) in D and q(1), ..., q(j) in E. Taking the set

$T:=\{{p}_{1},\mathrm{\dots},{p}_{i},{q}_{1},\mathrm{\dots},{q}_{j}\}$ |

the intersections

$T\cap D\text{}and\text{}T\cap E$ |

can not be strictly separated. By contraposition it follows that if for each subset T of at most n+2 elements in D U E the sets

$T\cap D\text{}and\text{}T\cap E$ |

can be strictly separated by a hyperplane then D and E can be strictly separated.

Kirchberger's theorem has a great significance in the solution of the problem how to decide the separability of finite point-sets. If we want to investigate directly the intersection of the convex hulls whether they are disjoint or not we should solve the equation

$\sum _{{v}_{i}\in D}{\lambda}_{i}{v}_{i}=\sum _{{w}_{j}\in E}{\mu}_{j}{w}_{j}$ |

under the additional conditions

$\sum {\lambda}_{i}=1\text{}and\text{}\sum {\mu}_{j}=1.$ |

Therefore we have m+k unknown parameters in a system of linear equations containing n+2 members, where m and k are the numbers of elements of the sets D and E, n is the dimension of the space (the number of coordinates). In case of m+k >> n+2 it seems to be very hard to solve because of the enormous amount of free parameters. Kirchberger's theorem provides a method to divide the solutionof the problem into several but elementary parts: after choosing elements v(1), ..., v(m') in D and w(1), ..., w(k') in E, respectively, the problem is reduced to the solution of the system

$\sum _{i=1}^{m\mathrm{\text{'}}}{\lambda}_{i}{v}_{i}=\sum _{j=1}^{k\mathrm{\text{'}}}{\mu}_{j}{w}_{j},\sum {\lambda}_{i}=1\text{}and\text{}\sum {\mu}_{j}=1.$ |

Here m'+k' is at most n+2 (the number of equations).