On f-Derangements and Decomposing Bipartite Graphs into Paths

Abstract

Let $f:\{1,...,n\}\to \{1,...,n\}$ be a function (not necessarily one-to-one). An $f-derangement$ is a permutation $g:\{1,...,n\}\to \{1,...,n\}$ such that $g(i)\ne f(i)$ for each $i=1,...,n$. When $f$ is itself a permutation, this is a standard derangement. We examine properties of f-derangements, and show that when we fix the maximum number of preimages for any item under $f$, the fraction of permutations that are f-derangements tends to $1/e$ for large $n$, regardless of the choice of $f$. We then use this result to analyze a heuristic method to decompose bipartite graphs into paths of length 5