April 25 & 26, 2009
Benjamin Braun
Nowhere harmonic colorings of graphs
Given a simple graph, proper graph colorings and
nowhere-zero integer flows are combinatorial structures with interesting enumerative properties. We describe a related combinatorial
structure, nowhere harmonic colorings, and show
that they are also interesting from an enumerative perspective. Using
the theory of inside out polytopes, we obtain
enumerative results regarding nowhere harmonic colorings involving
quasipolynomials and a combinatorial reciprocity
theorem. Joint work with Matthias Beck.
Jesus De Loera
Subgraph Isomorphism through Polynomial Ideals and their relaxations
Given two graphs G and H, the subgraph isomorphism problem asks
whether there is a subgraph of G isomorphic to H. Instances of this
question include a wide range of famous questions in Graph Theory (e.g.
graph isomorphism, existence of hamiltonian cycles or cliques, etc).
We investigated the convex-algebraic-geometric nature of such questions. Starting with a non-linear encoding of the problem using polynomial ideals we present a hierarchy of relaxations each yielding relevant computational and combinatorial information. In particular derive some results on the problem of estimating the number of distinct isomorphic subgraph inside G and connections to the multiplicity of eigenvalues of the adjacency matrices of G and H.
This is joint work with C. Hillar (MSRI-Berkeley), P. Malkin (UC Davis), and M. Omar (UC Davis).
Jeffrey Doker
Volumes of matroid polytopes
We express the matroid polytope P_M of a matroid M as a signed Minkowski sum of simplices, and obtain a formula for the volume of P_M. This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian Gr_{k,n}. We then derive analogous results for the independent set polytope and the associated flag matroid polytope of M. Our proofs are based on a natural extension of Postnikov's theory of generalized permutohedra.
Lenny Fukshansky
Points of small height missing a union of varieties
Let K be a number field, Q-bar, or the field of rational functions on a smooth projective curve of genus 0 or 1 over a perfect field, and let V be a subspace of K^N, N>1. Let Z_K be a union of varieties defined over K such that V is not contained in Z_K. We prove the existence of a point of small height in V outside of Z_K, providing an explicit upper bound on the height of such a point in terms of the height of V and the degree of a hypersurface containing Z_K, where dependence on both is optimal. Our method is based on some counting lattice points in slices of a cube, a version of combinatorial nullstellensatz, and a version of Siegel's lemma with inhomogeneous heights. As a corollary of the method, we derive an explicit lower bound for the number of algebraic integers of bounded height in a fixed number field.
Joseph Gubeladze
Hom, tenzor, Ker, and Coker constructions for polytopes
The set of affine maps between any two convex polytopes is a convex polytope in a natural way; i. e., the category of convex polytopes and affine maps is a closed category. Employing ideas from category theory -- such as adjoint functors, representable functors, Yoneda lemma, we will propose universal polytopal constructions as in the title. Actual computation of these objects, as opposed to the existence claims, is a hard problem. In the second half of the talk I will present results obtained jointly with T. Bogart on the 6-dimensional polytope of affine maps between regular n- and m-gons. Already there one faces a number of combinatorial, arithmetic and algorithmic challenges.
Martin Henk
Average Behavior of the Frobenius Numbers
Given a primitive positive integer vector a, the largest integer that can not be represented as a non-negative integer combination of the coefficients of a
is called the Frobenius number of a. We show that the asymptotic growth of the Frobenius number on average is
significantly slower than the growth of the maximum Frobenius number. More precisely, we prove that it does not essentially exceed ||a||^{1+1/(n-1)},
where ||a|| denotes the maximum norm.
Milena Hering
The caterpillar polytope and its relatives
To a trivalent tree on n leaves with a positive weight attached to each leaf is associated a lattice polytope. The corresponding toric embeddings arise as toric degenerations of the moduli space of n weighted ordered points on the projective line. I will discuss the Ehrhart polynomials of these polytopes and show that the toric ideals admit a quadratic Groebner basis. This is joint work with Ben Howard.
Serkan Hosten
Growth series of cyclotomic and root lattices
Given a set of monoid generators of a lattice, one can define the word length function on the elements of the lattice, and the corresponding generating function also known as the growth series of the lattice. This series is the Hilbert series of a toric algebra. In interesting instances, such as in the case of root lattices $A_n$, $C_n$ and $D_n$ (where the generators are all roots), or for cyclotomic lattices (where the generators are all roots of unity), this algebra is the coordinate ring of a projective toric variety defined by the convex hull of the generators. Methods from toric Groebner bases and Ehrhart theory gives us a unifying approach to compute the growth series of these lattices.
Diane Maclagan
Combinatorial bounds on nef cones
The nef cone is a convex, but not necessarily polyhedral, cone
associated to a variety X. When X is a (complete) toric variety
determined by a polytope P, the nef cone is a well-understood polyhedral
cone. I will describe joint work with Angela Gibney (Georgia) bounding
the nef cone of X using information from a suitably chosen embedding of
X into a (non-complete) toric variety.
Benjamin Nill
Bounds on lattice polygons and the classification of toric log Del Pezzo surfaces
We study lattice polygons containing the origin in their interiors. Astonishingly, even for these simple objects elementary questions are still open. In this talk, we give an upper bound on the area
that depends cubically on the maximal lattice distance of the origin from the facets. The most interesting case occurs when all the vertices are primitive lattice points. In this situation there is a
one-to-one correspondence to toric log Del Pezzo surfaces,
which was used to give a complete classification of these varieties
up to Gorenstein index < 17.
This is joint work with Alexander M. Kasprzyk and Maximilian Kreuzer.
Hidefumi Ohsugi
Toric ideals of nested configurations
This is a joint work with Satoshi Aoki, Takayuki Hibi and
Akimichi Takemura.
Segre product and Veronese subring are important operations to study
semigroup rings.
We introduce the notion of nested configurations which is a
generalization of these operations.
In particular, Groebner bases of toric ideals of nested
configurations are studied.
As an application, we discuss quadratic Groebner bases of toric
ideals arising from certain convex polytopes.
Andreas Paffenholz
Lattice Polytopes in polymake
The polymake software system by Gawrilow and Joswig deals with convex
polytopes and related objects from geometric combinatorics. The
forthcoming polymake release 3 will contain an application that deals
with specific properties of lattice polytopes. The main focus of the
provided methods is on toric geometry. polymake provides a unified
interface to several existing software packages for lattice polytopes
(e.g. 4ti2, latte, normaliz), as well as various new methods that link
between the programs and compute additional properties. In my talk I
will give a short introduction to the polymake system and then report
on the lattice polytope application. This is joint work with Michael
Joswig and Benjamin Mueller.
Sam Payne
Frobenius splittings for lattice polytopes
I will discuss some of the combinatorial aspects of diagonal splittings of toric varieties, with a focus on their interpretation and consequences for lattice polytopes. In particular, I will present a combinatorial solution to Oda's Problem for diagonally split lattice polytopes, based on joint work with Christian Haase.
Sinai Robins
Tiling Lattices with Translates of Sublattices
We study the problem of tiling (that is, exactly covering) an n-dimensional lattice by finitely many translates of sublattices. This problem extends the 1-dimensional case studied by Morris Newman and others. If we assume that each tiling sublattice is a Cartesian product of arithmetic progressions, we can prove that at least two of the sublattices must be translates of one another. In the absence of the assumption of special structure, it can happen (for n > 2) that no two of the sublattices are translates of one another. We use theta functions to give an (almost) equivalent description in terms of multidimensional Gauss Sums. The case n = 2 remains open. Joint work with David Feldman and Jim Propp.
Francisco Santos
52 years of the Hirsch conjecture
The Hirsch conjecture, stated in 1957 a letter by Warren M. Hirsch (1920Ð2007) to George Dantzig (1914Ð2005) says that the graph of a d-polytope with n facets cannot have diameter bigger than n-d.
Despite being one of the most basic, fundamental, and old open problems in polytope theory, our knowledge about it is shamefully scarce. Most strikingly, no polynomial upper bound is known for the diameter. In contrast, very few polytopes where the bound $n-d$ is achieved are known. More precisely: only one such example is known, leaving aside "trivial cases" and polytopes that can be derived from it by more or less standard constructions.
In this talk I will briefly revise the history of the conjecture, focusing on the side of constructions and "partial counterexamples".
Raman Sanyal
b-transshipments, modular flow reciprocity, and a combinatorial interpretaion of the Tutte polynomial
In analogy to the beautiful reciprocity for the chromatic polynomial of a graph we give a combinatorial
interpretation for the values of the modular flow polynomial evaluated at a negative integer. The proof involves
Ehrhart polynomials of a family of b-transshipment polytopes that encode the combinatorial objects in question.
With the modular flow reciprocity we can give a combinatorial meaning to (almost) all evaluations of the Tutte
polynomial of a graph. This is joint work with Felix Breuer.
Hal Schenck
Toric specializations of the Rees algebra of Koszul cycles
We describe obstructions to a conjecture that the length
of the 2-linear strand of a homogeneous, prime, nondegenerate
ideal I with degree two piece generated by quadrics of rank
at most four is governed by a determinantal subideal of I,
and prove a variant of the conjecture. The obstructions arise
from toric specializations of the Rees algebra of Koszul cycles,
and we give an explicit construction of toric varieties with
minimal linear syzygies of arbitrarily high rank.
(joint work with M. Stillman)
Alan Stapledon
Weighted Ehrhart Theory
In Ehrhart theory, one studies the number of lattice points in any dilation of a lattice polytope P. In this talk, we present a refinement of this theory in which every lattice point v is counted with a particular weight w(v), determined by the smallest rational number m such that v lies in mP. We will show how this leads to simple proofs and generalizations of some classical results of Ehrhart and Hibi. Secondly, we will explain the
geometric motivation for this approach. More specifically, we will discuss the correspondence with orbifold Betti numbers of toric stacks.
Rekha Thomas
Theta Bodies for Polynomial Ideals
We extend Lovasz's construction of the theta body of a graph to create a hierarchy of semidefinite relaxations for the convex hull of any real variety. These relaxations tie into the literature via work by Lasserre. When the variety is finite, i.e., the convex hull is a polytope, we give a complete characterization of when the first theta body equals the polytope, answering partially a question by Lovasz. For all varieties, the first theta body has a precise geometric description that I will describe. Joint work with Joao Gouveia and Pablo Parrilo.
Jan Vershelde
Searching for Solution Curves of Polynomial Systems
A polynomial system with as many equations as unknowns
is expected to have only isolated solutions.
In the exceptional case of a solution curve we propose
to develop the solution curve starting at infinity.
A tropism defines the leading powers of this Puiseux series development of a solution curve.
Computing these tropisms along with the coefficients
of the Puiseux series leads to a polyhedral method
for solution curves of polynomial systems.
Volkmar Welker
On the Lefschetz-Property for Vernonese Rings
We study the Lefschetz property of Cohen-Macaulay standard graded algebras for Veronese rings. In particular, we study the question
if for high enough r the r'th Veronese algebra of a given
algebra is Lefschetz. We collect evidence that this is so by studying the enumerative consequences of the Lefschetz property on the h-vector of the algebra.
Kevin Woods
A Finite Calculus Approach to Ehrhart Polynomials
Given a polytope P, the lattice point enumerator counts, as a function
of t, the number of integer points in the dilated polytope tP. If P
has rational vertices, this function is a quasi-polynomial in t,
called the Ehrhart quasi-polynomial. Inspired by the analogy of
Ehrhart quasi-polynomials as a discrete version of the volume of a
polytope, we present a new proof of the existence of these
quasi-polynomials. This proof uses finite calculus and induction, and
provides quick proofs of two other related results: McMullenÕs theorem
about the periods of the individual coefficients of the
quasi-polynomial, and the Ehrhart-Macdonald theorem on reciprocity.
This is joint work with Steven Sam.
Ruriko Yoshida
The balanced minimum evolution polytopes
The balanced minimum evolution (BME) is a well-known distance based method to reconstruct a phylogenetic tree from a dissimilarity map. In 2008, Eickmeyer et al. defined the notion of the BME polytopes and showed that the vertices of the BME polytope are the BME vectors of binary trees. The BME vector of the star phylogeny lies in the interior of the BME polytope, and all other BME vectors lie on the boundary of the BME polytope. In addition, Eickmeyer et al. showed that finding the BME tree is solving a linear programming problem over the BME polytope. In this talk we will discuss on the structures of the BME polytopes and also we will discuss some open problems.