Daniel Panario, University of Toronto (daniel@cs.toronto.edu)

Exact largest and smallest size of components in decomposable structures

Golomb and Gaal (1998) study the number of permutations on $n$ objects with largest cycle length equal to $k$. They give explicit expressions on ranges $n/(i+1) < k \leq n/i$ for $i=1, 2, \ldots$, derive a general recurrence for the number of permutations of size $n$ with largest cycle length equal to $k$, and provide the contribution of the ranges $(n/(i+1),n/i]$ for $i=1, 2, \ldots$, to the expected length of the largest cycle.

In this talk, we show how to generalize their work in several ways. We provide exact extremal properties in random decomposable combinatorial structures. These structures include permutations, polynomials over finite fields, and several others (in both the labelled and unlabelled cases). The extremal properties include the same type of results as the ones of Golomb and Gaal (1998) but for the number of objects of size $n$ with largest (and smallest) size of components exactly equal to $k$. The results are derived using basic combinatorial tools like generating functions. [Joint work with Bruce Richmond.]