abstracts of the main talks
Bill Chen (Nankai University, China)
Recent developments on log-concavity and q-log-concavity of combinatorial polynomials
In this talk, I wish to report
some recent work with my students and colleagues
at Nankai University on log-concavity and
q-log-concavity of combinatorial polynomials.
While this is a classical subject of algebraic
combinatorics, interesting problems and techniques
continue to emerge.
(1) We proved the unimodality conjecture on
balanced colorings of the n-cube proposed by
Palmer, Read and Robinson, and obtained a log-
concavity theorem for sufficiently large n.
(2) We proved the ratio monotone property of the
Boros-Moll polynomials which is stronger than the
log-concavity. We further proved the 2-log-concavity
which was considered as a difficult problem.
The 2-log-convexity of the Apery numbers has
been established. We obtained the reverse ultra
log-concavity of the Boros-Moll polynomials,
and confirmed Moll's minimum conjecture.
A combinatorial approach has been found to justify
the log-concavity and other properties of the Boros-Moll polynomials.
(3) By using the Littlewood-Richardson rule, we
obtained certain Schur positivity results that
lead to a proof of the q-log-convexity conjecture
for the Narayana polynomials.
(4) By establishing the strong q-log-concavity of
q-Narayana numbers Nq(n,k) for fixed k,
we confirmed the 2-fold case of the q-log-concavity
conjecture for the Gaussian coefficients proposed
by McNamara and Sagan.
(5) We found a unified approach to the
q-log-convexity of the Bell polynomials, the
Bessel polynomials, the Ramanujan polynomials and
the Dowling polynomials.
(6) We shall also mention some open problems.
Persi Diaconis (Stanford University, USA)
A probabalistic interpretation of the Macdonald polynomials
The two-parameter Macdonald polynomials are a central object of study in algebraic
combinatorics. Arun Ram and I have found a simple Markov chain on partitions (with
stationary distributon the Macdonald weight) whose eigenfunctions are the
co-efficients of the Macdonald polynomials when expanded in the power sums. In turn,
this Markov chain is a special case of classical algorithms in statistical mechanics
(Swedsen-Wang and auxiliary variable algorithms). The wealth of knowledge about
Macdonald polynomials allows a sharp analysis of the rate of convergence of the
Markov chain to stationarity.
Alicia Dickenstein (Universidad de Buenos Aires, Argentina)
Hypergeometric series with algebro-geometric dressing
Important classical functions as well as generating functions
associated to combinatorial objects are given by series whose
coefficients satisfy hypergeometric recurrences. Following Gelfand,
Kapranov and Zelevinsky, who defined A-hypergeometric systems
satisfied by suitable homogeneous versions of classical hypergeometric
functions, we will present joint work with Eduardo Cattani, Laura
Matusevich, Fernando Rodríguez Villegas, Timur Sadykov and Bernd
Sturmfels, to describe the structure of rational hypergeometric series
in two variables and the ocurrence of finite solutions to
hypergeometric recurrences.
Joseph Gubeladze (San Francisco State University, USA)
Normal polytopes
In Section 1 we overview combinatorial results on normal
polytopes, old and new. These polytopes represent central objects
of study in the contemporary discrete convex geometry, on the
crossroads of combinatorics, commutative algebra, and algebraic
geometry. In Sections 2 and 3 we describe two very different
possible ways of advancing the theory of normal polytopes to next
essential level, involving arithmetic and topological aspects.
Florent Hivert (Université de Rouen, France)
Combinatorial representation theory of algebras: the example of j-trivial monoids
The representation theory of algebras is a very important source of
interesting combinatorics. The symmetric groups leading to the combinatorics
of tableaux is certainly the most striking example, but it is far from being
unique: other examples include the various Hecke algebras, descent
algebras... Another interesting feature of the representation theory of the
finite dimensional algebras is that it is mostly effective. As a consequence,
with the appropriate tools one can very easily use computers for exploration.
The goal of the talk is to discuss these features together with the simple
remark that several recently studied algebras are in fact monoid algebras:
examples are 0-Hecke algebras, degenerated Ariki-Koiki algebras, Solomon-Tits
algebras. Apparently, the fact that they are indeed monoid algebras wasn't
used in those studies. However, from recent results in semigroups theory it
seem that a lot of representation theory of a semigroup algebra is of
combinatorial nature (provided the representation theory of groups is
known). One can expect, for example, that for aperiodic semigroup (semigroup
which doesn't contains non trivial groups), most of the combinatorial
information (dimensions of the simple/projective indecomposable,
induction/restriction constants/Cartan's invariants) can be computed without
using any linear algebra.
In this talk, we will focus on the so-called J-trivial monoids, which are
the monoids M such that the product has the following triangular properties:
there exists a partial ordering <= on M such that for a x, y in M, one
had xy <= x and xy <= y. A typical example is the 0-Hecke monoid of
a Coxeter group. We will show that for such a monoid, most of the
combinatorial data of the representation theory including the Cartan's
invariant matrix and the quiver can be expressed by counting particular kinds
of elements in the monoid itself.
This is a joint work with Tom Denton, Anne Schilling and Nicolas Thiéry.
Tara Holm (Cornell University, USA)
The discrete geometry of moment polytopes
Moment polytopes are convex polytopes associated to Hamiltonian systems in symplectic geometry. The discrete geometry of the moment polytope can tell us a good deal about the global geometry and topology of the corresponding system. I will give a brief introduction to symplectic geometry to show how moment polytopes arise, followed by a survey demonstrating how combinatorial techniques can be brought to bear on topological questions.
Jon McCammond (University of California, Santa Barbara, USA)
Posets and curvature
It is extremely common to convert a partially ordered set into a simplicial complex and to correlate the topology of the resulting space with the structure of the original poset. In this talk, I discuss how the adding a metric perspective and introducing notions such as curvature from geometric group theory help to enhance this connection. (Joint work with Tom Brady)
Ileana Streinu (Smith College, USA)
Rigidity, sparsity and pebble games
A famous open problem, going back to the work of James Clerk Maxwell in 1864, is to give a combinatorial characterization for generically rigid frameworks made from bars connected by rotatable joints. The same question can be asked for a long list of other geometrically constrained systems, but only very few answers are known. They include bar-and-joint frameworks in dimensions one and two, body-and-bar structures in arbitrary dimensions and a few other isolated instances such as skeleta of triangulated 3D polyhedra. The underlying combinatorial structure, in all these cases, is a graph satisfying some linear sparsity conditions. The pebble games are simple construction rules characterizing exactly those classes of sparse (hyper)graphs which are matroids. On the other hand, for Maxwell's problem the necessary (but not sufficient) sparsity condition falls "just below" the matroidal range.
This talk will present these varied facets of combinatorial rigidity (accompanied by a variety of visual and physical props), and will conclude with some recent results.
Peter Winkler (Dartmouth College, USA)
The Worm order and its applications
Let x and y be two words in a linearly-ordered alphabet
(such as the real numbers). We say that x is below y in
the worm order if they can be "scheduled" in such a way that
x is always less than or equal to y.
It turns out that in any submodular system there is a
maximal chain that is minimal in the worm order, among all
paths from 0 to 1. One consequence is a set of general
conditions under which parallel scheduling can be done without
backward steps.
Among the applications are a fast algorithm for scheduling
multiple processes without overusing a resource; a theorem about
searching for a lost child in a forest; and a closed-form expression
for the probability of escaping from the origin in a form of
coordinate percolation.
Joint work in part with Graham Brightwell (LSE) and in part
with Lizz Moseman (USMA).
