×

Neighborhood growth dynamics on the Hamming plane. (English) Zbl 1373.05092

Summary: We initiate the study of general neighborhood growth dynamics on two-dimensional Hamming graphs. The decision to add a point is made by counting the currently occupied points on the horizontal and the vertical line through it, and checking whether the pair of counts lies outside a fixed Young diagram. We focus on two related extremal quantities. The first is the size of the smallest set that eventually occupies the entire plane. The second is the minimum of an energy-entropy functional that comes from the scaling of the probability of eventual full occupation versus the density of the initial product measure within a rectangle. We demonstrate the existence of this scaling and study these quantities for large Young diagrams.

MSC:

05C35 Extremal problems in graph theory
05E10 Combinatorial aspects of representation theory
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
82B05 Classical equilibrium statistical mechanics (general)

References:

[1] M. Aizenman and J. L. Lebowitz. Metastability effects in bootstrap percolation. J. Phys. A, 21:3801-3813, 1988. · Zbl 0656.60106
[2] J. Balogh and B. Bollob´as. Bootstrap percolation on the hypercube. Probab. Theory and Related Fields, 134:624-648, 2006. · Zbl 1087.60068
[3] P. N. Balister, B. Bollob´as, J. D. Lee, and B. P. Narayanan.Line percolation. arXiv:1403.6851
[4] J. Balogh, B. Bollob´as, H. Duminil-Copin, and R. Morris. The sharp threshold for bootstrap percolation in all dimensions. Trans. Amer. Math. Soc., 364:2667-2701, 2012. · Zbl 1238.60108
[5] J. Balogh, B. Bollob´as, and R. Morris. Bootstrap percolation in high dimensions. Combin. Probab. Comput., 19:643-692, 2010. · Zbl 1263.60082
[6] J. Balogh, B. Bollob´as, R. Morris, and O. Riordan. Linear algebra and bootstrap percolation. J. Combin. Theory Ser. A , 119:1328-1335, 2012. · Zbl 1242.05190
[7] B. Bollob´as, H. Duminil-Copin, R. Morris, and P. Smith. The sharp threshold for the Duarte model. Ann. Probab., to appear.arXiv:1603.05237 · Zbl 1454.60141
[8] J. Balogh and G. Pete. Random disease on the square grid. Random Structures Algorithms, 13:409-422, 1998. · Zbl 0964.60006
[9] F. Benevides and M. Przykucki.Maximum percolation time in two-dimensional bootstrap percolation. SIAM J. Discrete Math., 29:224-251, 2015. · Zbl 1371.60169
[10] T. Chan, G. Gordon, and J. E. Paguyo. Neighborhood growth on the Hamming plane: bounds on extremal quantities. REU project, UC Davis, 2016.
[11] J. Chalupa, P. L. Leath, and G. R. Reich. Bootstrap percolation on a Bethe lattice. J. Phys. C, 12:L31-L35, 1979.
[12] J. Gravner. Growth phenomena in cellular automata. In Encyclopedia of Complexity and Systems Science (R. A. Meyers, ed.), entry 95, pages 1-22, Springer-Verlag, New York, 2009.
[13] J. Gravner and D. Griffeath. First passage times for the threshold growth dynamics on Z2. Ann. Probab., 24:1752-1778, 1996. · Zbl 0872.60077
[14] J. Gravner and D. Griffeath. Nucleation parameters in discrete threshold growth dynamics. Exp. Math., 6:207-220, 1997. · Zbl 0899.60085
[15] J. Gravner, C. Hoffman, J. Pfeiffer, and D. Sivakoff. Bootstrap percolation on the Hamming torus. Ann. Appl. Probab., 25:287-323, 2015. · Zbl 1308.60109
[16] A. E. Holroyd. Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory and Related Fields, 125:195-224, 2003. · Zbl 1042.60065
[17] S. Janson, T. Luczak, A. Ruci´nski. Random Graphs. John Wiley & Sons, Hoboken, NJ, 2000. the electronic journal of combinatorics 24(4) (2017), #P4.2954 · Zbl 0968.05003
[18] R. Morris. Minimal percolating sets in bootstrap percolation. Electron. J. Combin. 16(1), #R2, 2009. · Zbl 1178.60070
[19] N. Morrison and J. A. Noel.Extremal bounds for bootstrap percolation in the hypercube.arXiv:1506.04686 · Zbl 1378.05204
[20] F. Petrov. Limit shapes of Young diagrams. Two elementary approaches. J. Math. Sci. (N.Y.), 166:63-74, 2010. · Zbl 1288.60009
[21] E. Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation. Electron. J. Combin., 17, #R80, 2010. · Zbl 1228.60114
[22] E. Riedl. Largest and smallest minimal percolating sets in trees. Electron. J. Combin., 19(1), #P64, 2012. · Zbl 1244.05062
[23] D. Romik. The Surprising Mathematics of Longest Increasing Subsequences. Cambridge University Press, New York, 2015. · Zbl 1345.05003
[24] D. Sivakoff. Random site subgraphs of the d-dimensional Hamming torus. Combin. Probab. Comput., 23:290-315, 2014. · Zbl 1290.05133
[25] E. Slivken.Low threshold bootstrap percolation on the Hamming torus. arXiv:1407.2317
[26] A. M. Vershik. Statistical mechanics of combinatorial partitions, and their limit shapes. Funct. Anal. Appl. 30:90-105, 1996. · Zbl 0868.05004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.