טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMichal Lenkiewicz
SubjectIntersecting Convex Sets
DepartmentDepartment of Mathematics
Supervisor Professor Emeritus Katchalski Meir
Full Thesis textFull thesis text - English Version


Abstract

This work is closely related to a well known theorem of Eduard Helly on convex sets in d-dimensional Euclidean space.

Helly's theorem asserts that for a finite family of convex sets in Rd, the intersection of all sets is nonempty, provided that the intersection of every d or less sets is non empty.

Meir Katchalski extended results of Branko Grünbaum and proved that the intersection of the members of such a family is at least k-dimensional, provided that the intersection of every f(k,d)=min{d,2(d-k)}  sets or less is at least k-dimensional.

Another closely related result by Katchalski for such families is that the intersection of the members of such a family contains a ray, provided that the intersection of every 2d or less sets contains a ray.

We extend this result and prove that for every k at most d, the intersection of the members of the family contains a k-dimensional convex cone, provided that the intersection of every f(k,d) sets or less  contains a convex cone of dimension k.  The constant f(k,d) is best possible.

The proof utilizes properties of families of convex cones with apex zero in Rd for which the intersection of the members of the family is {0}.

We prove that for any such family of convex cones {A1,?,Ad} with apex  0 in Rd and intersection equal to {0},  there are disjoint subsets T1,?,Tt of T={1,?,d}, such that A(T\Ti) is a subspace of dimension |Ti|-1, where A(T\Ti) is the intersection of all sets Aj of the family  with j in T\Ti.

This is related to results of Katchalski on nondegenerate families of convex cones. A nonempty family  of convex cones with apex 0 in Rd is called a nondegenerate family (N.D.F) if each member of the family is d-dimensional and the intersection of any r members of the family is at least (d-r)-dimensional for 0<r<d and the intersection of all members of the family is the origin.

We also prove and use results which force the intersection of a family to be at least 1-dimensional.

 A typical such result is the following: For {A1,?,Ad} a finite family of convex sets in Rd, if the intersection of all sets is nonempty  and the sum of the dimensions of the intersection of all sets but one is greater than d(d) then the dimension of the intersection of all members of the family is greater than 0. Moreover, if there are exactly d sets in the family then the dimension of the intersection of all members of the family is equal to d.