Sexta-feira, 15 de outubro de 1999
Auditório Jacy Monteiro
Instituto de Matemática e Estatística, USP
4:20 - 5:10 Daniel Panario, University of Toronto
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 exactly 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.
Then, briefly, we comment on results previously obtained by the authors when
we allow asymptotical estimations. The class of generating functions covered
by our studies is the exp-log class where components have a singularity of the
logarithmic type. If time permits, we sketch our study of the probability
that the $j$th smallest component of an object of size $n$ be larger than $m$,
and that it be equal to $m$, $1 \leq m \leq n$ (large deviation and local
theorems). We comment on the connexion of our results to the Buchstab
function, which underlays the study of numbers up to $n$ with no primes
smaller than $m$. Expectation, variance and higher moments of the $r$th
smallest component are also derived. We finish with some examples of
applications of these results to classical combinatorial structures such as
permutations, random mappings, and 2-regular graphs.
Based on two joint works with Bruce Richmond (University of Waterloo, Canada)
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Fri Oct 8 11:55:12 EDT 1999