Computing parametric counting functions using exact half-open decompositions of polyhedra

We consider the problem of efficiently computing the parametric counting function of the integer points in a family of polytopes described by a fixed matrix and a varying right-hand side vector. This class of parametric counting functions includes the well-known vector partition functions. It is well-known that the counting function is a piecewise quasipolynomial function, which can be computed by running Barvinok's algorithm on the pieces of a chamber decomposition. Computations with Barvinok's short rational generating functions are traditionally being performed in the dual space, to avoid the combinatorial complexity of inclusion-exclusion formulas for the intersecting proper faces of cones. We prove that, on the level of indicator functions of polyhedra, there is no need for using inclusion-exclusion formulas to account for boundary effects: All linear identities in the space of indicator functions can be purely expressed using half-open variants of the full-dimensional polyhedra in the identity. This gives rise to a practically efficient, parametric Barvinok algorithm in the primal space. This is an improvement on our earlier technique of computing explicit irrational perturbations. We also apply the half-open decomposition technique to the problem of the computation of Ehrhart polynomials of polytopes associated with matroids and polymatroids. The talk is based on the papers arXiv:math.CO/0603308, arXiv:0705.3651 [math.CO] (joint work with S. Verdoolaege) and unpublished joint work with J. A. De Loera and David Haws.

September 21, 2007

3:10 p.m.

Jameson Cahill

San Francisco State University

Rank tables, permutation arrays, and flag arrangements

We will define a new combinatorial object which we call a rank table. The most important fact about rank tables can be summarized as follows: "A rank table is to a flag arrangement what a matroid is to a hyperplane arrangement." We will use this fact to disprove a conjecture which says that all permutation arrays can be realized as a flag arrangement in some vector space.

September 28, 2007

3:10 p.m.

Emanuele Delucchi

University of Pisa

The K(pi,1) problem for arrangements of hyperplanes

The study of arrangements of hyperplanes is at the crossroad of (at least) topology, geometry, algebra and combinatorics. This talk will be a gentle walk through this very rich landscape. Our guide will be guided by the following question: when is the complement of a set of hyperplanes in complex space aspherical? We will start with a look of the historically first appearance of this question (a conjecture by Brieskorn, in 1972) and take this as a motivation to illustrate, with easy but instructive examples, some of the different ideas that originated from it during the last 35 years in the attempt to clarify whether asphericity of the complement is a combinatorially determined property of the arrangement. This question is still open and in the focus of a very active research.

October 5, 2007

3:10 p.m.

Tim Hsu

San Jose State University & MSRI

Progress on the Griggs Nesting Conjecture

Normalized matching posets form a large class of posets that includes such naturally occurring examples as Boolean lattices (the subsets of a finite set, partially ordered by inclusion) and linear lattices (the subspaces of a finite vector space, ordered by inclusion). It was shown independently by Anderson and Griggs that any rank-symmetric-unimodal normalized matching poset P has a symmetric chain decomposition; in other words, P can be partitioned into chains that are symmetric around the middle of P. Griggs later conjectured that, analogously: Griggs Nesting Conjecture. Every rank-unimodal (but not necessarily symmetric) normalized matching poset can be partitioned into nested chains. We will discuss recent progress that Mark Logan, Shahriar Shahriari, and the speaker have made on the Griggs Nesting Conjecture. If time permits, we will also discuss recent and ongoing related work done by students, including the master's thesis work of Katherine Shelley (SJSU MA 2007). This talk is aimed at advanced undergraduates and beginning graduate students. No background is necessary other than basic familiarity with graphs, as we will spend most of our time defining the key terms used above (including poset, chain, rank-symmetric, rank-unimodal, normalized matching, and nested) and looking at examples. For students and faculty interested in finding out more, we will also discuss some open problems and possible research topics.

October 12, 2007

3:10 p.m. Glenn Appleby Santa Clara University		4:10 p.m. Benjamin Nill Freie Universität Berlin
Matrix Pairs and Littlewood-Richardson Fillings Several objects of mathematical interest are indexed by partitions, such as Schur polynomials, Jordan forms of nilpotent matrices, and invariant factors of matrices over discrete valuation rings (like power series rings). When, for example, two such matrices are multiplied, we try to predict the invariant factors of the product in terms of the invariants of the two original matrices. In other words, if (a,b,c) is a triple of partitions, how can we tell if there is a triple (A,B,C) of matrices over a power series ring such that the invariants for A are a, B for b, and C for c, where AB = C? For many of the problems mentioned above, the *same* set of triples appears and these connections need to be better understood. In this talk we will present recent results (in joint work with Tamsen McGinley) where we find explicit methods to relate this matrix problem to the combinatorics of Littlewood-Richardson fillings of skew tableaux.		The degree of lattice polytopes The number of lattice points in integer multiples of a lattice polytope has a rational generating function. Its numerator is called the h*-polynomial, and its degree is the degree of the lattice polytope. It is well-known that the degree equals at most the dimension of the polytope, and it is smaller the more "empty" the lattice polytope is. Our main question of interest is the following: What can we say about lattice polytopes of given degree? In this talk we present recent results and ongoing work on a conjecture of Batyrev, with an elementary proof in the case of a lattice simplex.

October 26, 2007

3:10 p.m. Amanda Ruiz San Francisco State University		3:35 p.m. Anna Brown San Francisco State University
Presentations of cotransversal matroids Whitney's 2-isomorphism theorem states that there is a series of moves you can apply to a graphical presentation of a graphical matroid that will preserve the matroid, and that given a presentation of a graphical matroid, we can obtain any other presentation via a series of these moves. This motivates a question: is there an analogous set of moves you can perform on a directed graph presentation of a cotransversal matroid? In this talk we will find that there is a set of moves on these cotransversal matroids that will result in different presentations of the same matroid, and that given a presentation of a cotransversal matroid, we can obtain any other presentation via a series of these moves. This is joint work with Kimberly Seashore.		Convexity in tropical oriented matroids The study of convex geometries is a relatively new area of mathematics, and the study of tropical oriented matroids is newer still. We will begin by discussing Ardila and Develin's definition of a tropical oriented matroid and will then show that each tropical oriented matroid defines a convex geometry.

November 2, 2007

3:10 p.m.

Alex Eskin

University of Chicago & MSRI

Coarse differentiation and the geometry of solvable groups

A quasi-isometry is a map between two metric spaces which respects distances up to an additive and a multiplicative constant. It is the natural notion of equivalence if one considers finitely generated groups as geometric objects. Even though quasi-isometries have no local structure, I will discuss a sort of differentiation substitute for such maps, and describe some recent progress in the area.

November 9, 2007

2:10 p.m. Sven Herrmann Technical University Darmstadt		3:10 p.m. Raman Sanyal Technical University Berlin
Splits: Simple Subdivisions of Convex Polytopes The aim of this talk is to develop the theory of splits of convex polytopes. Splits are the simplest possible (non-trivial) subdivisions of a polytope P. Since they are all regular we get in this way a bunch of facets for the secondary polytope of P. If P is the second hypersimplex our theory reduces to the split decomposition theory for finite metric spaces developed by Dress et al. Lots of their results can be generalized to arbitrary polytopes. The presented theory is very similar to work of Hirai who developed a split decomposition of polyhedral convex functions. We will illustrate this similarities here and also give an explicit algorithm to compute splits.		Polytope projections and topological obstructions Is it possible to Minkowski sum two triangles in the plane to a 9-gon? Like many problems regarding combinatorial/geometric properties of polytopes, this one can be phrased in terms of projections. We show how Gale duality helps translating questions concerning polytope projections into topological embeddability questions. As a sneak preview: The answer to the above question is "No" since the complete bipartite graph K_{3,3} is not planar.

November 30, 2007

3:10 p.m.

Rick Scott

Santa Clara University

Reciprocity of growth series for right-angled Coxeter groups

Abstract: The growth series for a Coxeter group W with respect to the standard generating set is known to be a rational function. When the nerve of the Coxeter group is a triangulation of a sphere, then a theorem of Charney and Davis says that this rational function is reciprocal. That is, replacing the indeterminate t with 1/t yields the same rational function up to sign. In this talk we consider the growth series with respect to the larger generating set consisting of all longest elements in finite parabolic subgroups. This generating set is a more natural choice with respect to the automatic structure for W. We show that for right-angled Coxeter groups this ``automatic growth series'' is also reciprocal when the nerve is a sphere.

December 7, 2007

2:10 p.m. Eric Mortenson Penn State		3:10 p.m. Eric Babson UC Davis
Finite field analogs of hypergeometric series, coefficients of modular forms, and p-adic congruences We discuss applications of finite field analogs of hypergeometric series to Beukers' congruences, Beukers-like congruences of Rodriguez-Villegas, and congruences of Van Hamme.		A Sperner Lemma for several colorings Fredric Muenier noted that if a subdivision of a tetrahedron has three simplicial maps to that tetrahedron taking the subdivision of each face to that face then there is some simplex which none of the three maps collapses to a vertex. This is one case of a larger conjecture he made. I will discuss a topological viewpoint which allows one to prove this conjecture.