A Caltech Library Service

Two Pigeon Hole Principles and Unions of Convexly Disjoint Sets


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.


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.))
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):
  • Bohnenblust, Henri Frederic
Thesis Committee:
  • Bohnenblust, Henri Frederic
Defense Date:25 October 1973
Record Number:CaltechTHESIS:01282021-003857087
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14059
Deposited By: Benjamin Perez
Deposited On:04 Feb 2021 16:59
Last Modified:04 Feb 2021 17:00

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page