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 |
|---|
