Combinatorial Consequences of Relatives of the Lusternik-Schnirelmann-Borsuk Theorem

Author

Gwen Spencer, Harvey Mudd College

Graduation Year

2005

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Francis Edward Su

Reader 2

Alfonso Castro

Abstract

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.

Recommended Citation

Spencer, Gwen, "Combinatorial Consequences of Relatives of the Lusternik-Schnirelmann-Borsuk Theorem" (2005). HMC Senior Theses. 175.
https://scholarship.claremont.edu/hmc_theses/175