Joint graduate student seminar - Pure Mathematics/Combinatorics & Optimization

Tuesday, February 5, 2013 4:30 pm - 4:30 pm EST (GMT -05:00)

Speakers:
Ian Payne - Pure Mathematics
Georg Osang - Combinatorics & Optimization

"The Payne Conjecture"

This is a collaborative colloquium with graduate students from the Pure Math and C&O departments. Our first speaker, Ian Payne, will introduce the list homomorphism problem, which he recently showed was NP-complete for even cycles of length at least six. While attempting to reduce the case for graphs with even girth to the case for even cycles, Ian conjectured that every graph with girth eight would contain at least one pair of vertices at distance four that lie on a unique cycle. During his talk Ian will explain how this conjecture would imply that list homomorphism is NP-complete for graphs with girth eight.
At a recent pub night, Ian shared his conjecture with some of the C&O grads. Our second speaker, Georg Osang, immediately began constructing a counterexample. After some discussion Georg realized that the well-known Tutte-Coxeter is a minimal counterexample. During his talk Georg will describe the Tutte-Coxeter graph and explain how it disproves the Payne conjecture. Following the colloquium there will be a social event at the Grad House.