Seminar Details
Using the Borsuk-Ulam Theorem to Prove the Chromatic Number of the Knaser Graph
- Start Date: October 19, 2022
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Nilava Metya - Rutgers University
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Presentation Type: Stand Alone Presentation
- Abstract:
The Knaser graph K(n,k) is the graph whose vertices are the n-subsets of {1,2,..,2n+k} and two vertices are connected if and only if they don't intersect. An example is the Petersen graph (https://en.wikipedia.org/wiki/Petersen_graph) which is K(2,1). Knaser, in 1955, conjectured that the chromatic number of K(n,k) is k+2. In fact, the chromatic number for the Petersen graph is 1+2=3. I'll try to prove this conjecture in the limited time. The technique will be to show that k+2 is both the upper and lower bound. This graph is indeed (k+2)-colourable, which proves the upper bound. We'll use a combinatorial version of the Borsuk-Ulam theorem to prove the lower bound.