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/9djrxf90. https://resolver.caltech.edu/CaltechTHESIS:01282021003857087
Abstract
In Euclidean space R^{n}, 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^{n}, 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^{n}. 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 + (k1)ℓ. It is also shown that there exists examples such that χe(h, k, ℓ, t) > hk + t + (k1)ℓ.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Mathematics 
Degree Grantor:  California Institute of Technology 
Division:  Physics, Mathematics and Astronomy 
Major Option:  Mathematics 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  25 October 1973 
Record Number:  CaltechTHESIS:01282021003857087 
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:01282021003857087 
DOI:  10.7907/9djrxf90 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  14059 
Collection:  CaltechTHESIS 
Deposited By:  Benjamin Perez 
Deposited On:  04 Feb 2021 16:59 
Last Modified:  04 Feb 2021 17:00 
Thesis Files
PDF
 Final Version
See Usage Policy. 18MB 
Repository Staff Only: item control page