Author Archives: wilson.mark.c

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.

Asymptotics of the minimum manipulating coalition size for positional voting rules under IC behaviour

Geoffrey Pritchard and Mark C. Wilson, submitted to Journal of Economic Theory, February 2007 (20 pages).

Download author version

Abstract: We consider the problem of manipulation of elections using positional voting rules under Impartial Culture voter behaviour. We consider both the logical possibility of coalitional manipulation, and the number of voters that must be recruited to form a manipulating coalition. It is shown that the manipulation problem may be well approximated by a very simple linear program in two variables. This permits a comparative analysis of the asymptotic (large-population) manipulability of the various rules. It is seen that the manipulation resistance of positional rules with 5 or 6 (or more) candidates is quite different from the more commonly analyzed 3- and 4-candidate cases.

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.

Probability calculations under the IAC hypothesis

Mark C. Wilson and Geoffrey  Pritchard, Mathematical Social Sciences 54 (2007), 244-256.

Download author version

Abstract: We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.

Exact results on manipulability of positional voting rules

Geoffrey Pritchard and Mark C. Wilson, Social Choice and Welfare 29 (2007), 487-513.

Download author version

Abstract:

We consider 3-candidate elections under a general scoring rule and derive precise conditions for a given voting situation to be strategically manipulable by a given coalition of voters. We present an algorithm that makes use of these conditions to compute the minimum size M of a manipulating coalition for a given voting situation.

The algorithm works for any voter preference model — here we present numerical results for IC and for IAC, for a selection of scoring rules, and for numbers of voters up to 150. A full description of the distribution of M is obtained, generalizing all previous work on the topic.

The results obtained show interesting phenomena and suggest several conjectures. In particular we see that rules “between plurality and Borda” behave very differently from those “between Borda and antiplurality”.

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