The set of ratios of derangements to permutations in digraphs is dense in [0,1/2][0, 1/2]

preprint2021arXivOpen access

Abstract

A permutation in a digraph G=(V,E)G=(V, E) is a bijection f:V→Vf:V \rightarrow V such that for all v∈Vv \in V we either have that ff fixes vv or (v,f(v))∈E(v, f(v)) \in E. A derangement in GG is a permutation that does not fix any vertex. In [1] it is proved that in any digraph, the ratio of derangements to permutations is at most 1/21/2. Answering a question posed in [1], we show that the set of possible ratios of derangements to permutations in digraphs is dense in the interval [0,1/2][0, 1/2].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.