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

DOI10.37236/10293MaRDI QIDQ2073299zbMATH OpenOpenAlexFDO

Authors Bethany Austhof, Patrick Bennett, Nick Christo

Publication date 1 February 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.02995

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

number of permutationsratios of derangements

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30)

Abstract: A permutation in a digraph $G=(V,E)$ is a bijection $f:VightarrowV$ such that for all $vinV$ we either have that $f$ fixes $v$ or $(v,f(v))inE$. A derangement in $G$ 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/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]$.

Review text

Summary: A permutation in a digraph \(G=(V, E)\) is a bijection \(f:V \rightarrow V\) such that for all \(v \in V\) we either have that \(f\) fixes \(v\) or \((v, f(v)) \in E\). A derangement in \(G\) is a permutation that does not fix any vertex. \textit{M. Bucic} et al. [``Perfect matchings and derangements on graphs, J. Graph Theory 97, No. 2, 340--354 (2021; \url{doi:10.1002/jgt.22658})] proved that in any digraph, the ratio of derangements to permutations is at most \(1/2\). Answering a question posed by Bucic et al. [loc. cit.], we show that the set of possible ratios of derangements to permutations in digraphs is dense in the interval \([0, 1/2]\).

Recommendations

• On some densities in the set of permutations
• The fractional metric dimension of permutation graphs
• Domination ratio of a family of integer distance digraphs with arbitrary degree
• Domination ratio of integer distance digraphs
• scientific article; zbMATH DE number 1151857
• A bound for s-distance permutation families and explicit Ramsey graphs
• The ratio monotonicity of the \(q\)-derangement numbers
• Density theorems for bipartite graphs and related Ramsey-type results
• Perfect graphs of fixed density: counting and homogeneous sets
• scientific article; zbMATH DE number 1151848

Cites work

• Introduction to Random Graphs
• Perfect matchings and derangements on graphs
• The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph

Cited in

(2)

• Generating infinite digraphs by derangements
• Deranged Matchings: Proofs and Conjectures

This page was built for publication: The set of ratios of derangements to permutations in digraphs is dense in \([0,1/2]\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073299)