Вероятность и алгебра в комбинаторике, Райгородский А.М., 2008

Вероятность и алгебра в комбинаторике, Райгородский А.М., 2008.

   Настоящая брошюра возникла на основе лекций, прочитанных автором на летней математической школе «Современная математика» в Дубне в 2006 г. В ней рассказывается о двух мощных методах современного дискретного анализа — вероятностном и алгебраическом. Оба эти метода широко применяются сейчас для решения различных задач экстремальной комбинаторики. В частности, многие важные аспекты таких классических проблем, как проблема Борсука или проблема отыскания чисел Рамсея, рассматриваются исключительно с позиций вероятностной и алгебраической технологий. В брошюре на наиболее ярких примерах подобных задач излагаются основы методов. Необходимые сведения из (элементарной) теории вероятностей, анализа и алгебры приводятся в конце брошюры в специальном разделе. Брошюра доступна студентам младших курсов и даже школьникам. Однако полезна она может быть всем, кто интересуется комбинаторикой.




Определения и формулировки результатов.
Наука, которую принято называть «теорией Рамсея», начала бурно развиваться еще в первой половине XX в. Нельзя сказать, чтобы сам Рамсей, опубликовавший замечательную и, по существу, эпохальную статью в 1930 г., был именно основателем науки; и до него различные аспекты проблематики не раз рассматривались многими авторами. Все же результат Рамсея явился одной из главных вех в формировании теории. Если говорить совсем общо, теория Рамсея состоит в отыскании «неизбежных закономерностей» внутри хаоса. Чуть более конкретно можно сформулировать основную задачу этой науки следующим образом: требуется доказать, что, как бы мы ни разбили некоторую совокупность объектов на части, найдется часть, содержащая определенную подструктуру. Одна из классических теорем теории Рамсея принадлежит Б. Л. Ван дер Вардену: при любом разбиении натурального ряда на конечное число частей в некоторой части есть сколь угодно длинные арифметические прогрессии (см. [20]). По теории Рамсея имеется обширная литература (см., например, 1,4,21,22), и мы не станем даже пытаться охватить в этой лекции все многообразие «рамсеевских» задач. Нас будет интересовать именно та задача, которую впервые рассмотрел сам Рамсей в своей основополагающей работе 1930 г. Перейдем к ее постановке.

ОГЛАВЛЕНИЕ.
Введение.
Лекция 1. Задачи о пересечениях множеств.
1.1. Постановки задач и формулировки некоторых результатов.
1.2. Доказательство теоремы 1.
1.3. Доказательство теоремы 2.
1.4. Несколько слов об истории задач.
Лекция 2. Проблемы Борсука и Нелсона-Эрдёша-Хадвигера.
2.1. Постановки проблем и формулировки теорем.
2.2. Доказательство теоремы 5.
2.3. Доказательство теоремы 6.
Лекция 3. Числа Рамсея.
3.1. Определения и формулировки результатов.
3.2. Доказательство теоремы 8.
3.3. Доказательство теоремы 9.
3.4. Обсуждение следствий из теорем 8 и 9.
3.5. Обсуждение нижней оценки для R(3, t).
3.6. Явные нижние оценки диагональных чисел Рамсея.
3.7. Доказательство теоремы 10.
Лекция 4. Раскраски гиперграфов.
4.1. Определения и формулировки результатов.
4.2. Доказательство теоремы.
4.3. Доказательство теоремы.
Дополнение.
1. Теория вероятностей.
1.1. Классическое определение вероятности и схема Бернулли.
1.2. Геометрические вероятности и общее понятие вероятностного пространства.
1.3. Независимость случайных величин и событий.
1.4. Распределения случайных величин, моменты, центральная предельная теорема.
2. Линейная алгебра.
3. Теория графов.
4. Анализ.
Литература

Купить .





Теги: учебник по математике :: математика :: Райгородский :: комбинаторика :: схема Бернулли