MIT Combinatorics Seminar

Inside-Out Polytopes

Thomas Zaslavsky (Binghamton)

Wednesday, March 15, 2006   4:30 pm    Room 2-105


A number of combinatorial problems can be viewed as problems of counting lattice points in a certain convex set, which may be full-dimensional or involve some linear equations. For this there is a well-developed theory. Other problems, like graph coloring, are similar but involve linear antiequations, where a quantity cannot equal a constant. 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.