Generating infinite digraphs by derangements

DOI10.1093/QMATH/HAAA055MaRDI QIDQ3382302zbMATH OpenOpenAlexFDO

Authors Daniel Horsley, Cheryl E. Praeger, M. N. Iradmusa

Publication date 21 September 2021

Published in The Quarterly Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

fixed-point-free permutationsderangement generation property for a digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)

Abstract: A set $mathcalS$ of derangements (fixed-point-free permutations) of a set $V$ generates a digraph with vertex set $V$ and arcs $(x,x^{s}igma)$ for $xinV$ and $sigmainmathcalS$. We address the problem of characterising those infinite (simple loopless) digraphs which are generated by finite sets of derangements. The case of finite digraphs was addressed in earlier work by the second and third authors. A criterion is given for derangement generation which resembles the criterion given by De Bruijn and ErdH{o}s for vertex colourings of graphs in that the property for an infinite digraph is determined by properties of its finite sub-digraphs. The derangement generation property for a digraph is linked with the existence of a finite $1$-factor cover for an associated bipartite (undirected) graph.

Recommendations

• Derangement action digraphs and graphs
• Properties of generalized derangement graphs
• The set of ratios of derangements to permutations in digraphs is dense in \([0,1/2]\)
• Largest independent sets of certain regular subgraphs of the derangement graph
• On the spectrum of derangement graphs of order a product of three primes

Cited in

(2)

• The territorial raider game and graph derangements
• Derangement action digraphs and graphs

This page was built for publication: Generating infinite digraphs by derangements

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