CaltechTHESIS
A Caltech Library Service

# 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 Rn, 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 Rn, 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 Rn. 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)ℓ.

Item Type: Thesis (Dissertation (Ph.D.)) Mathematics California Institute of Technology Physics, Mathematics and Astronomy Mathematics Public (worldwide access) Bohnenblust, Henri Frederic Bohnenblust, Henri Frederic 25 October 1973 CaltechTHESIS:01282021-003857087 https://resolver.caltech.edu/CaltechTHESIS:01282021-003857087 10.7907/9djr-xf90 No commercial reproduction, distribution, display or performance rights in this work are provided. 14059 CaltechTHESIS Benjamin Perez 04 Feb 2021 16:59 04 Feb 2021 17:00

## Thesis Files PDF - Final Version See Usage Policy. 18MB

Repository Staff Only: item control page