American Institute of Mathematical Sciences

Advanced
September  2021, 41(9): 4319-4349. doi: 10.3934/dcds.2021038

Permutations with restricted movement

Dor Elimelech

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

Received  January 2020 Revised  October 2020 Published  September 2021 Early access  March 2021

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

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: Perfect matchings, planner graphs, restricted movement permutations, topological entropy, dynamical systems.
Mathematics Subject Classification: Primary: 37B50,; Secondary: 37B05, 37B40.
Citation: Dor Elimelech. Permutations with restricted movement. Discrete and Continuous Dynamical Systems, 2021, 41 (9) : 4319-4349. doi: 10.3934/dcds.2021038
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.

show all references

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.

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

Download full-size image

Download as 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_+}) $
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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} $
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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 $
Figure Options

Download full-size image

Download as 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) $
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

[1]

Xiaomin Zhou. Relative entropy dimension of topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6631-6642. doi: 10.3934/dcds.2019288
[2]

Yun Zhao, Wen-Chiao Cheng, Chih-Chang Ho. Q-entropy for general topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2059-2075. doi: 10.3934/dcds.2019086
[3]

João Ferreira Alves, Michal Málek. Zeta functions and topological entropy of periodic nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems, 2013, 33 (2) : 465-482. doi: 10.3934/dcds.2013.33.465
[4]

Jakub Šotola. Relationship between Li-Yorke chaos and positive topological sequence entropy in nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5119-5128. doi: 10.3934/dcds.2018225
[5]

Alfredo Marzocchi, Sara Zandonella Necca. Attractors for dynamical systems in topological spaces. Discrete and Continuous Dynamical Systems, 2002, 8 (3) : 585-597. doi: 10.3934/dcds.2002.8.585
[6]

Jérôme Rousseau, Paulo Varandas, Yun Zhao. Entropy formulas for dynamical systems with mistakes. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4391-4407. doi: 10.3934/dcds.2012.32.4391
[7]

Yujun Zhu. Preimage entropy for random dynamical systems. Discrete and Continuous Dynamical Systems, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829
[8]

Karsten Keller. Permutations and the Kolmogorov-Sinai entropy. Discrete and Continuous Dynamical Systems, 2012, 32 (3) : 891-900. doi: 10.3934/dcds.2012.32.891
[9]

Jeremias Epperlein, Stefan Siegmund. Phase-locked trajectories for dynamical systems on graphs. Discrete and Continuous Dynamical Systems - B, 2013, 18 (7) : 1827-1844. doi: 10.3934/dcdsb.2013.18.1827
[10]

Stefan Siegmund, Petr Stehlík. Preface: Special issue on dynamical systems on graphs. Discrete and Continuous Dynamical Systems - B, 2018, 23 (5) : i-iii. doi: 10.3934/dcdsb.201805i
[11]

Chao Ma, Baowei Wang, Jun Wu. Diophantine approximation of the orbits in topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2455-2471. doi: 10.3934/dcds.2019104
[12]

Silvére Gangloff, Alonso Herrera, Cristobal Rojas, Mathieu Sablik. Computability of topological entropy: From general systems to transformations on Cantor sets and the interval. Discrete and Continuous Dynamical Systems, 2020, 40 (7) : 4259-4286. doi: 10.3934/dcds.2020180
[13]

Noriaki Kawaguchi. Topological stability and shadowing of zero-dimensional dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2743-2761. doi: 10.3934/dcds.2019115
[14]

H.T. Banks, S. Dediu, H.K. Nguyen. Sensitivity of dynamical systems to parameters in a convex subset of a topological vector space. Mathematical Biosciences & Engineering, 2007, 4 (3) : 403-430. doi: 10.3934/mbe.2007.4.403
[15]

Katrin Gelfert. Lower bounds for the topological entropy. Discrete and Continuous Dynamical Systems, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555
[16]

Jaume Llibre. Brief survey on the topological entropy. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3363-3374. doi: 10.3934/dcdsb.2015.20.3363
[17]

Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete and Continuous Dynamical Systems, 2016, 36 (7) : 3705-3717. doi: 10.3934/dcds.2016.36.3705
[18]

Xiongping Dai, Yunping Jiang. Distance entropy of dynamical systems on noncompact-phase spaces. Discrete and Continuous Dynamical Systems, 2008, 20 (2) : 313-333. doi: 10.3934/dcds.2008.20.313
[19]

Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122
[20]

Wooyeon Kim, Seonhee Lim. Notes on the values of volume entropy of graphs. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5117-5129. doi: 10.3934/dcds.2020221

2021 Impact Factor: 1.588

Tools

Metrics

  • PDF downloads (156)
  • HTML views (172)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy