Author Archives: wilson.mark.c

The job market time lag: why?

Yet another press article has come out (Tech sector needs to be sexier) saying that the computer industry has a serious skills shortage. At the same time enrolments have been dropping in the CS area over several years, and not just in New Zealand, but worldwide. Again we are being told that the parents and guidance counsellors are giving poor advice to high school students, and not explaining just how strong their prospects of interesting and well-paid jobs are.

Is there a coherent theory that explains this sort of mismatch? It has been several years now – why do parents and guidance counsellors take so long to get the message? Don’t they look at any evidence and predictions by analysts? On what do they base their ideas? It seems rather odd to give advice to teenagers that may have a major impact on their future without using some rigorous analysis. Or am I missing the point?

The diameter of random Cayley digraphs of given degree

Manuel Lladser, Primoz Potocnik, Jana Siagova, Jozef Siran and Mark C. Wilson, submitted to Random Structures and Algorithms, June 2006 (12 pages)

Download author version

Abstract: We consider random Cayley digraphs of order $latex n$ with uniformly distributed generating set of size $latex k$. Specifically, we are interested in the asymptotics of the probability such a Cayley digraph has diameter two as $latex ntoinfty$ and $latex k=f(n)$. We find a sharp phase transition from 0 to 1 as the order of growth of $latex f(n)$ increases past $latex sqrt{n log n}$. In particular, if $latex f(n)$ is asymptotically linear in $latex n$, the probability converges exponentially fast to 1.

The first post

Like millions of other people, I have finally decided to start a blog. I have taken the opportunity to do some extra work and start to migrate my old website here. Thus there are a lot of posts dated before this one – there is one for each research paper, for example.

I am not known for self-deprecating statements. However starting a blog takes me outside my comfort zone of normal behaviour, so I thought I would continue this by choosing such a title. If you don’t see why it is self-deprecating, see this site and perhaps this one.

The main purpose for the moment is to force me to indite, in a disciplined way, some of the many thoughts that rattle around my brain almost continuously. I hope that others may find some of these interesting and informative. I aim to post at least once a week – let’s see what happens.

A new method for computing asymptotics of diagonal coefficients of multivariate generating functions

Alexander Raichev and Mark C. Wilson, to appear in Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007).

Download author version

Let $latex sum_{mathbf{n}inmathbb{N}^d} f_{mathbf{n}} mathbf{x}^mathbf{n}$ be a multivariate generating function that converges in a neighborhood of the origin of $latex mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $latex f_{a_1n,ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.

Note: there is a typo: in Example 3.6, we should have $latex c = ( (L-b)/a, (L-a)/b )$ where $latex L = sqrt{a^2 + b^2}$.

Random and exhaustive generation of permutations and cycles

to appear in Annals of Combinatorics (10 pages).

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. This algorithm is very similar to the standard method for generating a random permutation, but is less well known.

We consider both methods in a unified way, and discuss their relation with exhaustive generation methods. We analyse several random variables associated with the algorithms and find their grand probability generating functions, which gives easy access to moments and limit laws.

Longest alternating subsequences in pattern-restricted permutations

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

Download author version

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.