April 29 & 30, 2006
Margaret Bayer* & T. Bisztriczky
Some special nonsimplicial polytopes
Cyclic polytopes play a special role in the combinatorial study of simplicial
polytopes. Bisztriczky introduced nonsimplicial analogues of cyclic polytopes.
The construction depends on parity of the dimension. In odd dimensions there
are the ordinary polytopes, which were studied extensively by Bisztriczky, by
Dinh and by Bayer. In even dimensions there are the periodically-cyclic Gale
polytopes. Here we find analogues of some results on ordinary polytopes for
periodically-cyclic Gale polytopes.
Fu Liu
Ehrhart polynomials of lattice-face polytopes
There is a simple formula for the Ehrhart polynomial of a cyclic polytope. In
this talk, we will explain that the same formula holds for a more general class
of polytopes, lattice-face polytopes. We develop a way of decomposing any
d-dimensional simplex in general position into d! signed sets and carefully
count the number of lattice points inside them. We are thus able to conclude
the desired formula.
Kevin Woods
Periods of Ehrhart quasi-polynomials
Given a rational polytope P, iP(n) := #(nP \cap Zd) is a
quasi-polynomial in n, that is, there exist a period D and
polynomial functions f1, ..., fD such that iP(n) = fj(n)
for n = j mod D. This function iP(n) is called the
Ehrhart quasi-polynomial of P. The minimum period
of iP(n) must divide D(P) = min{n in N: nP
is an integral polytope}, and for most polytopes the minimum period
is exactly D(P). In some interesting real world--real
math-world, at least--examples, the period of iP(n) is mysteriously
smaller.
This motivates the study of periods of Ehrhart quasi-polynomials, and we will
present a survey of some results along this line. We give examples to show
that difference between D and the actual minimal period can be
arbitrarily "bad." We also examine better bounds on the periods of the
coefficients of the Ehrhart quasi-polynomials. Finally, we examine the
computational complexity of determining the minimum period, using the tool of
rational generating functions. Along the way, we will present a number of open
questions related to these periods.
Mike Develin* & Josephine Yu
Tropical polytopes
Tropical polytopes are polytopes over the max-plus semiring. These turn out to
be geometric objects which are even more purely combinatorial than our
combinatorial friends, ordinary polytopes; we will present the current state of
the theory, defining their faces and using them to construct cellular
resolutions of monomial ideals. We will also be presenting a large number of
either conjectures or theorems, depending on what happens between this abstract
submission deadline and the conference itself.
Alicia Dickenstein, Eva-Maria Feichtner* & Bernd Sturmfels
Newton polytopes of A-discriminants
Given an integer point configuration A, we provide a positive
formula for the extreme monomials of the A-discriminant without
any smoothness assumption. Our approach is via tropical geometry.
It is based on the fact that the tropicalized A-discriminant can
be described in terms of well-studied objects from geometric
combinatorics.
Geir Agnarsson & Walter Morris*
Minkowski sums of simplices
We study the combinatorics of the face lattice of the Minkowski sum
of k simplices, each of which is generated by a subset of the set of standard
basis vectors in Rr. We prove some results on the graphs of such polytopes
and introduce a "master polytope," the faces of which generate all these
polytopes.
Alexander Postnikov
Permutohedra reshaped
We discuss various generalizations of the associahedron
and the permutohedron that recently came up in several
different areas. We calculate volumes and count numbers
of lattice points, numbers of vertices, and f-vectors
of these polytopes.
Christophe Hohlweg & Carsten Lange*
Realizations of the associahedron and cyclohedron
We describe many different realizations with integer coordinates
for the associahedron (i.e., the Stasheff polytope) and for the cyclohedron
(i.e., the Bott-Taubes polytope) and compare them to the permutahedron of
type A and B respectively.
The coordinates are obtained by an algorithm which uses an oriented
Coxeter graph of type A or B respectively as only
input and which specialises to a procedure presented by J.-L. Loday
for a certain orientation of A.
Helaman Ferguson & Sinai Robins*
Integer linear programming using differentiable Dedekind sums from analytic number theory
One of the most fundamental problems in integer linear
programming is that of finding an integer point inside a
given rational polytope. Here we develop a new tool to solve this problem. We
first give a survey of the history of Dedekind sums, and show the current state
of a recently
developed theory of higher dimensional differentiable
Dedekind sums.
We next use these differentiable Dedekind sums to locate
integer points in rational polytopes. Some examples in low
dimensions will be given. Moreover, no background in
Dedekind sums is assumed at all, to maximize accessibility
for the casual mathematical observer.
Akimichi Takemura & Ruriko Yoshida*
Fundamental holes and saturation points of a commutative semigroup and their applications to contingency tables
Suppose we have a commutative semigroup generated by a finite subset of Zd
and its saturation. In 2006 we showed
the necessary and sufficient conditions for the given semigroup to have a
finite number of elements in
the difference between the semigroup and its saturation. Also we defined
saturation points, minimal saturation points, and fundamental holes and we
showed the simultaneous finiteness of holes, nonsaturation points, and minimal
saturation points.
In this talk we will show our new results and we will show some simulation
results on contingency tables.
Jesus De Loera* & Shmuel Onn
A canonical form for polytopes and its algorithmic consequences
In this talk we present the following result: Every convex polytope
is a face of an axial 3-way transportation polytope. The face in
question can be found very explicitly, which in a way means that one
can rewrite any linear inequality system into a special canonical form. This
has several interesting consequences in linear and integer programming.