Coalescence under Preimage Constraints

Abstract

The primary goal of this document is to record the asymptotic effects that preimage constraints impose upon the sizes of the iterated images of a random function. Specifically, given a subset $\mathcal{P}\subseteq {\mathbb{Z}}_{\ge 0}$ and a finite set $S$ of size $n$, choose a function uniformly from the set of functions $f:S\to S$ that satisfy the condition that $|f^{-1}(x)|\in \mathcal{P}$ for each $x\in S$, and ask what $|f^k(S)|$ looks like as $n$ goes to infinity. The robust theory of singularity analysis allows one to completely answer this question if one accepts that $0\in \mathcal{P}$, that $\mathcal{P}$ contains an element bigger than 1, and that $\gcd (\mathcal{P})=1$; only the third of these conditions is a meaningful restriction. The secondary goal of this paper is to record much of the background necessary to achieve the primary goal.

68 pages, 24 figures