Graduation Year


Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science



Reader 1

Francis Edward Su

Reader 2

Alfonso Castro


Call a set of 2n + k elements Kneser colored when its n-subsets are put into classes such that disjoint n-subsets are in different classes. Kneser showed that k + 2 classes are sufficient to Kneser-color the n-subsets of a 2n + k element set. There are several proofs that this same number is necessary which rely on fixed-point theorems related to the Lusternik-Schnirelmann- Borsuk (LSB) theorem. By employing generalizations of these theorems we expand the proofs mentioned to obtain proofs of an original result we call the Subcoloring theorem. The Subcoloring theorem asserts the existence of a partition of a Kneser-colored set that halves its classes in a special way. We demonstrate both a topological proof and a combinatorial proof of this main result. We present an original corollary that extends the Subcoloring theorem by providing bounds on the size of the pieces of the asserted partition. Throughout, we formulate our results both in combinatorial and graph theoretic terminology.

gspencer.jpg (7 kB)
A picture of Gwen Spencer

kneser.pdf (152 kB)
A paper on work described in this thesis

lsbkkm.pdf (101 kB)
The Lusternik-Schnirelmann-Borsuk Theorem Implies the KKM Lemma

gspencer-2005-prop.pdf (72 kB)
Thesis Proposal

gspencer_2005_presentation.pdf (261 kB)
Presentation Slides