A Tree Pruning Approach to the Hurwitz Enumeration Problem

   John Irving, (Wilfred Laurier University)



The primary focus of this talk will be the Hurwitz enumeration problem, which asks for the number H_0(\pi) of decompositions of a given permutation \pi into an ordered product of a minimal number of transpositions such that these factors act transitively on the underlying set of symbols. (The problem is typically phrased in terms of counting almost simple branched coverings of the sphere by the sphere with arbitrary ramification over one special point, but the two phrasings are equivalent.) I shall demonstrate that these transitive factorizations can be encoded as planar edge-labelled maps with certain descent structure, and describe a bijection that ``prunes trees'' from such maps. This allows for a shift in focus from the combinatorics of factorizations to the sometimes more manageable combinatorics of smooth maps. As a result, we gain combinatorial insight into the nature of Hurwitz's famous formula for H_0(\pi), and derive new bijections that prove his formula in certain restricted cases.

Applied Algebra seminar home