A Lovász-Kneser Theorem for Triangulations

Speaker: Anton Molnar (Emory) Abstract: In 1978, Lovász used topological techniques to determine the chromatic number of the Kneser graph of k-element subsets of [n]. We will discuss a new geometric setting by considering the Kneser graph of triangulations of a convex n-gon. Primarily, we will present a proof that the chromatic number is n−2. We will also talk about some other related problems such as the Hamiltonicity and independence number. Joint work with Cosmin Pohoata, Michael Zheng, and Daniel Zhu. Chapters: 00:00 Introduction 01:00 Lovász-Kneser Theorem 02:27 Triangulations of a Convex n-gon 04:30 Proof of Chromatic Number 06:30 Related Problems (Hamiltonicity, Independence Number) 08:28 Conclusion and Future Work