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