On the Deepest Cycle of a Random Mapping

Abstract: Let

m a t h c a l T_{n}

be the set of all mappings

T : 1, 2, l d o t s, n o 1, 2, l d o t s, n

. The corresponding graph of

T

is aunion of disjoint connected unicyclic components. We assume that each

T i n m a t h c a l T_{n}

is chosen uniformly at random (i.e., with probability

n^{- n}

). The deepest cycle of

T

is contained within its largest component. Let

u_{n} = u_{n} (T)

denote the length of the deepest cycle in

T i n m a t h c a l T_{n}

. In this paper, we find the limits of the expectation and variance of

u_{n} / s q r t n

as

n o i n f t y

. For

n

large enough, we also show that nearly

55 %

of all cyclic vertices of a random mapping

T i n m a t h c a l T_{n}

lie in the deepest cycle and that a vertex from the longest cycle of

T

does not belong to its largest component with approximate probability

0.075

.

This page was built for publication: On the Deepest Cycle of a Random Mapping