The UC Berkeley combinatorics seminar

Spring 2011, Monday 5-6pm, Evans Hall 939
Organizers: Alex Engström, Kelli Talaska, Lauren Williams.

The seminar will be followed by drinks and/or dinner. Speakers and participants are warmly invited to join us.

If you would like to be added to the seminar mailing list, contact Lauren Williams.

Date Speaker Title
January 17, Günter M. Ziegler, TU Berlin Colored versions of Tverberg's theorem

More than 50 years ago, the Cambridge undergraduate Bryan Birch showed that “3N points in a plane” can be split into N triples that span triangles with a non-empty intersection. He also conjectured a sharp, higher-dimensional version of this, which was proved by Helge Tverberg in 1964 (freezing, in a hotel room in Manchester).

In a 1988 Computational Geometry paper, Bárány, Füredi & Lovász noted that they needed a “colored version of Tverberg's theorem”. Bárány & Larman proved such a theorem for 3N colored points in a plane, and conjectured a version for d dimensions. A remarkable 1992 paper by Živaljević & Vrećica obtained this, though not with a tight bound on the number of points. The proof was based on equivariant topology and the beautiful combinatorics of “chessboard complexes”.

We propose a new “colored Tverberg theorem”, which is tight, and which generalizes Tverberg's original theorem. The proof uses some interesting tools from Algebraic Topology, based on the (by now) standard set-up of a “configuration space/test map” scheme. Finally, we discuss recent efforts towards a “colored Tverberg theorem for maps to manifolds”.

Joint work with Pavle V. Blagojević and Benjamin Matschke. Arxiv: 0910.4987, 0911.2692.

January 24 Dido Salazar-Torres, SFSU Gelfand-Tsetlin and Feigin-Fourier-Littelmann-Vinberg
polytopes as marked poset polytopes

Stanley showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from posets with integers assigned to some of its elements.

Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes and the Feigin-Fourier-Littelmann-Vinberg polytopes, which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.

This is joint work with Federico Ardila and Thomas Bliem.

January 31 Charles Chen, UC Berkeley Plane partitions and monomial complete intersections

We consider the homogeneous components Ur of the map on R=k[x,y,z]/(xA, yB, zC) that multiplies by x+y+z. We give a bijective proof of the identity proven by Li and Zanello equating the determinant of the middle component Ur when (A, B, C)=(a+b, a+c, b+c) to the number of plane partitions in an a by b by c box. We also prove that, for certain vector subspaces of R, similar identities hold relating determinants to symmetry classes of plane partitions, in particular classes 3, 6, and 8.

This is joint work with Alan Guo, Xin Jin, and Gaku Liu.

February 7 Max Glick, U Michigan The pentagram map

The pentagram map, introduced by R. Schwartz, is defined by the following construction: given a polygon as input, draw all of its "shortest" diagonals, and output the smaller polygon which they cut out. I will explain how the machinery of cluster algebras can be used to obtain explicit formulas for the iterates of the pentagram map. The formulas are written in terms of certain cross ratios, and involve generating functions associated with a family of posets which arose in the work of N. Elkies, G. Kuperberg, M. Larsen, and J. Propp on alternating sign matrices.

February 14 Federico Ardila, SFSU Universal polynomials for Severi degrees of toric surfaces

The Severi degree is the number of plane curves of degree d and n nodes going through a fixed generic set of (the right number of) points. For large enough d, the Severi degrees equal the Gromov-Witten invariants. In 2009, Fomin and Mikhalkin proved the 1995 conjecture that for fixed n, Severi degrees are eventually polynomial in d.

We study the Severi degrees corresponding to arbitrary "h-transverse" toric surfaces. We prove the analogous result that the Severi degrees are eventually polynomial as a function of the multidegree. Perhaps more surprisingly, we prove that the Severi degrees are also eventually polynomial "as a function of the surface".

Our strategy is to use tropical geometry to express Severi degrees in terms of Mikhalkin's floor diagrams, and then study those combinatorial objects in detail. The analysis is motivated by the work of Fomin and Mikhalkin, and requires new ideas. Our method gives rise to effective computations of Severi degrees. The talk will be self-contained, and will focus on the combinatorial aspects of this work, which is joint with Florian Block.

February 21 President's day
February 28 Steve Klee, UC Davis Cellular Resolutions of Ideals Defined by
Simplicial Homomorphisms

We introduce the class of cointerval simplicial complexes, which are related to the classes of cointerval hypergraphs, introduced by Dochterman and Engstrom, and shifted simplicial complexes, introduced by Erdos-Ko-Rado (combinatorial shifting) and Kalai (algebraic shifting). We will discuss some geometric properties of cointerval complexes, and introduce a (polyhedral) complex of order-preserving homomorphisms, OHOM(A,B), between simplicial complexes A and B. We will show that the complex OHOM(A,B) supports a minimal free resolution of an associated monomial ideal when B is a cointerval simplicial complex. This work is joint with Benjamin Braun and Jonathan Browder.

March 7 Patricia Hersh, NCSU A homological obstruction to greedy sorting on trees

Given any finite group and any minimal set S of generators, Eric Babson and Vic Reiner introduced an associated ``Coxeter-like complex'' whose cells are cosets of ``parabolic subgroups'', i.e. subgroups generated by subsets of S. They conjectured a lower bound on the connectivity in the case where W is the symmetric group and S is a set of transpositions. I will discuss the proof of this conjecture and how this relates to the question of which trees admit pleasant notions of inversions, weak order and greedy sorting on the set of tree labelings. Part of this is joint work with John Shareshian.

March 14 Isabella Novik, U Washington Centrally symmetric triangulations of products of
spheres with few vertices

What is the minimum number of vertices needed to triangulate the product of spheres SixSd-2-i in a centrally symmetric way? We show that for all values of i and d with 0<=i<=d-2, the answer to this question is 2d. Moreover, the triangulations we construct possess a vertex-transitive action by a group of order 4d. This solves in the affirmative certain conjectures by Sparla and Lutz. The crux of our construction is the definition of a certain manifold with boundary whose boundary is the required triangulation of SixSd-2-i.

Joint work with Steve Klee.

March 21 Spring recess
March 28 Alex Fink, NCSU Valuative matroid invariants and the Grassmannian

One of the natural objects associated to every realisable matroid is a torus orbit on the Grassmannian. This underlies many of the appearences of matroid base polytope decompositions. We begin with some remarks independent of the geometry on so-called valuative functions of matroids, those functions which behave well in polytope decompositions. We then introduce the geometry, and turn the K-theory of the torus orbits on the Grassmannian into an entirely combinatorial picture of polyhedra and lattice points. We use this to bring non-realisable matroids into the picture, and to give related interpretations of two matroid invariants, namely the Tutte polynomial and an invariant of Speyer's giving combinatorial bounds on linear spaces in tropical geometry.

This talk is based on joint work with David Speyer.

April 4 Veronica Crispin, Uppsala U/UO The Ratliff-Rush operation on an ideal

The union of all (Ii+1:Ii), for i>0, where I is an ideal in a Noetherian ring, was first studied by Ratliff and Rush in 1978. The union has the interesting property being the largest ideal with the same high powers as I. We give a survey on the concept and show how the Ratliff-Rush operation of some classes of monomial ideals in k[x,y] is computed using numerical semigroups. Also we show a recent result that generalizes the two-dimensional case to classes of monomial ideals in three variables and more.

April 11 Anne Schilling, UC Davis Crystal energies via the charge in types A and C

The energy function of affine crystals is an important grading used in one-dimensional configuration sums of statistical mechanical models and generalized Kostka polynomials. It is defined by the action of the affine Kashiwara crystal operators through a local combinatorial rule generalizing descents and the R-matrix. Nakayashiki and Yamada related the energy function in type A to the charge statistic of Lascoux and Schuetzenberger. Computationally, it is much more efficient to compute charge than energy since its definition involves a recursive definition of local energy and the combinatorial R-matrix, for which not in all cases efficient algorithms exist. In this talk we relate energy to a new charge statistic in type C which comes from the Ram-Yip formula for Macdonald polynomials. This involves in particular the generalization of parts of the Kyoto path model for perfect crystals to the nonperfect setting, which yields an isomorphism between affine highest weight crystals and tensor products of Kirillov-Reshetikhin crystals.

This is joint work with Cristian Lenart.

April 18 Matthew Stamps, UC Davis Topological representations of matroid maps

The Topological Representation Theorem for matroids states that every matroid can be realized as an arrangement of codimension-one homotopy spheres on a sphere. Engstrom recently showed how to explicitly construct such an arrangement for any given matroid. I will show that the structure preserving maps between matroids induce topological mappings between their representations using Engstrom's construction. Specifically, I will show that weak maps induce continuous (Z/2Z)-equivariant maps which weakly decrease Betti numbers. If time permits, I will also discuss how this process yields a functor from the category of matroids with weak maps to the homotopy category of topological spaces.

April 25 Jeff Doker, UC Berkeley Geometry of the Multiplihedron

The associahedron is a polytope whose combinatorics encode the structure of rooted trees on a fixed number of leaves. The multiplihedron is a polytope that extends this notion by applying paint to parts of these trees. In this talk we will explain what painted trees are and how they are used to construct the multiplihedron. We will then discuss some geometric properties of the multiplihedron, including its face lattice, Minkowski decomposition, and volume. We'll also look at an interesting family of polynomials which arise in the computation of this volume.

April 30 BADmath day at SFSU
May 2 Igor Pak, UCLA Finite Tilings

Given a set of tiles (think polyominoes) and a region, can we tile the region by copies of the tiles? In general, this decision problem is undecidable for infinite regions and NP-complete for finite regions. In the case of finite regions, the problem can be solved in polynomial time for some special set of tiles and simply connected regions using combinatorial group theory or commutative algebra. On the other hand, the NP-completeness proofs rely heavily on the regions having lots of holes. Most recently, Jed Yang and I resolved this problem in the negative: we proved that for simply connected regions and rectangular tiles, the decision problem is still NP-complete. The talk will be survey style, and aimed at a general audience.

Previous seminars: spring, fall 2009; spring, fall 2010.