Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 13 (2008) > Paper 4 open journal systems 


Threshold phenomena on product spaces: BKKKL revisited (once more)

Raphaël Rossignol, Université Paris 11, France


Abstract
We revisit the work of Bourgain et al. (1992) -- referred to as ``BKKKL'' in the title -- about influences on Boolean functions in order to give a precise statement of threshold phenomenon on the product space {1,...,r}N, generalizing one of the main results of Talagrand (1994).


Full text: PDF

Pages: 35-44

Published on: January 19, 2008


Bibliography
  1. Benaim, Michel; Rossignol, Raphaël. Exponential concentration for First Passage Percolation through modified Poincaré inequalities. To appear in Annales de l'IHP. arXiv.org:math.PR/0609730
  2. Bollobás, Béla; Riordan, Oliver. The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields 136 (2006), no. 3, 417--468. MR2257131
  3. Bollobás, Béla; Riordan, Oliver. The critical probability for random Voronoi percolation in the plane is 1/2. Probab. Theory Related Fields 136 (2006), no. 3, 417--468. MR2257131
  4. Bollobás, Béla; Riordan, Oliver. Sharp thresholds and percolation in the plane. Random Structures Algorithms 29 (2006), no. 4, 524--548. MR2268234 (2007h:60089)
  5. Bollobás, Béla; Riordan, Oliver. A short proof of the Harris-Kesten theorem. Bulletin of the London Mathematical Society 38 (2006), no. 3, 470--484. MR2239042
  6. Bourbaki, Nicolas. Eléments de mathématique. IX. Première partie: Les structures fondamentales de l'analyse. Livre IV: Fonctions d'une variable réelle (théorie élémentaire). Chapitre I: Dérivées. Chapitre II: Primitives et intégrales. Chapitre III: Fonctions élémentaires}. Actualités Sci. Ind., (1949), no. 1074. Hermann et Cie., Paris. MR0031013
  7. Bourgain, Jean; Kahn, Jeff; Kalai, Gil; Katznelson, Yitzhak; Linial, Nathan. The influence of variables in product spaces. Israel J. Math. 77 (1992), no. 1-2, 55--64. MR1194785 (94g:05091)
  8. Falik, Dvir; Samorodnitsky, Alex. Edge-isoperimetric inequalities and influences. Combin. Probab. Comput. 16 (2007), no. 5, 693--712. MR2346808
  9. Friedgut, Ehud. Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput. 13 (2004), no. 1, 17--29. MR2034300 (2004m:06021)
  10. Friedgut, Ehud; Kalai, Gil. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993--3002. MR1371123 (97e:05172)
  11. Grimmett, Geoffrey. Percolation.Second edition.Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339 (2001a:60114)
  12. Hatami, H. (2006). Influences and decision trees. arXiv.org:math/0612405.
  13. Kahn, Jeff; Kalai, Gil; Linial, Nathan. The influence of variables on Boolean functions. In Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., (1988), pages 68--80. IEEE, Washington.
  14. Margulis, G. A. Probabilistic characteristics of graphs with large connectivity.(Russian) Problemy Peredav ci Informacii 10 (1974), no. 2, 101--108. MR0472604 (57 #12300)
  15. Paroissin, C. and Ycart, B. (2003). Zero-one law for the non-availability of multistate repairable systems. Int. J. of Reliability, Quality and Safety Engineering, 10(3):311--322.
  16. Rossignol, Raphaël. Threshold for monotone symmetric properties through a logarithmic Sobolev inequality. Ann. Probab. 34 (2006), no. 5, 1707--1725. MR2271478 (Review)
  17. Russo, Lucio. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129--139. MR0671248 (84e:60153)
  18. Talagrand, Michel. On Russo's approximate zero-one law. Ann. Probab. 22 (1994), no. 3, 1576--1587. MR1303654
  19. van den Berg, Rob. Approximate zero-one laws and sharpness of the percolation transition in a class of models including 2d Ising percolation. To appear in Ann. Probab. arXiv.org:0707.2077.
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X