The Square-Peg Problem

Given a Jordan curve in the plane, are there four points lying on the curve that form a square? The talk will recount how I got into this problem, some solutions with conditions, and how my co-authors (Jason Cantarella and Elizabeth Denne) are approaching the full case, which is still unknown.

Topology and the Minimum Weight Triangulation Problem

Topological and algorithmic techniques are useful in the study of problems in combinatorics, discrete geometry, and computational complexity. We combine aspects of these fields in a study of the minimum weight triangulation problem for planar point sets. In particular, we investigate how minimum weight triangulations are affected by the addition of points. Let mwt(X) denote the weight (i.e., the sum of the edge lengths) of a minimum weight triangulation of a finite point set X in R2. The conditions are studied under which an n-point set X will allow an (n+1)st point p (called a Steiner point) to give mwt(X union {p}) < mwt(X). Such a p is called a Steiner reducing point, and the collection of all such Steiner reducing points is called the Steiner reducing set of X, denoted St(X). We prove that these Steiner reducing sets can have complicated topology: they may have many connected components or may fail to be simply connected.

On the coefficients of Hilbert quasi-polynomials

Abstract

The Newton Polytope of the Implicit Equation

We apply tropical geometry to study the image of a map defined by Laurent polynomials with generic coefficients. The tropicalization of an algebraic variety is a polyhedral fan, and we give a combinatorial description of this fan for a parametrized variety without computing the defining ideal. If this image is a hypersurface then our approach gives a construction of the Newton polytope of the defining polynomial.

Products of foldable triangulations

Regular triangulations of products of lattice polytopes are constructed with the additional property that the dual graphs of the triangulations are bipartite. The (weighted) size difference of this bipartition is a lower bound for the number of real roots of certain sparse polynomial systems by recent results of Soprunova and Sottile [Adv. Math. 204(1):116-151, 2006]. Special attention is paid to the cube case. This is joint work with Nikolaus Witte (TU Berlin).

2:10 p.m. Mark de Longueville Freie Universität Berlin		3:10 p.m. Anton Dochtermann University of Washington
Splitting necklaces - a problem for thieves, topologists, and combinatorialists In this talk I will discuss a famous theorem by Noga Alon about fairly splitting a necklace among several thieves. The question about actually finding such a splitting leads to interesting combinatorial analogs of generalizations of the Borsuk-Ulam theorem. Moreover, we will see that higher dimensional necklaces lead to very beautiful spaces that certainly will be appreciated by the community of thieves. Joint work with R. Zivaljevic.		Paths, homotopy, and Hom complexes in the category of graphs For a graph G, we consider the 'graph of paths' in G determined by the internal hom structure associated to the categorical product. This leads us to a notion of graph homotopy which we show is characterized by topological properties of the so-called Hom complex, a functorial way to assign a space to a pair of graphs (originally introduced/used by Lovasz, Babson and Kozlov, etc. to get lower bounds on chromatic number). We discuss some features of graph homotopy and along the way present results that describe the interaction of the Hom complex with certain graph operations/structures. A consideration of the graph of closed paths in G leads to a graph theoretic interpretation of the higher topology of the Hom compelexes, as well as (in the equivariant setting) a class of 'test' graphs that give new insight into the original Lovasz bound. Parts of this are joint work with Eric Babson and Carsten Schultz.

2:10 p.m. Frank Lutz Technische Universität Berlin		3:10 p.m. Nikolaus Witte Technische Universität Berlin
Periodic Foams, Polyhedral Surfaces, and Graph Coloring Manifolds I will present examples of - simplicial manifolds with small edge valence, - geometric realizations of triangulated surfaces, - and Hom complexes that are manifolds.		Construction of combinatorial 4-manifolds as branched covers Any closed oriented PL d-manifold is a branched cover of the d-sphere, but no restrictions on the number of sheets nor the topology of the branching set are known for d>4 in general. As for dimension 4, Piergallini proved that every closed oriented PL 4-manifold is a 4-fold branched cover of the 4-sphere branched over an immersed PL surface. This generalizes a long standing result by Hilden and Montesinos to dimension four. Izmestiev and Joswig gave a combinatorial equivalent of the Hilden and Montesinos result, constructing (fairly explicit) closed oriented combinatorial 3-manifolds as unfoldings of combinatorial 3-spheres. The construction of Izmestiev and Joswig is generalized and applied to the result of Piergallini, obtaining closed oriented combinatorial 4-manifolds as unfoldings of combinatorial 4-spheres.

Ehrhart series and lattice triangulations

I will discuss combinatorial formulas for counting lattice points in polytopes using lattice triangulations. These formulas are inspired by calculations from stringy algebraic geometry, and lead to examples of reflexive polytopes whose Ehrhart series have unexpected properties.

Tropical Discriminants

We use tropical geometry to take a fresh look at the theory of A-discriminants of Gelfand, Kapranov and Zelevinsky. We show that the tropical A-discriminant is the Minkowski sum of the row space of A and the Bergman fan of the kernel of A. The latter is a well-studied object in geometric combinatorics. As our main application, we present a positive formula for the extreme monomials of the A-discriminant, regardless of any smoothness assumption. This is joint work with Alicia Dickenstein and Bernd Sturmfels.

Proofs are Graph Homomorphisms

"Mathematicians care no more for logic than logicians for mathematics." (de Morgan, 1868) The dry syntactic manipulations of formal logic can be repellant to mathematicians. This talk presents a syntax-free formulation of propositional logic in which proofs are combinatorial rather than syntactic, recasting propositional logic as a branch of graph theory. It defines a combinatorial proof of a proposition P as a graph homomorphism h : C -> G(P) where G(P) is a graph associated with P, and C is a colored graph. The talk summarises a paper which just appeared in Annals of Mathematics. The talk should be accessible to a broad mathematical audience. In particular, it will not presume any background in propositional logic.