

























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^σ)$ for $x\in V$ and $σ\in\mathcal{S}$. 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 Erdő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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。