Logo

Mathematical Sciences Research Institute

Home » GTC Main Seminar: Colorful complete bipartite subgraphs in generalized Kneser graphs

Seminar

GTC Main Seminar: Colorful complete bipartite subgraphs in generalized Kneser graphs August 30, 2017 (10:00 AM PDT - 11:00 AM PDT)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Frédéric Meunier (École Nationale des Ponts-et-Chaussées)
Description No Description
Video
No Video Uploaded
Abstract/Media

Any proper coloring of a Kneser graph with a minimum number of colors contains an almost-complete bipartite subgraph with all colors on each side. (An almost-complete bipartite graph is a complete bipartite graph minus a perfect matching.) This is a theorem due to Chen (2012), which solved a conjecture about the circular chromatic number of Kneser graphs. We prove that such a "colorful" subgraph still exists for the generalized Kneser graphs (obtained from any hypergraph), and for their categorical products, when they match a certain topological lower bound for the chromatic number (Dol’nikov’s bound). This result has some consequences for the circular chromatic number and Hedetniemi’s conjecture.



Joint work with Meysam Alishahi and Hossein Hajiabolhassan.

No Notes/Supplements Uploaded No Video Files Uploaded