Nevin Kapur: Singularity Analysis for Hadamard products, with Applications

This is a joint work with Jim Fill and Philippe Flajolet.

Philippe Flajolet and Andrew Odlyzko developed singularity analysis as ``a class of methods by which one can translate, on a term-by-term basis, an asymptotic expansion of a function around a dominant singularity into a corresponding asymptotic expansion for the Taylor coefficients of the function.'' I will discuss results that extend this class, primarily the determination of how singularities get composed under the Hadamard product of series, defined as

$$\mbox{$(f \odot g)(z) := \displaystyle\sum_n f_n g_n z^n$ f... ...aystyle\sum_n f_n z^n$, $g(z) = \displaystyle\sum_n g_n z^n$.}$$

I will show how these results can be used to analyze asymptotically recurrences arising in various settings including the random permutation and uniform model on binary search trees and the evolution of random graphs.

Bibliography

Fla99

Philippe Flajolet.
Singularity analysis and asymptotics of Bernoulli sums.
Theoret. Comput. Sci., 215(1-2):371-381, 1999.

FO90

Philippe Flajolet and Andrew Odlyzko.
Singularity analysis of generating functions.
SIAM J. Discrete Math., 3(2):216-240, 1990.

Back to the Index