Generating Infinite Digraphs by Derangements

Daniel Horsley, Moharram Iradmusa, Cheryl E. Praeger

Research output: Contribution to journalArticleResearchpeer-review

Abstract

A set $\mathcal{S}$ of derangements (fixed-point-free permutations) of a set V generates a digraph with vertex set V and arcs $(x,x^{\,\sigma})$ for x V and $\sigma\in\mathcal{S}$. We address the problem of characterizing those infinite (simple loopless) digraphs which are generated by finite sets of derangements. The case of finite digraphs was addressed in an earlier work by the second and third authors. A criterion is given for derangement generation which resembles the criterion given by De Bruijn and Erdos 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.

Original languageEnglish
Pages (from-to)961-974
Number of pages14
JournalQuarterly Journal of Mathematics
Volume72
Issue number3
DOIs
Publication statusPublished - 1 Sep 2021

Cite this