Generating infinite digraphs by derangements

DOI10.1093/QMATH/HAAA055zbMATH Open1479.05129arXiv1909.03675OpenAlexW3110584669MaRDI QIDQ3382302FDOQ3382302

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)

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.

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

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

zbMATH Keywords

fixed-point-free permutationsderangement generation property for a digraph

Mathematics Subject Classification ID

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

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)