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.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1178 |
| Date | 01 May 2005 |
| Creators | Spencer, Gwen |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HMC Senior Theses |
Page generated in 0.0023 seconds