Thomas Zaslavsky

Inside-Out Polytopes

Abstract for the Combinatorics and Number Theory Seminar
2002 November 18 (Monday)

A number of combinatorial problems can be viewed as problems of counting lattice points in a certain convex set. For this there is a well-developed theory. Other problems, like graph coloring, are similar but involve inequality constraints. Matthias Beck and I have found a way to modify the standard theory so it can apply to such problems. I will show how this is done and how it yields new insights into coloring of graphs and signed graphs, counting magic squares, etc.