2022/01/07 by Plantholt, Michael, Habibi, Hamidreza, Mussell, Benjamin
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.02332
Let f: \1, ..., n\ → \1, ..., n\ be a function (not necessarily one-to-one). An f-derangement is a permutation g:\1,...,n\ → \1,...,n\ such that g(i) ≠ 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