A probability measure μ on the subsets of the edge set of a graph G is a 1-independent probability measure (1-ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1-ipm μ , denote by G μ the associated random graph model. Let ℳ 1 , ⩾ p ( G ) denote the collection of 1-ipms μ on G for which each edge is included in G μ with probability at least p. For G = Z 2 , Balister and Bollobás asked for the value of the least p ⋆ such that for all p > p ⋆ and all μ ∈ ℳ 1 , ⩾ p ( G ) , G μ almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p ⋆. We also determine the 1-independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f 1, G (p), the infimum over all μ ∈ ℳ 1 , ⩾ p ( G ) of the probability that G μ is connected. We determine f 1, G (p) exactly when G is a path, a complete graph and a cycle of length at most 5.

Faculty of Informatics Masaryk University Brno Czech Republic

Institutionen för Matematik och Matematisk Statistik Umeå Universitet Umeå Sweden

Zobrazit více v PubMed

Aaronson J., Gilat D., Keane M., and de Valk V., An algebraic construction of a class of one‐dependent processes, Ann. Probability 17 (1989), 128–143.

Bálint A., Beffara V., and Tassion V., On the critical value function in the divide and color model, Latin Am. J. Prob. Math. Stat. 10 (2013), 653–666.

P. Balister and B. Bollobás, Percolation in the k‐nearest neighbor graph In Recent Results in Designs and Graphs: A Tribute to Lucia Gionfriddo, Quaderni di Matematica, vol. 28.

Balister P. and Bollobás B., Critical probabilities of 1‐independent percolation models, Combin. Prob. Comput. 21 (2012), 11–22.

Balister P., Bollobas B., Sarkar A., and Kumar S., Reliable density estimates for coverage and connectivity in thin strips of finite length In Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking (pp. 75–86). New York: ACM, 2007.

Balister P., Bollobas B., and Stacey A., Upper bounds for the critical probability of oriented percolation in two dimensions In Proc. R. Soc. Lond. A (pp. 201–220), vol. 440: The Royal Society, 1993.

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

Balister P., Bollobás B., and Walters M., Random transceiver networks, Adv. Appl. Probab. 41 (2009), 323–343.

Ball N., Rigorous confidence intervals on critical thresholds in 3 dimensions, J. Stat. Phys. 156 (2014), 574–585.

Benjamini I. and Stauffer A., Perturbing the hexagonal circle packing: a percolation perspective In Annales de l'Institut Henri Poincaré, Probabilités et Statistiques (pp. 1141–1157), vol. 49: Institut Henri Poincaré, 2013.

Bollobás B. and Riordan O., Percolation. Cambridge University Press, Cambridge, 2006.

Bondy A., Shen J., Thomassé S., and Thomassen C., Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121–131.

Burton R.M., Goulet M., and Meester R., On 1‐dependent processes and k‐block factors, Ann. Probab. 21 (1993), 2157–2168.

Deijfen M., Häggström O., and Holroyd A.E., Percolation in invariant Poisson graphs with iid degrees, Arkiv Mate. 50 (2012), 41–58.

Deijfen M., Holroyd A.E., and Peres Y., Stable Poisson graphs in one dimension, Electronic J. Probab. 16 (2011), 1238–1253.

V. Falgas‐Ravry (2012). Thresholds in probabilistic and extremal combinatorics, PhD thesis. University of London, London.

Grimmett G.R., Percolation. Springer, Berlin, vol. 321, 1999.

Grünbaum B. and Shephard G.C., Tilings and patterns. W. H. Freeman & Co., 1987.

Haenggi M. and Sarkar A., Percolation in the secrecy graph, Discrete Appl. Math. 161 (2013), 2120–2132.

Harris T.E., A lower bound for the critical probability in a certain percolation process, Math. Proc. Camb. Philos. Soc. 56 (1960), 13–20.

A. E. Holroyd and T. M. Liggett, Finitely dependent coloring In Forum of Mathematics, Pi, vol. 4 Cambridge: Cambridge University Press, (2016).

Janson S., Runs in m‐dependent sequences, Annals Probab. (1984), 805–818.

Kesten H., The critical probability of bond percolation on the square lattice equals 1/2, Commun. Math. Phys. 74 (1980), 41–59.

Liggett T.M., Schonmann R.H., and Stacey A.M., Domination by product measures, Ann. Probab. 25 (1997), 71–95.

Lyons R., Random walks and percolation on trees, Ann. Probab. (1990), 931–958.

Mathieu P. and Temmel C., K‐independent percolation on trees, Stochastic Processes Appl. 122 (2012), 1129–1153.

Meester R. and Roy R., Continuum percolation. Cambridge Univ. Press, Cambridge, vol. 119, 1996.

Pfender F., Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), 483–495.

Riordan O. and Walters M., Rigorous confidence intervals for critical probabilities, Phys. Rev. E 76 (2007), 011110. PubMed

Scott A.D. and Sokal A.D., The repulsive lattice gas, the independent‐set polynomial, and the Lovász local lemma, J. Stat. Phys. 118 (2005), 1151–1261.

Scott A.D. and Sokal A.D., On dependency graphs and the lattice gas, Combin. Prob. Comput. 15 (2006), 253–279.

Suding P.N. and Ziff R.M., Site percolation thresholds for Archimedean lattices, Phys. Rev. E 60 (1999), 275–283. PubMed

van den Berg J. and Ermakov A., A new lower bound for the critical probability of site percolation on the square lattice, Random Structures Algorithms 8 (1996), 199–212.

Wierman J.C., Substitution method critical probability bounds for the square lattice site percolation model, Combin. Prob. Comput. 4 (1995), 181–188.