Abstracts for The Bay Area Discrete Math Day, Spring 2003

• 10:00-11:00 Craig Tracy (UC Davis)
  A Limit Theorem for Shifted Schur Measure

  To each partition λ=(λ₁,λ₂,...) with distinct parts we assign the probability Q_λ(x) P_λ(y)/Z where Q_λ and P_λ are the Schur Q-functions and Z is a normalization constant. This measure, which we call the shifted Schur measure, is analogous to the much-studied Schur measure. For the specialization of the first m coordinates of x and the first n coordinates of y equal to α (0 < α < 1) and the rest equal to zero, we derive a limit law for m,n → ∞ with m/n fixed. For the Schur measure the α-specialization limit law was derived by Johansson. Our main result implies that the two limit laws are identical. This work is joint work with Harold Widom.
  ps or pdf

• 11:10-11:40 Ezra Miller (MSRI)
  Unfolding polyhedra in many dimensions

  It is unknown at present whether the boundary of every 3-polytope can be unfolded onto the plane after cutting along some of its edges. However, if the cuts are allowed to pass through interiors of faces, then unfoldings are known to exist, and algorithms for constructing them are important in robotics and computer graphics. This talk generalizes to arbitrary dimension the constructions and algorithms for unfolding convex polyhedral boundaries, with cuts through facets allowed. Analyzing the complexity of the algorithms raises fundamental enumerative questions concerning metric geometry of polytopes. This work is joint with Igor Pak.

• 12:10-12:40 Mark Cooke (Network Appliance)
  Simulated Annealing and Combinatorial Problems

  Simulated annealing is a popular heuristic that is often presented as an alternative to backtracking and integer programming techniques. I will present recent work on combining simulated annealing with these methods to solve difficult combinatorial problems. I will present a case study in optimizing cruise line promotions, emphasizing the engineering aspects of the solution approach. I will also discuss recent work in exploring Gray codes, including the approach used to find the first 8-bit Beckett-Gray codes.

• 2:00-3:00 Peter Littelmann (Universität Wuppertal/MSRI)
  LS-galleries, the affine grassmann variety and the path model

  We present a new version of the path model for representations of a semisimple group G. We replace in the new setting the LS-paths by certain galleries in the affine Coxeter complex. Using the corresponding affine building, we associate in a canonical way to the model some finite dimensional projective varieties in the affine grassmann variety associated to G. It turns out that these are precisely the cycles investigated by Mirkovic and Vilonen in their proof of a geometric version of the Satake isomorphism.

• 3:15-3:45 Joseph Gubeladze (San Francisco State University)
  Unimodular triangulations and covers of multiples of polytopes

  The Knudson-Mumford classical result says that all high multiples of a convex lattice polytope have unimodular triangulations. I will discuss the algebra related to this result (in toric geometry, commutative algebra) as well as an effective version of a weaker claim on unimodular covers. This constitutes my joint work with Winfried Bruns. Finally, I will explain why one can hope for an "effective Knudson-Mumford" (still not proved) - for every natural number d there is a natural number c_d such that c_d P has a unimodular triangulation for arbitrary d-dimensional lattice polytope P.

• 4:15-5:15 Mark Haiman (UC Berkeley)
  Diagonal coinvariants for Weyl groups

  The coinvariant ring for a finite group G acting on a vector space V is the quotient of the polynomial ring k[V] by the ideal generated by G-invariant polynomials without constant term. Recently I proved that for the "diagonal" action of the symmetric group S_n on two copies H&oplus H of its natural representation H, the coinvariant ring has dimension (n+1)^(n-1). Earlier I had conjectured that the corresponding number for a Weyl group W acting diagonally should be (h+1)^r, where h is the Coxeter number and r is the rank -- provided that in general the space with this dimension is not the coinvariant ring itself, but some naturally occuring proper quotient of it. Iain Gordon has proved my conjecture using representation theory of Cherednik algebras. I will explain the background material and Gordon's result.
  ps or pdf