Alon N., Spenser J. — The probabilistic method :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Alon N., Spenser J. — The probabilistic method

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: The probabilistic method

Авторы: Alon N., Spenser J.

Аннотация:

One of the most powerful and popular tools used in combinatorics is the probabilistic method. Describes current algorithmic techniques, applying both the classical method and the modern tools it uses. Along with a detailed description of the techniques used in probabilistic arguments, it includes basic methods which utilize expectation and variance plus recent applications of martingales and correlation inequalities. Examines discrepancy and random graphs and covers such topics as theoretical computer science, computational geometry, derandomization of randomized algorithms and more. A study of various topics using successful probabilistic techniques is included along with an Open Problems Appendix by Paul Erd?s, the founder of the probabilistic method.

Язык:

Рубрика: Математика/Алгебра/Комбинаторика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: Second edition

Год издания: 2000

Количество страниц: 319

Добавлена в каталог: 12.03.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Margulis      137—138 142
Marica      84
Markov      57 101 162 264 266
Markov chain      162
Martingale      2 vii 93—100 102—104 108—109
Martingale, Doob process      95
Martingale, edge exposure      94—97
Martingale, flip a coin      95
Martingale, inequality      vii 95 101 111
Martingale, vertex exposure      95—96 99
Matousek      226
Matrix, adjacency of a graph      137 139—140 143—144
Matrix, adjacency of a tournament      61
Matrix, Hadamard      207—208
Matula      5—6 52
Maurey      95 99
Mean      35—36 42 44 96 102 105 109—110 115 124 126—127 129 162 164—166 168 201 264 268—270
Mean, geometric      22—24
Meet      83 89
Meir      217—218
Miklos      278
Milman      95 99 137—138
Minc      22 60
Monochromatic      1—3 6—7 16—17 20—21 26 30—33 65 67 69 75—76 199 249—250 254—255 257 276—277
Moon      4 134
Nakayama      70
Naor      257
NC      253—254 256
Nesetfil      278
Newborn      259
Nilli      138
Normal, distribution      19 42 44—45 102 209 267—269 271 276
NP(non-deterministic polynomial time)      184 191 194—195
P(polynomial time)      2
Pach      68 223 226
Packing      29—30 34 36—37 54 229
Packing of       230
Packing, constant      29 229
Packing, greedy      34
Packing, number      37 54
Packing, random      34
Paley      148
Parity function      183 188—190 194 196
Partially ordered set      83 88—90
Paturi      219
Paul      185
Peralta      257
Perles      221
Permanent      22—23 60—61
Peroche      70
Pessimistic estimators      251
Phase transition      161 168
Phillips      138 142
Pinsker      137
Pintz      28—29
Pippenger      54
Pittel      168
Podderyugin      5—6
poisson      35—36 115 119 121 123—124 127—128 156 162 164—166 168 269—270
Primality testing algorithm      141
Prime      9 21 28 42—45 59 72 134 138 141—142 148 189 276
Projective plane      246
Property of graphs      88
Pythagoras      20 216
Quadratic residue character      135
Quasi-random      134
Rabin      141
Radhakrishnan      7 30
Rado      12 277
Radon      222
Raghavan      250—251
Ramachandran      253
Ramanujan      42 139
Ramsey      1 10 16 25—26 37 67 133—134 273 275—277 280
Ramsey theorem      275 277
Ramsey, function      277
Ramsey, graph      133—134
Ramsey, graph, explicit construction      133
Ramsey, number      1 10 25—26 37 67 273 276
Ramsey, theory      16 280
Random process, walk      93 142 150—151
Random variables      4 10—11 13 18—19 21 41—42 44 58—59 93 101 103 106 108 115 117 126—127 146 162 197 237 240 242—243 245 254—257 263—264 270 272
Random variables, almost d-wise independence      257
Random variables, binomial      72 113 124 188 220 224
Random variables, d-wise independence      253—257
Random variables, decomposition      13 42 75
Random variables, entropy      240
Random variables, indicator      4 13—14 26—27 42 48 51 56—57 91 116 119 121 181 197 200 202 220 235—236 246 268—269
Random variables, standard normal      271
Range space      220—223 225—226 228
Razborov      189 191—192

Recoloring      30
Renyi      49 155—156 161 276
Riemann      136 229
Rival      88
Rodl      37 53—54 136 142 219 278
Rodl nibble      53 105
Ronyai      226
Rooted graph      111 174
Roth      126
Rothschild      26
Sands      88
Sarnak      138 142
Sauer      221
Saxe      185
Schechtman      95 99
Schiitte      3 136
Schonheim      84
Schrijver      22
Schwarz      135 139—140 148
Second moment method      41—42 47 53—54 168
Selfridge      250 277
Shamir      96
Shannon      231—233
Shearer      65 242 244 272
Shelah      171 221
Shepp      88
Simon      219
Simonovits      244
Simons      93
Sipser      185
Sloane      255
Smolensky      189
Sorting network      137
Sos      244 278
Spencer      26—27 34 36 54 67 73 96 101 104 117 121 125 134 136 171 201 204 250 260 279
Spencer’s theoren      171
Srinivasan      7 30
Steiner      54
Stirling      19 43 61
Sturtevant      242
Subbotovskaya      194—195
Suen      128—129
Sum-free      8—9
Szabo      226
Szekely      260
Szekeres      4 275 278—279
Szele      2 14 60
Szemeredi      28—29 137 140 259—261 272—273 277
Szonyi      278
Tactical configuration      54
Talagrand      105
Talanov      171
Tanner      137
Tarjan      6
Tetali      127 276
Thomason      142
Threshold function      47—49 120—121 124 129 156—157 171—172 178
Tikhonov’s Theorem      66
Tournament      3—4 11 14 60—63 134—136
Tournament, explicit construction      4 136
Tournament, quadratic residue tournament      134—135 148
Trotter      260
Turan      27—28 42 44 91—92 277
Turan’s Theorem      27—28 91—92
Ullman      2
Valtr      217
Vapnik      221—222
Variance      vii 18 41—42 44 55—56 58—59 101—102 146 188 201 224 267—268 270
VC-dimension      viii 220—225 227
Vector, imbalanced      209
Vertex transitive graph      150—151
Vesztergombi      204
Vizing      194
Vu      110—111
Walk      140—142 144 151
Walk, random      93 142 150—151
Wegener      185
Weierstrass      113
Weil      136 139 148
Welzl      221 223 225—226
Wendel      215
Wernisch      226
Whitney      243
Wigderson      140 185
Wilson      134 136 142
Witness      141—142
Woeginger      223
Wright      170
XYZ-theorem      89
Yao      185
Zero-one laws      171—174 178

1 2

О проекте