Concentration of measure and isoperimetric inequalities in product spaces
Talagrand, Michel
Publications Mathématiques de l'IHÉS, Tome 82 (1995), p. 73-205 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{PMIHES_1995__81__73_0,
     author = {Talagrand, Michel},
     title = {Concentration of measure and isoperimetric inequalities in product spaces},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     volume = {82},
     year = {1995},
     pages = {73-205},
     mrnumber = {97h:60016},
     zbl = {0864.60013},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/PMIHES_1995__81__73_0}
}

Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'IHÉS, Tome 82 (1995) pp. 73-205. http://gdmltest.u-ga.fr/item/PMIHES_1995__81__73_0/

[A-L-R] M. Aizenman, J. L. Lebowitz, D. Ruelle, Some rigorous results on the Sherrington-Kirkpatrick spin glass model, Commun. Math. Phys. 112 (1987), 3-20. | MR 88k:82104a | Zbl 1108.82312

[A-S] N. Alon, J. Spencer, The Probabilistic Method, Wiley, 1991.

[A-M] D. Amir, V. D. Milman, Unconditional and symmetric sets in n-dimensional normed spaces, Israel J. Math. 37 (1980), 3-20. | MR 83b:46016 | Zbl 0445.46011

[B1] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), 49-55. | MR 89i:05244 | Zbl 0666.05033

[B2] B. Bollobás, Random graphs revisited, Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 81-98. | MR 92m:05168 | Zbl 0752.05045

[B-B] B. Bollobás, G. Brightwell, The height of a random partial order : Concentration of Measure, Annals of Applied Probab. 2 (1992), 1009-1018. | MR 94b:06005 | Zbl 0758.06001

[C-L] E. G. Coffman, Jr., G. S. Lucker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, 1991. | Zbl 0759.90043

[C-N] F. Comets, J. Neveu, The Sherrington-Kirkpatrick Model of Spin Classes and Stochastic Calculus : the high temperature case, Comm. Math. Phys. 166 (1995), 549-564. | MR 96d:82035 | Zbl 0811.60098

[D-MS] S. Dilworth, S. Montgomery-Smith, The distribution of vector-valued Rademacher series, Ann. Probab. 21 (1993), 2046-2052. | MR 94i:60027 | Zbl 0798.46006

[F] A. M. Frieze, On the length of the longest monotone subsequence in a random permutation, Ann. Appl. Prob. 1 (1991), 301-305. | MR 92e:60020 | Zbl 0738.05002

[G-M] M. Gromov, V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), 843-854. | MR 84k:28012 | Zbl 0522.53039

[Har] L. H. Harper, Optimal numbering and isoperimetric problems on graphs, J. Comb. Theory (1966), 385-395. | MR 34 #91 | Zbl 0158.20802

[H] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. | MR 26 #1908 | Zbl 0127.10602

[J] S. Janson, Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990), 221-290. | MR 93a:60041 | Zbl 0747.05079

[J-S] W. Johnson, G. Schechtman, Remarks on Talagrand's deviation inequality for Rademacher's functions, Lecture Notes in Math. 1470, Springer Verlag, 1991, 72-77. | MR 92m:60017 | Zbl 0753.60024

[Ka] R. M. Karp, An upper bound on the expected cost of an optimal assignment, in Discrete Algorithm and Complexity : Proceedings of the Japan-US joint Seminar, Academic Press, 1987, 1-4. | MR 88k:90128 | Zbl 0639.90066

[K1] H. Kesten, Aspects of first-passage percolation, Ecole d'Eté de Probabilité de Saint-Flour XIV, Lecture Notes in Math. 1180, 125-264, Springer Verlag, 1986, 125-264. | MR 88h:60201 | Zbl 0602.60098

[K2] H. Kesten, On the speed of convergence in first passage percolation, Ann. Applied Probab. 3 (1993), 296-338. | MR 94m:60205 | Zbl 0783.60103

[K-S] R. M. Karp, J. M. Steele, Probabilistic analysis of heuristics, in The Traveling Salesman Problem, John Wiley and Sons, 1985, 181-205. | MR 811473 | Zbl 0582.90100

[Lea] J. Leader, Discrete isoperimetric inequalities, Proceedings of Symposia on Applied Mathematics, Vol. 44, 1991, 57-80. | MR 93j:60010 | Zbl 0744.60013

[L] M. Ledoux, Gaussian randomization and the law of the iterated logarithm in type 2 Banach spaces, Unpublished manuscript, 1985.

[L-T1] M. Ledoux, M. Talagrand, Characterization of the law of the iterated logarithm in Banach spaces, Ann. Probab. 16 (1988), 1242-1264. | MR 89i:60016 | Zbl 0662.60008

[L-T2] M. Ledoux, M. Talagrand, Probability in Banach Spaces, Springer Verlag, 1991. | MR 93c:60001 | Zbl 0748.60004

[Lu] T. Luczak, The chromatic number of Random graphs, Combinatorica 11 (1991), 45-54. | MR 92g:05164 | Zbl 0771.05090

[Mau1] B. Maurey, Construction de suites symétriques, Comptes Rendus Acad. Sci. Paris 288 (1979), 679-681. | MR 80c:46020 | Zbl 0398.46019

[Mau2] B. Maurey, Some deviation inequalities, Geometric and Functional Analysis 1 (1991), 188-197. | MR 92g:60024 | Zbl 0756.60018

[McD] C. Mcdiarmid, On the method of bounded differences, in Survey in Combinatorics (J. Simons, Ed.), London Mathematical Society Lecture Notes, Vol. 141, Cambridge Univ. Press, London/New York, 1989, 148-188. | MR 91e:05077 | Zbl 0712.05012

[M-H] C. Mcdiarmid, Ryan Hayward, Strong concentration for Quicksort, Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992, 414-421. | MR 1173912 | Zbl 0829.68040

[M-S] V. D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Math. 1200, Springer Verlag, 1986. | MR 87m:46038 | Zbl 0606.46013

[Mi1] V. D. Milman, A new proof of the theorem of A. Dvoretzky on sections of convex bodies, Func. Anal. Appl. 5 (1971), 28-37. | MR 45 #2451 | Zbl 0239.46018

[Mi2] V. D. Milman, Asymptotic properties of functions of several variables defined on homogenous spaces, Soviet. Math. Dokl. 12 (1971), 1277-1491. | MR 46 #2703 | Zbl 0236.26009

[Mi3] V. D. Milman, The heritage of P. Lévy in geometrical functional analysis, Astérisque 157/158 (1988), 273-301. | MR 91d:01005 | Zbl 0681.46021

[P] G. Pisier, Probabilistic methods in the geometry of Banach spaces. Probability and Analysis, Varena (Italy) 1985, Lecture Notes in Math. 1206, Springer Verlag, 1986, 167-241. | MR 88d:46032 | Zbl 0606.60008

[R1] W. Rhee, On the fluctuations of the stochastic traveling salesperson problem, Math. of Operation Research 13 (1991), 482-489. | MR 92k:90050 | Zbl 0751.90080

[R2] W. Rhee, A matching problem and subadditive Euclidean functionals, Ann. Applied Probab. 3 (1993), 794-801. | MR 95d:60024 | Zbl 0784.60020

[R3] W. Rhee, On the fluctuations of simple matching, Oper. Res. Letters 16 (1994), 27-32. | MR 95f:60019 | Zbl 0814.90070

[R4] W. Rhee, Inequalities for the Bin Packing Problem III, Optimization 29 (1994), 381-385. | MR 95i:90021 | Zbl 0820.90079

[Ro] J. Rosinski, Remarks on a Strong Exponential Integrability of Vector Valued Random Series and Triangular Arrays, Ann. Probab., to appear. | Zbl 0831.60007

[R-T] W. Rhee, M. Talagrand, A sharp deviation inequality for the stochastic traveling salesman problem Ann. Probab. 17 (1989), 1-8. | MR 89m:60065 | Zbl 0682.68058

[S] G. Schechtman, Levy type inequality for a class of metric spaces, Martingale Theory in Harmonic analysis and Banach spaces, Cleveland 1981, Lecture Note in Math. 939, Springer Verlag, 1981, 211-215. | Zbl 0502.47031

[S-S] E. Shamir, J. Spencer, Sharp concentration of the chromatic number of random graphs Gn,p, Combinatorica 7 (1987), 121-129. | MR 88i:05164 | Zbl 0632.05024

[T1] M. Talagrand, An isoperimetric theorem on the cube and the Kintchine Kahane inequalities, Proc. Amer. Math. Soc. 104 (1988), 905-909. | MR 90h:60016 | Zbl 0691.60015

[T2] M. Talagrand, Isoperimetry and integrability of the sum of independent Banach space valued random variables, Ann. Probab. 17 (1989), 1546-1570. | MR 91e:60054 | Zbl 0692.60016

[T3] M. Talagrand, A new isoperimetric inequality for product measure, and the tails of sums of independent random variables, Geometric and Functional Analysis 1 (1991), 211-223. | MR 92j:60004 | Zbl 0760.60005

[T4] M. Talagrand, A new isoperimetric inequality for product measure, and the concentration of measure phenomenon, Israel Seminar (GAFA), Lecture Notes in Math. 1469, Springer Verlag, 1991, 94-124. | MR 93d:60095 | Zbl 0818.46047

[T5] M. Talagrand, Regularity of infinitely divisible processes, Ann. Probab. 21 (1993), 362-432. | MR 94h:60058 | Zbl 0776.60053

[T6] M. Talagrand, Supremum of some canonical processes, Amer. J. Math. 116 (1994), 295-314. | MR 95g:60052 | Zbl 0798.60040

[T7] M. Talagrand, New concentration inequalities, in preparation. | Zbl 0893.60001

[W] D. W. Walkup, On the expected value of a random assignment problem, SIAM J. Comput. 8 (1979), 440-442. | MR 80e:68176 | Zbl 0413.68062

[Y] V. V. Yurinskii, Exponential bounds for large deviations, Theor. Prob. Appl. 19 (1974), 154-155. | Zbl 0323.60029