Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

4. fejezet - Generalizations and Applications

4. fejezet - Generalizations and Applications

Helly's theorem can be extended to infinite collections of convex sets but not without some additional restrictions as we shall see.

4.1 Helly's theorem: generalizations and applications

Theorem 4.1.1 (The countable version) Let B be the collection consisting of the sequence

B 1 , , B k ,

of compact convex sets in the coordinate space of dimension n. If every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Using the original version 3.3.1 of Helly's theorem we can produce a sequence

p 1 B 1 B n + 1 , , p m B 1 B n + m ,

Because of the compactness we can choose a convergent subsequence with the limit point p*. It is obviously a common point in all the members in B because if the index of the elements in the subsequence is large enough then the sequence runs in the corresponding compact set from B. ▮

Theorem 4.1.2 (The general version). Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 members. If every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Suppose, in contrary, that the intersection of the members in B is the empty-set. Then the union of their complement is just an open cover of the space. By Lindelöf theorem 1.2.1 we can choose acountable subcover and, consequently, the intersection of the corresponding members from B must be also empty. This contradicts to the countable version 4.1.1. ▮

In what follows we adopt the results in chapter 3 to the general version 4.1.2 of Helly's theorem together with some new applications.

Theorem 4.1.3 (Klee, Victor) Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that Bcontains at least n+1 member. If K is a non-empty subset and for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them then there exists a translate of K contained in all the members of B.

Proof Consider a new collection A of subsets

A γ = { p E n | p + K B γ } ,

(4.1)

where γ runs through the index set Γ. We are going to prove that A satisfies the conditions in the general version 4.1.2 of Helly's theorem. For the sake of definiteness consider two points p and q belonging to the member A(γ) of the family 4.1:

p + K B γ   a n d   q + K B γ .

(4.2)

Let λ be a real number between 0 and 1. If v is an element from the set

λ p + ( 1 - λ ) q + K

then it can be written into the form

v = λ p + ( 1 - λ ) q + w = λ ( p + w ) + ( 1 - λ ) ( q + w )

for some w in K. By our hypothesis 4.2

p + w B γ   a n d   q + w B γ

together with their convex combination v. Therefore

λ p + ( 1 - λ ) q A γ

(condition of the convexity). On the other hand suppose that the sequence p(m) in A(γ) tends to the limit p. Then for any k in K

l i m m p m + k = p + k B γ

because p(m)+k is in B(γ) and B(γ) is compact (especially closed). This means that p+K is a subset in B(γ), i.e. p is in A(γ) (condition of closedness). Finally K is bounded because compact (especially bounded) subsets contain translates of K. So is each member of A. Since for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them, every subfamily of n+1sets in A has a non-empty intersection. The general version 4.1.2 of Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K is contained in all the members of B. ▮

Theorem 4.1.4 (Klee, Victor) Let B be the family of compact convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 member. If K is a non-empty compact convex set and for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them then there exists a translate of K containing all the members of B.

Proof Consider a new collection A of subsets

A γ = { p E n | B γ p + K } ,

(4.3)

where γ runs through the index set Γ. We are going to prove that A satisfies the conditions in the general version 4.1.2 of Helly's theorem. For the sake of definiteness consider two points p and q belonging to the member A(γ) of the family 4.3:

B γ p + K   a n d   B γ q + K .

(4.4)

If b(γ) is in B(γ) then, by our hypothesis 4.4,

b γ = p + w   a n d   b γ = q + z

for some elements w and z in K. Let λ be a real number between 0 and 1. Then

b γ = λ b γ + ( 1 - λ ) b γ = λ p + ( 1 - λ ) q + λ w + ( 1 - λ ) z

and the convex combination of w and z is in K because of the convexity. Therefore

b γ λ p + ( 1 - λ ) q + K

and

λ p + ( 1 - λ ) q A γ

(condition of the convexity). On the other hand suppose that the sequence p(m) in A(γ) tends to the limit p. By the definition of A(γ) any element b(γ) in B(γ) can be written into the form

b γ = p m + v m

for a sequence v(m) of elements in K. Since K is compact (especially closed)

l i m m ( b γ - p m ) = b γ - p = l i m m v m K

and, consequently,

B γ p + K p A γ

(condition of closedness). Finally K is bounded and its translates with elements from A(γ) must cover a compact (especially bounded) subset B(γ). This means that A(γ) must be bounded. Since for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. The general version 4.1.2 of Helly's theorem implies that the familyof all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K contains all the members of B. ▮

Finally we present a Helly-type theorem without any condition of compactness for the member of the family of sets. In order to motivate the result discuss the following outline how to prove the general version of Helly's theorem:

(i) conditions (compactness, convexity, non-empty intersection of every subfamily containing n+1 members) --> countable version of Helly's theorem,

(ii indirect argumentation involving Lindelöf's theorem --> contradiction to the countable version.

In order to avoid compactness in the conditions the following result use the countable version directly as a requirement.

Theorem 4.1.5 Let B be the family of closed subsets in the coordinate space of dimension n and suppose that every countable subfamily of B has a non-empty intersection. Then the family of all the members in B has anon-empty intersection.

Closedness can be substituted with convexity as well.

Theorem 4.1.6 (Klee, Victor) Let B be the family of convex subsets in the coordinate space of dimension n and suppose that every countable subfamily of B has a non-empty intersection. Then the family of all the members in B has a non-empty intersection.

For the proof of a more general theorem see chapter 6, see also [35].

Theorem 4.1.7 Let B be the family of closed convex sets in the coordinate space of dimension n and suppose that B contains at least n+1 members. If one of them is compact and every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Proof Let K be the distinguished compact element of the family and apply the general version to the collection

K B γ ( γ Γ ) .

All the new sets are compact and every subfamily of n+1 sets in the new collection has a non-empty intersection because of the finite version of Helly's theorem. Therefore the general version 4.1.2 implies that all sets in B has a non-empty intersection.