| Предисловие | 5
|
| Глава 1. Обобщенная схема размещения и компоненты случайных графов | 9
|
| 1.1. Вероятностный подход к перечислительным задачам комбинаторики | 9
|
| 1.2. Обобщенная схема размещения | 25
|
| 1.3. Связность графов и обобщенная схема размещения | 34
|
| 1.4. Леса из некорневых деревьев | 43
|
| 1.5. Размеры деревьев в случайном лесе | 55
|
| 1.6. Максимальный размер деревьев в случайном лесе | 62
|
| 1.7. Графы с одноцикловыми компонентами | 73
|
| 1.8. Графы с компонентами двух типов | 85
|
| 1.9. Замечания и литературные ссылки | 102
|
| Глава 2. Эволюция случайных графов | 108
|
| 2.1. Докритические графы | 108
|
| 2.2. Критические графы | 114
|
| 2.3. Случайные графы с независимыми ребрами | 119
|
| 2.4. Неравновероятные графы | 128
|
| 2.5. Замечания и литературные ссылки | 140
|
| Глава 3. Системы случайных линейных уравнений в GF(2) | 143
|
| 3.1. Ранг матрицы и критические наборы | 143
|
| 3.2. Матрицы с независимыми элементами | 148
|
| 3.3. Ранг матрицы с малым числом единиц | 156
|
| 3.4. Циклы и совместность систем случайных уравнений | 165
|
| 3.5. Гиперциклы и совместность систем случайных уравнений | 178
|
| 3.6. Замечания и литературные ссылки | 187
|
| Глава 4. Случайные подстановки | 195
|
| 4.1. Случайные подстановки и обобщенная схема размещения | 195
|
| 4.2. Число циклов | 197
|
| 4.3. Подстановки с ограничениями на длины циклов | 207
|
| 4.4. Замечания и литературные ссылки | 211
|
| Глава 5. Уравнения, содержащие неизвестную подстановку | 220
|
| 5.1. Уравнения второй степени | 220
|
| 5.2. Уравнения простой степени | 226
|
| 5.3. Уравнения составной степени | 237
|
| 5.4. Замечания и литературные ссылки | 241
|
| Литература | 244
|
| Предметный указатель | 253
|
Колчин Валентин Федорович
Доктор физико-математических наук, действительный член Академии криптографии РФ. Окончил механико-математический факультет МГУ и аспирантуру Математического института имени В. А. Стеклова АН СССР, в котором работал с 1961 г. Был заместителем главного редактора журнала «Математические заметки», членом редколлегии журнала «Random structures and algorithms». Организовал журнал «Дискретная математика»; заместитель главного редактора, а в 2004–2013 гг. — главный редактор. Организатор Петрозаводских конференций по вероятностным методам в дискретной математике; активно участвовал в создании и организации работы Института прикладных математических исследований Карельского научного центра РАН.
В. Ф. Колчин — признанный специалист по теории случайных размещений, случайных графов и системам случайных уравнений над конечными полями; автор работ по теории случайных размещений частиц по ячейкам, случайным подстановкам и отображениям, системам дискретных уравнений, локальным предельным теоремам для сумм случайных величин. Он разработал эффективный метод доказательства предельных теорем в комбинаторных схемах, основанный на представлении изучаемых распределений как условных распределений сумм независимых случайных величин. Автор около 40 статей и трех монографий.
