Daniel Panario, Department of Computer Science, University of Toronto

Smallest components in combinatorial structures

The smallest size of random decomposable combinatorial structures is studied in a general framework. These results apply to several combinatorial structures in both the labelled and the unlabelled case. Typical examples are the cyclic decomposition of permutations and the factorization of polynomials over finite fields into irreducible factors.

First, we briefly comment on the exp-log class and functions with a singularity of the logarithmic type. Then, we study the probability that the $j$th smallest component of an object of size $n$ be larger than $m$, $1 \leq m \leq n$. From this we derive local results, expectation and variance for the smallest components. We finish with some examples of applications of these results to classical combinatorial structures.