Permutations with restricted movement

Dor Elimelech

doi:10.3934/dcds.2021038

Article Contents

2021, Volume 41, Issue 9: 4319-4349. Doi: 10.3934/dcds.2021038

This issue Previous Article Supercritical elliptic problems involving a Cordes like operator Next Article PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video

Permutations with restricted movement

Dor Elimelech

School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Israel

Received: December 31, 2019

Revised: September 30, 2020

Early access: March 2021

Published: September 2021

This work was supported by the Israel Science Foundation (ISF) under grant No. 270/18 and 1052/18

Abstract Full Text(HTML) Figure(11) Related Papers Cited by

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 [18] 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.

Keywords:

Mathematics Subject Classification: Primary: 37B50,; Secondary: 37B05, 37B40.

Citation:

Full Text(HTML)

Figure 2.1. (a) The two-dimensional honeycomb lattice. (b) The fundamental domain

Download: Full-size image PowerPoint slide

Figure 2.2. (a) Paths configuration corresponding to an elements in $ \Omega(G_{A_L}) $. (b) Paths configuration corresponding to an elements in $ \Omega(G_{A_+}) $

Download: Full-size image PowerPoint slide

Figure 2.3. The graphs corresponding to $ A_+ $ and $ A_L $

Download: Full-size image PowerPoint slide

Figure 3.1. The graph $ G_{A_L}' $

Download: Full-size image PowerPoint slide

Figure 3.2. The quotient of $ L_{H} $ by the action of $ (2 {\mathbb Z})^2 $

Download: Full-size image PowerPoint slide

Figure 3.3. A correspondence between a function in $ B_{3, 3}(A_L) $ and a perfect cover of $ \hat{V}_{3, 3} $ in $ G_{A_L} $

Download: Full-size image PowerPoint slide

Figure 3.4. (a) The $ T $-gadget and the weights on its edges. (b) The construction of $ \hat{G} $ from $ G $

Download: Full-size image PowerPoint slide

Figure 3.5. The correspondence between a restricted permutation of the honeycomb lattice, perfect matchings and permutations of $ {\mathbb Z}^2 $ restricted by $ A_L $

Download: Full-size image PowerPoint slide

Figure 3.6. The corresponding graph for $ G_{A_+} $ from Theorem 1. Black points represent vertices of the form $ (I, n) $ and white points represent vertices of the form $ (O, n) $

Download: Full-size image PowerPoint slide

Figure 4.1. A locally admissible pattern which is not globally admissible where the restricting set is $ A_+ $

Download: Full-size image PowerPoint slide

Figure 4.2. The extension of $ \pi_v $ to a $ \pi\in \Omega(A_\oplus) $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	N. Chandgotia and T. Meyerovitch, Borel subsystems and ergodic universality for compact $\mathbb{Z}^d$-systems via specification and beyond, preprint, arXiv: 1903.05716.
[2]	H. Cohn, R. Kenyon and J. Propp, A variational principle for domino tilings, J. Amer. Math. Soc., 14 (2001), 297-346. doi: 10.1090/S0894-0347-00-00355-6.
[3]	M. Einsiedler and T. Ward, Ergodic Theory, Springer, 2013. doi: 10.1007/978-0-85729-021-2.
[4]	D. Elimelech, Permutations with Restricted Movement, M.Sc Thesis, Ben-Gurion University, 2019, arXiv: 1911.02233.
[5]	M. E. Fisher, Statistical mechanics of dimers on plane lattice, Phys. Rev., 124 (1961), 1664-1672. doi: 10.1103/PhysRev.124.1664.
[6]	M. E. Fisher, On the dimer solution of planar Ising models, J. of Math. Phys., 7 (1966), 1776-1781. doi: 10.1063/1.1704825.
[7]	M. Hochman and T. Meyerovich, A characterization of the entropies of multidimensional shifts of finite type, Annals of Math., 171 (2010), 2011-2038. doi: 10.4007/annals.2010.171.2011.
[8]	P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica, 27 (1961), 1209-1225.
[9]	P. W. Kasteleyn, Dimer statistics and phase transitions, Journal of Mathematical Physics, 4 (1963), 287-293. doi: 10.1063/1.1703953.
[10]	R. Kenyon, The planar dimer model with boundary: A survey, Directions in Mathematical Quasicrystals, CRM Monogr. Ser., 13 (2000), 307-328.
[11]	R. Kenyon, A. Okounkov and S. Sheffield, Dimers and amoebae, Annals of Math., 163 (2006), 1019-1056. doi: 10.4007/annals.2006.163.1019.
[12]	D. Kerr and H. Li, Entropy and the variational principle for actions of sofic groups, Inventiones Mathematicae, 186 (2011), 501-558. doi: 10.1007/s00222-011-0324-9.
[13]	D. Lind and B. H. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.
[14]	E. Lindenstrauss, Pointwise theorems for amenable groups, Inventiones Mathematicae, 146 (2001), 259-295. doi: 10.1007/s002220100162.
[15]	M. Misiurewicz, A short proof of the variational principle for a $\mathbb{Z}^N$ action on a compact space, Asterisque, 40 (1976), 147-157.
[16]	R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12 (1971), 177-209. doi: 10.1007/BF01418780.
[17]	K. Schmidt, Dynamical Systems of Algebraic Origin, Birkhäuser/Springer Basel AG, Basel, 1995.
[18]	K. Schmidt and G. Strasser, Permutations of $\mathbb{Z}^d$ with restricted movement, Studia Mathematica, 235 (2016), 137-170. doi: 10.4064/sm8498-8-2016.
[19]	M. Schwartz and J. Bruck, Constrained codes as networks of relations, IEEE Trans. Inform. Theory, 54 (2008), 2179-2195. doi: 10.1109/TIT.2008.920245.
[20]	H. N. V. Temperley and M. E. Fisher, Dimer problem in statistical mechanics–an exact result, Phil. Mag., 6 (1960), 1061-1063. doi: 10.1080/14786436108243366.