Matjaž Konvalinka ; Igor Pak - Geometry and complexity of O'Hara's algorithm

dmtcs:2692 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2692
Geometry and complexity of O'Hara's algorithm

Authors: Matjaž Konvalinka ORCID-iD1; Igor Pak 2

  • 1 Department of Mathematics, Vanderbilt University
  • 2 School of Mathematics

In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara's bijection is efficient in most cases and mildly exponential in general. Finally, we see that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: partitions,O'Hara's algorithm,complexity,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1073/pnas.78.4.2026
Source : ScholeXplorer IsRelatedTo PMC PMC319275
Source : ScholeXplorer IsRelatedTo PMID 16593004
  • 16593004
  • PMC319275
  • PMC319275
  • 16593004
  • 10.1073/pnas.78.4.2026
  • 10.1073/pnas.78.4.2026
Method for constructing bijections for classical partition identities.

Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 154 times.