Permutations with restricted movement

2020/01/01 by Elimelech, Dor
#Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics

paper · doi:10.48550/arxiv.2001.00274

Abstract

A restricted permutation of a locally finite directed graph G=(V,E) is a vertex permutation π: V→ V for which (v,π(v))∈ E, for any vertex v∈ V. The set of such permutations, denoted by Ω(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 ℤ^d permutations, in which Ω(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 ℤ^d-permutations. We discuss the global and local admissibility of patterns, in the context of restricted ℤ^d-permutations. Finally, we review the related models of injective and surjective restricted functions.

Related

• Master's thesis: Permutations With Restricted Movement
• Permutations of ℤ^d with restricted movement
• On intransitive graph-restrictive permutation groups
• Graph subshifts
• Puzzles of Quasi-Finite Type, Zeta Functions and Symbolic Dynamics for Multi-Dimensional Maps