Description of my past research

We continued this research in the paper "Decompositions of partially ordered sets" (to appear in Order). We show that the order complex of every graded poset has a ``weak'' shelling such that the intersection of each cell with the previously attached cells is homotopic to a ball or to a sphere. Generalizing the labeling technique used in the proof of our main theorem on the closure of the convex cone generated by all flag f-vectors of graded posets, we introduce the notion of ``chain-edge labeling with the first atom property'', or FA-labeling. These labelings generalize lexicographic shellings, introduced by Björner and Wachs. Another special subclass of FA-labelings provides a description of the cone of flag f-vectors of planar graded posets, and suggests a planar analogue of the flag h-vector. For planar Cohen-Macaulay posets the two h-vectors turn out to be equal, and the cone of flag h-vectors an orthant, whose dimension is a Fibonacci number.

I continued this research with R. Ehrenborg. In our paper "Flags and shellings of Eulerian cubical posets" we show a cubical analogue of Stanley's theorem expressing the cd-index of an Eulerian simplicial poset in terms of its h-vector. Our result implies that the cd-index conjecture for Gorenstein* cubical posets follows from Ron Adin's conjecture on the nonnegativity of his cubical h-vector for Cohen-Macaulay cubical posets. We show a cubical analogue of Stanley's conjecture about the connection between the cd-index of semisuspended simplicial shelling components and the reduced variation polynomials of certain subclasses of André permutations. The notion of signed André permutation used in this result is a common generalization of two earlier definitions of signed André-permutations. I presented a talk about this second paper at the 7th Conference on Formal Power Series and Algebraic Combinatorics (Paris May 1995).

In our paper "Permutation trees and variation statistics" (European Journal of Combinatorics, 19 (1998), 847-866) with E. Reiner we exploit binary tree representations of permutations to give a combinatorial proof of Purtill's result on the equality between the total cd-variation of André permutations and the total ab-variation of all permutations. Using Purtill's proof as a motivation we introduce a new "Foata-Strehl-like" action on permutations. This action allows us to give an elementary proof of Purtill's theorem and a bijection between André permutations of the first kind and alternating permutations starting with a descent. A modified version of our group action leads to a new class of André-like permutations with structure similar to that of simsun permutations.

I have showed that it is necessary that neither A nor B contain any idempotents and that they both have the one-sided cancellation property from the same side. Thus in the case of commutative semigroups we obtain a necessary and sufficient condition. In the general case, I show that no more necessary conditions may be imposed simultaneously on the elements of A and B.

In our paper "On the Diameter of Random Cayley Graphs of the Symmetric Group" (Combinatorics, Probability & Computing 1 (1992), 201-208) with L. Babai we show that when we take a random pair of elements of S_n, the Cayley graph of the generated group with respect to these two elements as generators is almost always at most exp((1/2+o(1))ln²n). ("Almost always" means that the probability of the contrary event converges to zero when n tends to infinity.) Together with a result of Dickson, which shows that a random pair of permutations generate almost always at least A_n, we obtain an upper bound for diam Gamma(A_n,S) which holds for almost all (A_n,S), and is much lower than the best known deterministic upper bound.