Tag Archives: combinatorics

An interesting new Mahonian permutation statistic

While studying the standard method for random permutation generation I discovered a function whose distribution on a uniformly random permutation of fixed length is the same as that of the number of inversions. Such things are called Mahonian permutation statistics.

This statistic appears to be new, but this is not as easy to show as I would like. After several attempts to find out by reading papers, asking experts and doing database searches, I concluded that it probably was and submitted the paper to the arXiv and for publication. Almost immediately I got email from Dennis White at University of Minnesota pointing out a connection with a paper by him and Galovich in 1996. This raises some questions: how much responsibility do we have in the modern research environment to check novelty? why is there no standard database of numerical values of all important functions, and how do we achieve one?

Abstract: The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic $stat$ that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics $des$ and $exc$ appear to coincide with any known Euler-Mahonian pair.
A general construction of Skandera yields an Eulerian partner $ska$ such that $(ska, stat)$ is equidistributed with $(des, maj)$. However $ska$ itself appears not to be a known Eulerian statistic.
Several ideas for further research on this topic are listed.

Download author copy

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.

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.

Degree- and time-constrained broadcast networks

Michael J. Dinneen, Geoffrey Pritchard and Mark C. Wilson, Networks 39 (2002), 1–9.

Download author version

Abstract: We consider the problem of constructing networks with as many nodes as possible, subject to upper bounds on the degree and broadcast time. The paper includes the results of an extensive empirical study of broadcasting in small regular graphs using a stochastic search algorithm to approximate the broadcast time. Significant improvements on known results are obtained for cubic broadcast networks.

Construction of time-relaxed minimal broadcast networks

Michael J. Dinneen, Jose A. Ventura, Mark C. Wilson and Golbon Zakeri, Parallel Processing Letters 9 (1999), 53-68.

Download author version

Abstract: In broadcasting, or one-to-all communication, a message originally held in one node of the network must be transmitted to all the other nodes. A minimal broadcast network is a communication network that can transmit a message originated at any node to all other nodes of the network in minimum time. In this paper, we present a compound method to construct sparse, time-relaxed, minimal broadcast networks ($latex t$-mbn), in which broadcasting can be accomplished in slightly more than the minimum time. The proposed method generates a new network by connecting a subset of nodes from several copies of a $latex t_1$-mbn using the structure of another $latex t_2$-mbn. The objective is to construct a network as sparse as possible satisfying the desired broadcasting time constraint. Computational results illustrate the effectiveness of the proposed method.