We consider the problem of counting <i>transitive factorizations</i> of permutations; that is, we study tuples (σ<i>r</i>,. . . ,σ1) of permutations on {1,. . . ,<i>n</i>} such that (1) the product σ<i>r</i>. . . σ1 is equal to a given target permutation π, and (2) the group generated by the factors σ<i>i</i> acts transitively on {1,. . . ,<i>n</i>}. This problem is widely known as the <i>Hurwitz Enumeration Problem</i>, since an encoding due to Hurwitz shows it to be equivalent to the enumeration of connected branched coverings of the sphere by a surface of given genus with specified branching. Much of our work concerns the enumeration of transitive factorizations of permutations into a minimal number of transposition factors. This problem has received considerable attention, and a formula for the number <i>c</i>(π) of such factorizations of an arbitrary permutation π has been derived through various means. The formula is remarkably simple, being a product of well-known combinatorial numbers, but no bijective proof of it is known except in the special case where π is a full cycle. A major goal of this thesis is to provide further combinatorial rationale for this formula. We begin by introducing an encoding of factorizations (into transpositions) as edge-labelled maps. Our central result is a bijection that allows trees to be "pruned" from such maps. This is shown to explain the appearance of factors of the form <i>k^k</i> in the aforementioned formula for <i>c</i>(π). It also has the effect of shifting focus to the combinatorics of smooth maps (<i>i. e. </i> maps without vertices of degree one). By providing decompositions for certain smooth planar maps, we are able to give combinatorial evaluations of <i>c</i>(π) when π is composed of up to three cycles. Many of these results are generalized to factorizations in which the factors are cycles of any length. We also investigate the <i>Double Hurwitz Problem</i>, which calls for the enumeration of factorizations whose leftmost factor is of specified cycle type, and whose remaining factors are transpositions. Finally, we extend our methods to the enumeration of factorizations up to an equivalence relation induced by possible commutations between adjacent factors.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1102 |
| Date | January 2004 |
| Creators | Irving, John |
| Publisher | University of Waterloo |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | application/pdf, 1639162 bytes, application/pdf |
| Rights | Copyright: 2004, Irving, John. All rights reserved. |
Page generated in 0.0025 seconds