Return to Colloquia & Seminar listing
A Simple Proof of the Kneser-Lovasz Theorem
Student-Run Discrete Mathematics| Speaker: | Matt Stamps, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Apr 3 2008, 12:00AM |
Description
Consider the problem of partitioning the $n$-element subsets of a
$2n+k$-element set such that any two of the $n$-element subsets contained
in the same partition class are pairwise intersecting. In 1955, Kneser
showed that this can always be done with $k+2$ classes. He also
conjectured that $k+2$ is the least possible number of classes in such a
partition. This conjecture was open for several decades until Lovasz gave
a proof using techniques in algebraic topology. I'll give a much simpler
proof of this theorem due to Joshua Greene in 2002.