MIT Combinatorics Seminar
InsideOut Polytopes
Thomas Zaslavsky (Binghamton)
Wednesday, March 15, 2006 4:30 pm Room 2105
ABSTRACT

A number of combinatorial problems can be viewed as problems of counting
lattice points in a certain convex set, which may be fulldimensional or
involve some linear equations. For this there is a welldeveloped 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.


