PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Robert Vaughan.

Title:Geometry and complexity of O'Hara's algorithm
Seminar:Algebra and Number Theory Seminar
Speaker:Igor Pak, University of Minnesota
Abstract:
O'Hara's algorithm is a well known bijection generalizing Glaisher's bijection between partitions into distinct and odd parts, a classical combinatorial proof of Euler's result. The bijection is very natural and easy to state but its inner working is rather mysterious. Until now, even the number of steps of this bijection (viewed as an algorithm) remained wide open. In this talk I will discuss the geometry behind this bijection and present a number of complexity results. Among other things, when the number of part sizes is bounded, we show that the map of O'Hara's bijection can be computed in polynomial time, while O'Hara's algorithm is exponential. No previous knowledge of partition theory is assumed. This is joint work with Matja Konvalinka.

Room Reservation Information

Room Number:MB106
Date:11 / 13 / 2008
Time:11:15am - 12:05pm