Building on previous work by four of us (ABCN), we consider further generalizations of Warrington's juggling Markov chains. We first introduce “multispecies” juggling, which consist in having balls of different weights: when a ball is thrown it can possibly bump into a lighter ball that is then sent to a higher position, where it can in turn bump an even lighter ball, etc. We both study the case where the number of balls of each species is conserved and the case where the juggler sends back a ball of the species of its choice. In this latter case, we actually discuss three models: add-drop, annihilation and overwriting. The first two are generalisations of models presented in (ABCN) while the third one is new and its Markov chain has the ultra fast convergence property. We finally consider the case of several jugglers exchanging balls. In all models, we give explicit product formulas for the stationary probability and closed form expressions for the normalisation factor if known.

We reinterpret and generalize conjectures of Lam and Williams as statements about the stationary distribution of a multispecies exclusion process on the ring. The central objects in our study are the multiline queues of Ferrari and Martin. We make some progress on some of the conjectures in different directions. First, we prove Lam and Williams' conjectures in two special cases by generalizing the rates of the Ferrari-Martin transitions. Secondly, we define a new process on multiline queues, which have a certain minimality property. This gives another proof for one of the special cases; namely arbitrary jump rates for three species.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

A cell complex in number theory2011In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 46, no 1-4, p. 71-85Article in journal (Refereed)

Abstract [en]

Let Delta(n) be the simplicial complex of squarefree positive integers less than or equal to n ordered by divisibility. It is known that the asymptotic rate of growth of its Euler characteristic (the Mertens function) is closely related to deep properties of the prime number system. In this paper we study the asymptotic behavior of the individual Betti numbers beta(k)(Delta(n)) and of their sum. We show that Delta(n) has the homotopy type of a wedge of spheres, and that as n -> infinity S beta(k)(Delta(n)) = 2n/pi(2) + O(n(theta)), for all theta > 17/54, Furthermore, for fixed k, beta k(Delta(n)) similar to n/2logn (log log n)(k)/k!. As a number-theoretic byproduct we obtain inequalities partial derivative(k)(sigma(odd)(k+1)(n)) infinity S beta k((Delta) over tilde (n)) = n/3 + O(n(theta)), for all theta > 22/27.

We address the problem of computing the expected reversal distance of a genome with n genes obtained by applying t random reversals to the identity. A good approximation is the expected transposition distance of a product of t random transpositions in S-n. Computing the latter turns out to be equivalent to computing the coefficients of the length function (i.e., the class function returning the number of parts in an integer partition) when written as a linear combination of the irreducible characters of Sn. Using symmetric functions theory, we compute these coefficients, thus obtaining a formula for the expected transposition distance. We also briefly sketch how to compute the variance.

KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.

Eriksson, K.

Sjostrand, J.

Note on the lamp lighting problem2001In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 27, no 03-feb, p. 357-366Article in journal (Refereed)

Abstract [en]

We answer some questions concerning the so-called sigma -game of Sutner [Linear cellular automata and the Garden of Eden, Math. Intelligencer 11 (1989), 49-53]. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m x n grid is odd or even.

We define a class of hypercubic (shape [n](d)) arrays that in a certain sense are d-dimensional analogs of permutation matrices with our motivation from algebraic geometry. Various characterizations of permutation arrays are proved. an efficient generation algorithm is given, and enumerative questions are discussed although not settled. There is a partial order on the permutation arrays, specializing to the Bruhat order on S-n, when d equals 2, and specializing to the lattice of partitions of a d-set when n equals 2.

We study a decomposition of Fl(n)(d-1), where: Fl(n) denotes the flag manifold over C-n. The strata are defined by the dimensions of intersections of one space from each fag, so for d equal to 2 this is the usual Bruhat cell decomposition, The strata are indexed by permutation arrays, which are d-dimensional analogs of permutation matrices. We present a partial order on these permutation arrays, specializing: to the Bruhat order on S-n when d equals 2 and to the lattice of partitions of a d-set when n equals 2.

8.

Eriksson, Kimmo

et al.

Mälardalen University, School of Education, Culture and Communication.

Sjöstrand, Jonas

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).

We consider a family of birth processes and birth-and-death processes on Young diagrams of integer partitions of n. This family incorporates three famous models from very different fields: Rost's totally asymmetric particle model (in discrete time), Simon's urban growth model, and Moran's infinite alleles model. We study stationary distributions and limit shapes as n tends to infinity, and present a number of results and conjectures.

We investigate the topology and combinatorics of a topological space called the edge-product space that is generated by the set of edge-weighted finite labelled trees. This space arises by multiplying the weights of edges on paths in trees, and is closely connected to tree-indexed Markov processes in molecular evolutionary biology. In particular, by considering combinatorial properties of the Tuffley poset of labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset.

It is well known that a Coxeter group W, partially ordered by the Bruhat order, is a graded poset, with rank function given by the length, and that it is EL-shellable, hence Cohen-Macaulay, and Eulerian. We ask whether Invol(W), the subposet of W induced by the set of involutions, is endowed with similar properties. If W is of type A or B, we proved, respectively in [F. Incitti, The Bruhat order on the involutions of the symmetric group, J. Algebraic Combin. 20 (2004), 243-261] and [F. Incitti, The Bruhat order on the involutions of the hyperoctahedral group, European J. Combin. 24 (2003), 825-848], that Invol(W) is graded, EL-shellable and Eulerian. In this work we complete the investigation on the classical Weyl groups, extending these results to type D and providing a unified description for the rank function.