Total dual integrality and perfect graphs

Abstract: Many problems in combinatorial optimization can be expressed as detecting total dual integrality (TDI) in a 'non-generic' system of linear inequalities. One such case is the weak perfect graph theorem (WPGT) of Lovasz. We will present various ways for detecting TDI in a non-generic system by studying secondary fans and Groebner bases of toric ideals. When coupled with computational algebra packages, this understanding provides an experimentally feasible tool for investigating TDI in a whole host of scenarios. It also provides a new, Groebner basis proof of WPGT for chordal graphs. More generally, we will present an explicit polyhedral strengthening of WPGT. This is joint work with Andras Sebo.

Research topics

Flag arrangements and tilings of simplices

I will start by discussing the line arrangement that results from intersecting d generically chosen complete flags in Cn. I will give a combinatorial description of the matroid Tn,d that keeps track of the linear dependence relations among these lines. I will show how the bases of the matroid Tn,3 describe the equilateral triangles with holes which can be tiled with unit rhombi. More generally, I will provide evidence for a conjectural connection between the matroid Tn,d and certain tilings of simplices. If time allows, I will end by outlining the connection between these results and the Schubert calculus of the flag manifold, drawing on work of Eriksson-Linusson and Billey-Vakil. In particular, we obtain a very simple and effective criterion for guaranteeing the vanishing of many structure constants. I will keep the talk as self-contained as possible. (This is joint work with Sara Billey at the University of Washington.)

Interpolating Polynomial Equations

Abstract: Given d distinct points on a line, elementary linear algebra shows that one can find a polynomial function of degree d-1 taking specified values at each of the points--this is called interpolation. Interpolation on d points cannot be done with polynomials of degree d-2. On the other hand, polynomials of degree d-1 suffice even if the points are not on a line, but in a plane or higher dimensional space. However, for "most" sets of d points in a higher-dimensional space, polynomials of much smaller degree suffice for interpolation. There is a remarkable formula giving the exact degree required for interpolation on any set of points, and it is related to deep questions about commutative algebra and algebraic geometry. I'll explain the ideas necessary to understand this formula, and talk about some questions to which it leads.

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

Abstract: Triangulations of a convex polygon are known to be counted by the Catalan numbers. A natural generalization of a triangulation is a k-triangulation, which is defined to be a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. It was recently shown by Jonsson that k-triangulations are enumerated by certain determinants of Catalan numbers, that are also known to count k-tuples of non-crossing Dyck paths. However, no bijective proof is known for general k. In this talk I will present a bijection for the case k=2. The bijection is obtained by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.

2 p.m. Ellen Veomett University of Michigan		3 p.m. Seth Sullivant Harvard University
A Positive Semidefinite Approximation of the Traveling Salesman Polytope Abstract: For many interesting convex bodies X, the membership question (is the point p in X?) is difficult to answer. In an attempt to rectify this situation, we look for another convex body which is "close" to X for which the membership question is easy. We will present a construction which produces a hierarchy of sets P1, P2, ..., each contained in X. Each Pk is obtained as an intersection of a cone of positive semidefinite quadratic forms with an affine space. If X is a 0-1 polytope of dimension n, we can show that Pn = X, similar to construction results of Lasserre, Lovasz and Schrijver, and Sherali and Adams. In the particular case where X is the traveling salesman polytope on n cities, Tn, we can give metric bounds. The traveling salesman polytope can be easily described as the convex hull of the orbit of a particular vector under an action of the symmetric group. We will show that if k is no more than n/2, then the scaling of Pk by n/k+O(1/n) contains Tn. Membership in Pk is computable in time polynomial in n, the degree of the polynomial linear in k. If time permits, we will discuss facets of the traveling salesman polytope which lie on the boundary of Pk.		Combinatorial secant varieties Abstract: Given two projective varieties X and Y, their join X*Y is obtained by taking the Zariski closure of the union of all lines spanned by a point in X and a point in Y. The join of a variety X with itself is called the secant variety of X. In this talk, I will describe the construction of joins and secants in the combinatorial context of monomial ideals. For ideals generated by squarefree quadratic monomials, the generators of the secant ideals are obstructions to graph colorings and this leads to a commutative algebra version of the Strong Perfect Graph Theorem. Questions about secant varieties of combinatorially defined varieties (e.g., Grassmannians, determinantal varieties, toric varieties) can often be reduced to the monomial case. I will try to emphasize the combinatorial aspects of all of this, including the connections to graph theory, regular triangulations, and partially ordered sets. This is joint work with Bernd Sturmfels.

Metric geometry of hypercubes

Abstract: We will begin by recalling some general principles of classical geometry. In particular, we'll talk about so-called Helmholtz's "free mobility" principle. Then we'll use the ideas surrounding the "free mobility" principle to formulate homogeneity properties of abstract metric spaces. A particular result from discrete metric geometry of infinite dimensional hypercubes will be discussed.

Scheduling CCRR tournaments

Abstract: In this talk, I will describe how to construct CCRRs, complete coupling round robin schedules. The motivation for these schedules is a problem in scheduling bridge tournaments with the table-of-four format. The techniques come from combinatorial design theory. I will start out with a brief introduction to design theory, and I will emphasize direct constructions for the tournaments. So the talk should be accessible to students with an interest in scheduling problems and combinatorics.

2 p.m. Matthias Koeppe University of Magdeburg & UC Davis		3 p.m. Evgeny Materov University of Massachusetts
Fully polynomial time approximation schemes for mixed-integer polynomial optimization in fixed dimension Abstract: Integer linear optimization, that is the problem of optimizing a linear functional over the integer points of a polyhedron, is NP-hard. However, when we fix the number of variables, it can be solved in polynomial time using the algorithm of Lenstra (1983). More strongly, Khachiyan and Porkolab (2000) showed that convex polynomial functions can be minimized over the integer points of convex semialgebraic sets in polynomial time, when the number of variables is fixed. The situation is different when we consider arbitrary (not necessarily convex) objective functions over the integer points of a polytope. Even when the dimension is fixed >= 2 and the degree is bounded <= 4, the optimization problem is still NP-hard. We prove the existence of a fully polynomial-time approximation scheme (FPTAS) for the maximization problem where the objective function is non-negative on the feasible region, when the dimension is fixed. This is the strongest possible result, unless P=NP. We then extend the FPTAS to the case of mixed-integer polynomial optimization, where some of the variables are integers and some are reals. math.OC/0410111, math.OC/0505677 (joint work with J. A. De Loera, R. Hemmecke, and R. Weismantel)		Toric Duality for Quotient Rings Abstract: Let S be the homogeneous coordinate ring of a complete toric variety X. We study the duality between the graded parts of the quotient ring R = S/I, where I is the ideal generated by dim(X) + 1 polynomials in S that don't vanish simultaneously on X. This duality is related to the theory of multivariable residues and also appears in the study of Frobenius algebras. The case when X is a projective space and S is a usual homogeneous ring was considered by F. S. Macaulay. Unlike the classical situation for X = Pn, the pairing between the graded parts of R might be non-perfect which can be shown using the machinery of spectral sequences. In particular, I will illustrate the failure of the duality by some concrete examples when X is a product of projective spaces. Also, I would like to explain how this duality can be written down explicitly in terms of the Bezoutian of the polynomials generating the ideal I. This a joint project with David A. Cox.

Tropical oriented matroids

Abstract: In earlier work with Bernd Sturmfels, we showed that a class of objects called tropical polytopes are in bijection with regular subdivisions of products of simplices. It turns out that tropical polytopes are the same as tropical hyperplane arrangements, making it natural to generalize them to tropical oriented matroids. The current joint project, with Federico Ardila, is to properly axiomatize tropical OMs, ideally so that they at least contain all subdivisions of products of simplices. I will describe our progress and draw some pretty pictures. No previous knowledge of what the word "tropical" means in this context is required.

Growth types of Coxeter groups and their quotients

Abstract: Coxeter groups are a very special class of groups defined via generators and relations. They are intimately related to the classical finite dimensional semisimple Lie algebras and to their infinite dimensional counterparts - the affine and indefinite Kac-Moody algebras. To every Coxeter group W is associated an object with rich combinatorial structure -- its root system. Many aspects of these groups can be studied by analyzing the action of the group on its root system. We will use this approach to study the "growth type" of the group. Roughly, if we let gamma(n) denote the number of elements of the group of length <=n, the growth type measures the rate of growth of gamma(n) with n. It is well known that Coxeter groups of finite and affine type have polynomial growth while all other Coxeter groups have exponential growth. I will describe a generalization of this latter result to quotients W/WJ of such Coxeter groups by their parabolic subgroups. Along the way, we will introduce reflection subgroups of W and a criterion of M. Dyer in terms of inner products of roots that enables construction of such subgroups. We'll use this and some root system combinatorics to construct certain reflection subgroups of W that are isomorphic to "universal Coxeter groups". This will lead us to the result that the quotients W/WJ have exponential growth too. This will (hopefully) be a self-contained, accessible talk.

A Geometric Littlewood-Richardson Rule

Abstract: I will describe an explicit geometric Littlewood-Richardson rule, interpreted as deforming the intersection of two Schubert varieties so that they break into Schubert varieties. There are no restrictions on the base field, and all multiplicities arising are 1; this is important for applications. This rule should be seen as a generalization of Pieri's rule to arbitrary Schubert classes, by way of explicit homotopies. It has a straightforward bijection to other Littlewood-Richardson rules, such as tableaux and Knutson and Tao's puzzles. This gives the first geometric proof and interpretation of the Littlewood-Richardson rule. It has a host of geometric consequences, which I may describe, time permitting. The rule also has an interpretation in K-theory, suggested by Buch, which gives an extension of puzzles to K-theory, and in fact a Littlewood-Richardson rule in equivariant K-theory (ongoing work with Knutson). The rule suggests a natural approach to the open question of finding a Littlewood-Richardson rule for the flag variety, leading to a conjecture, shown to be true up to dimension 5. Finally, the rule suggests approaches to similar open problems, such as Littlewood-Richardson rules for the symplectic Grassmannian and two-step flag varieties.

On the Frobenius problem

Abstract: Let N > 1 be an integer, and let 1 < a1 < ... < aN be relatively prime integers. The Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be expressed as a linear combination of a1, ..., aN with non-negative integer coefficients. The condition that a1, ..., aN are relatively prime implies that such number exists. The general problem of determining the Frobenius number given N and a1, ..., aN is known to be NP-hard, but there has been a number of different bounds on the Frobenius number produced by various authors. We use techniques from the geometry of numbers to produce a new bound, relating the Frobenius number to the covering radius of the null-lattice of the linear form with coefficients a1, ..., aN. Our bound is frequently better than the previously known ones, in particular when this lattice has equal successive minima (ESM); we show that this happens infinitely often. This is joint work with Sinai Robins.

Viveka Erlandsson, Mary Halloran, and Dorothy Moorefield