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

DOI10.37236/10293zbMATH Open1481.05061arXiv2101.02995OpenAlexW3119228984MaRDI QIDQ2073299FDOQ2073299

Authors: Bethany Austhof, Patrick Bennett, Nick Christo 

Publication date: 1 February 2022

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

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]$.

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

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

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

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)

Cites Work

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

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)