Permutations with restricted movement

Abstract

A restricted permutation of a locally finite directed graph $G=(V,E)$ is a vertex permutation $\pi :V\to V$ for which $(v,\pi (v))\in E$, for any vertex $v\in V$. The set of such permutations, denoted by $\Omega (G)$, with a group action induced from a subset of graph isomorphisms form a topological dynamical system. We focus on the particular case presented by Schmidt and Strasser (2016) of restricted ${\mathbb{Z}}^d$ permutations, in which $\Omega (G)$ is a subshift of finite type. We show a correspondence between restricted permutations and perfect matchings (also known as dimer coverings). We use this correspondence in order to investigate and compute the topological entropy in a class of cases of restricted ${\mathbb{Z}}^d$-permutations. We discuss the global and local admissibility of patterns, in the context of restricted ${\mathbb{Z}}^d$-permutations. Finally, we review the related models of injective and surjective restricted functions.

To be published in Discrete and Continuous Dynamical Systems Journal