Mathematical Sciences - Colloquium

Professor Matt DeVos
Princeton University

From Coloring Planar Graphs to Choosability in Vector Spaces

Tutte discovered an interesting connection between coloring planar graphs and nowhere-zero flows.  For planar dual graphs G and G*, he showed that k-colorings of G dualize no nowhere-zero k-flows of G*.  Based on this duality, Tutte made three fascinating conjectures concerning nowhere-zero flows.  All three of these conjectures are still open.

After exploring this duality and discussing some known properties of nowhere-zero flows, we move on to a more general perspective:
choosability in vector spaces.  In this realm we discuss what is known to be true and what is conjectured to be true.   In particular, we give two choosability theorems about matrices over fields of characteristic two which generalize Jaeger's 4-flow and 8-flow theorems, and we suggest a new conjecture about matrices over fields of odd characteristic which would imply Tutte's 5-flow conjecture.

Friday, 7 September 2001
4:10 p.m. in James E Todd Building CE 203-204
Reception at 3:30 p.m. CE 204

This talk is part of The Big Sky Conference, sponsored by the National Science Foundation 
and the Department of Mathematical Sciences. 


Fall 2001 Colloquium Schedule | Mathematical Sciences home | The University of Montana home