homeinfotalkspeoplelinksarchive

MIT Combinatorics Seminar

Reducibility for the four-color theorem and related conjectures

Sergey Norin  (Georgia Institute of Technology)

Wednesday, February 07, 2007    4:00 pm (unusual time!)   Room 2-136


ABSTRACT

Known proofs of the Four-Color Theorem consist of two steps - reducibility and discharging. While the discharging part is essentially human-checkable, the reducibility part is far from it. Reducibility is a useful technique that allows one to deduce that certain configurations cannot appear in a minimal counterexample, but it lacks a general theory.

Related notions of reducibility have been developed for the cycle double cover conjecture of Seymour and Szekeres and the 5-flow conjecture of Tutte. To settle these conjectures completely using this technique one would need the reducibility of an infinite sequence of configurations, and therefore at least a modest theory of reducibility.

We explain the technique of reducibility and discuss new results pertaining to the Four-Color Theorem and the 5-flow conjecture. This talk is based on joint work with Robin Thomas.