formal power series & algebraic combinatorics 2010

some pictures

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).

SF State Home