Concentration of measure and isoperimetric inequalities in product spaces
Publications Mathématiques de l'IHÉS, Tome 81 (1995), pp. 73-205. 
@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},
     pages = {73--205},
     publisher = {Institut des Hautes \'Etudes Scientifiques},
     volume = {81},
     year = {1995},
     mrnumber = {1361756},
     zbl = {0864.60013},
     language = {fr},
     url = {http://www.numdam.org/item/PMIHES_1995__81__73_0/}
}
TY  - JOUR
AU  - Talagrand, Michel
TI  - Concentration of measure and isoperimetric inequalities in product spaces
JO  - Publications Mathématiques de l'IHÉS
PY  - 1995
SP  - 73
EP  - 205
VL  - 81
PB  - Institut des Hautes Études Scientifiques
UR  - http://www.numdam.org/item/PMIHES_1995__81__73_0/
LA  - fr
ID  - PMIHES_1995__81__73_0
ER  - 
%0 Journal Article
%A Talagrand, Michel
%T Concentration of measure and isoperimetric inequalities in product spaces
%J Publications Mathématiques de l'IHÉS
%D 1995
%P 73-205
%V 81
%I Institut des Hautes Études Scientifiques
%U http://www.numdam.org/item/PMIHES_1995__81__73_0/
%G fr
%F PMIHES_1995__81__73_0
Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'IHÉS, Tome 81 (1995), pp. 73-205. http://www.numdam.org/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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

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

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

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

[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

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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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