Category Archives: Research

Longest alternating subsequences in pattern-restricted permutations

Ghassan Firro, Toufik Mansour and Mark C. Wilson, Electronic Journal of Combinatorics 14 (2007), R34 (11 pages).

Abstract: Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.

Twenty combinatorial examples of asymptotics derived from multivariate generating functions

Robin Pemantle and Mark C. Wilson, to appear in SIAM Review, June 2008.

Download author version

Abstract: Let $latex F$ be a power series in at least two variables that defines a meromorphic function in a neighbourhood of the origin; for example, $latex F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $latex F$, uniform in certain explicitly defined cones of directions.

The purpose of this article is to illustrate the use of these techniques on a variety of problems of combinatorial interest. The first part reviews the Morse-theoretic underpinnings of these techniques, and then summarizes the necessary results so that only elementary analyses are needed to check hypotheses and carry out computations. The remainder focuses on combinatorial applications. Specific examples deal with enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, descents and solutions to integer equations. After the individual examples, we discuss three broad classes of examples, namely functions derived via the transfer matrix method, those derived via the kernel method, and those derived via the method of Lagrange inversion. Generating functions derived in these three ways are amenable to our asymptotic analyses, and we state some further general results that apply to these cases.

Some old talks

Here are slides for recent talks, in reverse chronological order of delivery. If the date is incomplete, then the slides are not yet available, probably because the talk has not yet been given. Slides for several earlier talks seem no longer to be available. I will be putting up any newer talks as individual blog posts.

Asymptotics of coefficients of multivariate generating functions Workshop in Asymptotic Enumeration, ANU, Canberra, 2007-09-{10-14}.

Polytope computations in social choice theory Auckland Discrete Mathematics and Social Sciences Seminar 2007-04-23.

The diameter of random Cayley graphs 12th AofA workshop Alden Biesen 2006-07-06

Asymptotics of generalized Riordan arrays 11th AofA workshop Barcelona 2005-06-08

Multivariate generating functions II CDMTCS seminar Auckland 2005-04-26

Multivariate generating functions I CDMTCS seminar Auckland 2005-04-12

Sattolo’s algorithm INRIA Rocquencourt 2004-06-28

Towards a theory of multivariate generating functions INRIA Rocquencourt 2004-06-28

Asymptotics of multivariate generating functions Melbourne FPSAC conference 2002-07-

Superalgebras and their uses Missoula 1999-03-09

Primitive ideals in Hopf algebra extensions San Antonio 1999-01-14

Algebras of my acquaintance Auckland 1998-04-29

Asymptotics for generalized Riordan arrays

Mark C. Wilson, Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334 (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).

Download author version

Abstract: The machinery of Riordan arrays has been used recently by several authors. We show how meromorphic singularity analysis can be used to provide uniform bivariate asymptotic expansions, in the central regime, for a generalization of these arrays. We show how to do this systematically, for various descriptions of the array. Several examples from recent literature are given.

Probability generating functions for Sattolo’s algorithm

Mark C. Wilson, Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue on probabilistic analysis of algorithms).

Download author version

Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.

The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results results by determining the “grand” probability generating functions of the random variables.

The focus throughout is on using standard methods that give a unified approach, and open the door to further study.

Asymptotics of multivariate sequences, part II: multiple points of the singular variety

Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.

Download author version

Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.

In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.

Asymptotics of multivariate sequences, part I: smooth points of the singular variety

Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory Series A 97 (2002), 129-161.

Download author version

Abstract: Given a multivariate generating function $latex F(z_1 , ldots , z_d) = sum a_{r_1 , ldots , r_d} z_1^{r_1} cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy’s integral formula near singular points of $latex F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $latex F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $latex F$ where the local geometry is more complicated, and for which other methods of analysis are not known.

Associative algebras satisfying a semigroup identity

D. M. Riley and Mark C. Wilson, Glasgow Mathematical Journal 41 (1999), 453-462.

Download author version

Abstract: Denote by $latex (R,cdot)$ the multiplicative semigroup of an associative algebra $latex R$ over an infinite field, and let $latex (R,circ)$ represent $latex R$ when viewed as a semigroup via the circle operation $latex xcirc y=x+y+xy$. In this paper we characterize the existence of an identity in these semigroups in terms of the Lie structure of $latex R$. Namely, we prove that the following conditions on $latex R$ are equivalent: the semigroup $latex (R,circ)$ satisfies an identity; the semigroup $latex (R,cdot)$ satisfies a reduced identity; and, the associated Lie algebra of $latex R$ satisfies the Engel condition. When $latex R$ is finitely generated these conditions are each equivalent to $latex R$ being upper Lie nilpotent.