Проблемы Эрдеша-Секереша в комбинаторной геометрии

• Автор: Кошелев, Виталий Анатольевич
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 105 с. : ил.

Оглавление

Глава 1 Введение и история задачи

1.1 Первая проблема Эрдеша-Секереша

1.2 Вторая проблема Эрдеша-Секереша

1.3 Третья проблема типа Эрдеша-Секереша и величина к(п,к)

1.4 Четвертая проблема типа Эрдеша-Секереша

1.5 Многомерные обобщения

1.6 Введение в классификацию точечных множеств на плоскости

1.7 Новые результаты

Глава 2 Доказательство теоремы

2.1 Вспомогательные определения и обозначения

2.1.1 Сектора и запрещенные зоны
2.1.2 Расстановки
2.2 Основная часть доказательства: неисключительные случаи
2.2.1 "Тривиальные" случаи
2.2.2 Случаи с,] = 0(1<1<5)
2.2.3 Случаи с одной внутренней точкой
2.2.4 Случаи, основанные на применении минимальности восьмиугольника
2.2.5 Случаи с предельным применением минимальности восьмиугольника
2.2.6 Индивидуальные случаи
2.3 Основная часть доказательства: исключительные случаи
2.3.1 Конфигурации вида (8,7,3)
2.3.2 Конфигурации вида (8,6,2)
2.3.3 Конфигурации вида (8,6,1)
2.3.4 Конфигурации вида (8,5,1)
Глава 3 Доказательство теоремы
3.1 "Тривиальные" случаи
3.2 Случаи с 3 <
3.3 Случаи с применением минимальности семиугольника
3.4 Индивидуальные случаи

3.5 Некоторые замечания
Глава 4 Теоремы о внутренних точках
4.1 Доказательство теоремы
4.2 Доказательство теоремы
4.3 Доказательство теоремы
4.4 Доказательство теоремы
Глава 5 Сравнения
5.1 Доказательство теоремы
5.2 Доказательство теоремы

Глава
Введение и история задачи
1.1 Первая проблема Эрдеша-Секереша
Настоящая работа посвящена решению ряда рамсеевских задач в комбинаторной геометрии.
В 1935 году Г1. Эрдеш и Д. Секереш сформулировали следующую проблему (см. [1], [2]).
Первая проблема Эрдеша—Секереша. Для любого целого п > 3 найти минимальное положительное число д(п), такое, что из любого множества точек на плоскости, находягцегося в общем положении и содержащего по крайней мере д(п) точек, можно выбрать подмножество мошщости п, элементы которого являются вершинами выпуклого п-уголъпика.
Напомним, что множество точек находится в общем положении, если никакие три его элемента не лежат на одной прямой.
Рисунок 1.1: Любое множество из пяти точек содержит выпуклый четырехугольник
Первые результаты по этой задаче были получены Эрдешом и Секерешом в статье [1]. Они доказали существование д(п) для произвольного п, обосновав верхнюю оценку д{п) < (Д) + 1, а также высказали следующую гипотезу:
д(п) =? 2п~2 + 1. (1.1)
Эта гипотеза подтверждена для п < 6. Здесь случай д(3) = 3 очевиден; равенство д(4) = 5 было доказано Э. Кляйн в 1935 году (см. рис. 1.1, на котором изображены все три принципиально различных способа расположения

покрывающие плоскость вокруг четырехугольника ABCD. Далее, при необходимости два последних сектора можно заменить на (CR'D) и {AP'D) в соответствии с логикой из предыдущего пункта (см. рис. 2.17). При этом вполне может статься, что R! = Р или что Р' = R. Таким образом, при любом раскладе получается покрытие плоскости вокруг четырехугольника ABCD двумя 3-секторами и двумя 4-секторами с надлежащими ограничениями числа вершин восьмиугольника в каждом из них (см. рис. 2.17).
Во второй ситуации имеем другой набор секторов:
(.APQB), (BQC), {CQRD), (APD).
Как и прежде, можно при необходимости заменить сектор (APD) сектором (AP'D) (или сектором {ARD), если R € APD) и снова получить нужное покрытие.
В обеих ситуациях применяем логику из пункта (8,4,1) и находим выпуклый и пустой шестиугольник в данной конфигурации.
Заметим, что в обеих ситуациях, которые мы только что рассмотрели, используется одинаковое количество 3- и 4-секторов. Аналогичная картина будет наблюдаться и в дальнейшем.
Конфигурации вида (8, 5, > 3)
Рисунок 2.18: Конфигурации вида (8, 5,> 3)
Зафиксируем четыре последовательные вершины '-угольника Р — ]/{, <5 = 2, Л = И Й = р4 (здесь Р = в, если ] — 3). Обозначим через Трд множество Т{, через 7дЛ множество 7, а через Тр3 множество 7Д
Согласно утверждению 2' при £ = 2, если |7д| < 1, |7дД| < 1 или |7д5| < 1, то в конфигурации есть выпуклый и пустой шестиугольник, и все в порядке. Таким образом, остается рассмотреть случай Трд > 1, Рдр > 1,
ітць ' "