Two Pigeon Hole Principles and Unions of Convexly Disjoint Sets

Citation

Morris, Howard Cary (1974) Two Pigeon Hole Principles and Unions of Convexly Disjoint Sets. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/9djr-xf90. https://resolver.caltech.edu/CaltechTHESIS:01282021-003857087

Abstract

In Euclidean space Rⁿ, a set is convex if the set contains every straight line segment whose endpoints are in the given set. Suppose that a set C consisted of convex sets in Rⁿ, and that for any choice of n + 1 sets in C the n + 1 sets had a point in common. Then Helly's theorem states that any finite number of sets in C have a common point. (n+1) is known as the Helly number of convex sets in Rⁿ. One may ask if unions of k convex sets have a similar Helly's number. This paper puts convexity in the abstract, and imposes conditions on a set A (consisting of sets that are unions of k convex sets) such that A can be shown to have a Helly's number. This paper also considers an abstraction of the notion of "polygonally connected sets" from an abstract convexitist's point of view.

In showing that certain sets of unions of convex sets have an a Helly's number, a special case of a generalized pigeon hole principle is used. This paper also proves two generalized pigeon hole principles, and in many cases gives the best possible results. Both generalized pigeon hole principles make the following assumptions on a matrix A:

(1) there are n rows

(2) each row has at most ℓ zero's

(3) every submatrix of A, that does not have any zero entries, has at most k distinct (not identical) rows

(4) that numbers h and/or t are given.

One generalized pigeon hole principle states there exists a function χa(h, k, ℓ) such that if n ≥ χa(h, k, ℓ), then there must exist some h + 1 columns such that along every row of the matrix those h + 1 columns have the same entry with possibly ℓ exceptions. The other generalized pigeon hole principle states that there exists a function χe(h, k, ℓ, t) such that if n ≥ χe(h, k, ℓ, t), then there must exist some sh + t (s > 0) columns that can be partitioned into s sets of columns such that it is possible to make suitable changes to the zero entries in each of these sh + t columns in order to make those s sets of columns into s sets of equal columns. It is also shown that for certain values of h, k, ℓ, and t that χa(h, k, ℓ) = hk + 1 and χe(h, k, ℓ, t) = kh + t + (k-1)ℓ. It is also shown that there exists examples such that χe(h, k, ℓ, t) > hk + t + (k-1)ℓ.

Thesis Files