2
$\begingroup$

Let $S$ be a set with $n$ elements and let $f:S\to S$ be a random function, chosen uniformly among the $n^n$ possibilities. Considering $f$ as a directed graph of constant outdegree $1$, i. e. with vertex set $S$ and directed edges $k\to f(k)$ for all $k \in S$, $f$ decomposes into a bunch of cycles, possibly with trees attached to nodes of the cycle.

What is known about the statistics of this cycle structure, particularly in the limit $n \to \infty$?

For permutations on $n$ elements, it is known that, if $C_i$ denotes the number of cycles of length $i$, $C_1,C_2,...,C_m$ converge jointly in distribution to independent Poisson random variables with expectation values $1,1/2,...,1/m$ as $n \to\infty$. Can a similar statement be made about random endomorphisms on $n$?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Pretty much everything is known. Look at the references in this question mathoverflow.net/questions/389343/… $\endgroup$
    – Benjamin Steinberg
    Commented Apr 24, 2021 at 23:16
  • 1
    $\begingroup$ See also 6.1 of Peter Higgins book techniques of semigroup theory $\endgroup$
    – Benjamin Steinberg
    Commented Apr 24, 2021 at 23:17
  • 2
    $\begingroup$ Your question at the end can be given a positive answer with very little calculation. If we take a random map $S \to S$, and prune all the vertices of indegree zero, and repeat this process until the map restricted to the remaining vertices is a permutation, we will obtain a random permutation. Since all the cycles lie in this pruned subset, any fact about cycles that holds for a random permutation for large enough $n$ holds also for a random map for large enough $n$. $\endgroup$
    – Will Sawin
    Commented Apr 24, 2021 at 23:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .