Seminar Details
Asymptotics for Palette Sparsification
- Start Date: October 30, 2023
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Charles Kenney - Rutgers University
- Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
- Presentation Type: Stand Alone Presentation
- Abstract:
Let G be a graph on n vertices with maximum degree D. If we sample a list of (1+o(1)) ln(n) colors uniformly at random from {1,2,...,D+1}, independently for each vertex of G, then with high probability there is a proper coloring of G from these lists. This confirms a conjecture that Assadi expressed at this seminar in 2021. We overview the proof, discuss connections to other problems, and conclude with a couple conjectures of our own.
Joint work with Jeff Kahn.