Perturbing the hexagonal circle packing: a percolation perspective

Benjamini, Itai; Stauffer, Alexandre

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013) no. 4, pp. 1141-1157.

Nous considérons une juxtaposition hexagonale de cercles de rayon $1/2$ et nous la perturbons en laissant les cercles évoluer comme des mouvements browniens indépendants pendant un temps $t$. Nous montrons que, pour $t$ suffisamment grand, si ${𝛱}_t$ est le processus de points donné par les centres des cercles au temps $t$, alors quand $t\to \infty$, le rayon critique pour que les cercles centrés en ${𝛱}_t$ contienne une composante infinie converge vers celui de la percolation continue (qui est strictement plus grand que $1/2$ comme l’ont montré Balister, Bollobás et Walters). D’un autre coté, pour $t$ suffisamment petit, nous montrons (à l’aide d’une estimation de Monte Carlo pour une intégrale de grande dimension) que l’union des cercles contient une composante infinie. Nous discutons aussi des généralisations et des problèmes ouverts.

We consider the hexagonal circle packing with radius $1/2$ and perturb it by letting the circles move as independent Brownian motions for time $t$. It is shown that, for large enough $t$, if ${𝛱}_t$ is the point process given by the center of the circles at time $t$, then, as $t\to \infty$, the critical radius for circles centered at ${𝛱}_t$ to contain an infinite component converges to that of continuum percolation (which was shown - based on a Monte Carlo estimate - by Balister, Bollobás and Walters to be strictly bigger than $1/2$). On the other hand, for small enough $t$, we show (using a Monte Carlo estimate for a fixed but high dimensional integral) that the union of the circles contains an infinite connected component. We discuss some extensions and open problems.

[1] N. Alon and J. H. Spencer. The Probabilistic Method, 3rd edition. Wiley, Hoboken, NJ, 2008. | MR

[2] P. Balister, B. Bollobás and M. Walters. Continuum percolation with steps in the square or the disc. Random Structures Algorithms 26 (2005) 392-403. | MR

[3] B. Bollobás and O. Riordan. Percolation. Cambridge Univ. Press, Cambridge, UK, 2006. | MR

[4] J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups, 3rd edition. Springer, New York, 1999. | MR

[5] G. Grimmett. Percolation, 2nd edition. Springer, Berlin, 1999. | MR

[6] J. B. Hough, M. Krishnapur, Y. Peres and B. Virág. Zeros of Gaussian Analytic Functions and Determinantal Point Processes. Am. Math. Soc., Providence, 2009. | MR

[7] T. M. Liggett, R. H. Schonmann and A. M. Stacey. Domination by product measures. Ann. Probab. 25 (1997) 71-95. | MR

[8] M. Matsumoto and T. Nishimura. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simulation 8 (1998) 3-30.

[9] R. Meester and R. Roy. Continuum Percolation. Cambridge Univ. Press, Cambridge, UK, 1996. | MR

[10] P. Mörters and Y. Peres. Brownian Motion. Cambridge Univ. Press, New York, NY, 2010. | MR

[11] M. Penrose. Random Geometric Graphs. Oxford Univ. Press, New York, NY, 2003. | MR

[12] M. Penrose and A. Pisztora. Large deviations for discrete and continuous percolation. Adv. Appl. Probab. 28 (1996) 29-52. | MR

[13] Y. Peres, A. Sinclair, P. Sousi and A. Stauffer. Mobile geometric graphs: Detection, coverage and percolation. In Proceedings of the 22st ACM-SIAM Symposium on Discrete Algorithms (SODA) 412-428. SIAM, Philadelphia, PA, 2011. | MR

[14] A. Sinclair and A. Stauffer. Mobile geometric graphs, and detection and communication problems in mobile wireless networks. Preprint, 2010. Available at arXiv:1005.1117v2.

[15] A. Stauffer. Space-time percolation and detection by mobile nodes. Preprint, 2011. Available at arXiv:1108.6322v2.