COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2012

A solution to Wilf's sigma tau problem
Aaron Williams
Department of Mathematics and Statistics, McGill University
Friday Feb. 24, 2:30-3:30pm, ECS 660

The symmetric group S(n) can be generated by two simple operations: A rotation σ = (1 2 ... n), and a swap τ = (1 2). In 1975, Herb Wilf (1931-2012) asked if a stronger result holds: Can S(n) can be sequenced "so that each is obtained from its predecessor" by σ or τ? For example,

Don Knuth rates Wilf's problem as the second most difficult open problem in his new volume of The Art of Computer Programming, and states that solutions may not be of practical value due to their complexity. In this talk we solve the sigma tau problem by constructing a cyclic solution when n is odd, and a non-cyclic solution when n is even. (This is best possible, since a campanological result by Rankin and Swan proves there are no cyclic solutions when n is even.) The construction leads to a simple algorithm that creates each successive permutation in O(1) amortized time.

Short-range communication devices have enabled the large-scale dissemination of information through user mobility and contact, without the assistance of communication infrastructures. However, the intermittent connectivity, makes it challenging to determine when and how to forward a message possibly through a series of third parties to deliver it to the destination. This problem has attracted a lot of attention in the literature lately, with proposals ranging from oblivious epidemic to context-aware schemes. However most existing work assumed either independent or identical mobility characteristic across the users population. Observing most human mobility and interaction are interest-driven in the real world, in this research, we evaluate the performance of these schemes with an interest-driven mobility model. We further propose to take the user interest into account when determining routing strategies to further improve the performance of these schemes for mobile social networks. Simulation results have demonstrated the efficacy of the interest-aware routing strategies.

We work with small size balanced subsets of Z_p when p is prime. In a balanced set S, each element x in S is a midpoint between two other elements from S, i.e. 2x=y+z (mod p), y, z in S\{x}. Denote the minimum cardinality of a balanced set modulo p by α(p). We prove a new lower bound for α(p): for every prime p > 2, α(p) >= log₂ (p) + 1.41. Small balanced sets are needed in strategies for the family of combinatorial games analyzed in several papers by Z. Nedev and A. Quas.