Оглавление
Глава 1 Введение и история задачи 4
1.1 Первая проблема Эрдеша-Секереша 4
1.2 Вторая проблема Эрдеша-Секереша 6
1.3 Третья проблема типа Эрдеша-Секереша и величина /г(п, к) . . 7
1.4 Четвертая проблема типа Эрдеша Секереша . 9
1.5 Многомерные обобщения 10
1.6 Введение в классификацию точечных множеств на плоскости . 11
1.7 Новые результаты 14
Глава 2 Доказательство теоремы 1 19
2.1 Вспомогательные определения и обозначения 19
2.1.1 Сектора и запрещенные зоны 19
2.1.2 Расстановки 22
2.2 Основная часть доказательства: неисключительные случаи . . . 27
2.2.1 "Тривиальные" случаи 27
2.2.2 Случаи с і = 0 (1 < і < 5) 27
2.2.3 Случаи с одной внутренней точкой 2.2.4 Случаи, основанные на применении минимальности вось- 30
миугольника 2.2.5 Случаи с предельным применением минимальности вось- . 32
миугольника 38
2.2.6 Индивидуальные случаи 44
2.3 Основная часть доказательства: исключительные случаи . . . . 50
2.3.1 Конфигурации вида (8,7,3) 50
2.3.2 Конфигурации вида (8,6.2) . 55
2.3.3 Конфигурации вида (8,6,1) 59
2.3.4 Конфигурации вида (8,5,1) . 65
Глава 3 Доказательство теоремы 2 70
3.1 "Тривиальные" случаи . 70
3.2 Случаи с 3 < 2 70
3.3 Случаи с применением минимальности семиугольника 76
3.4 Индивидуальные случаи 80
2
3.5 Некоторые замечания.............................................85
Глава 4 Теоремы о внутренних точках 86
4.1 Доказательство теоремы 3.....................................86
4.2 Доказательство теоремы 4.....................................88
4.3 Доказательство теоремы 5.....................................93
4.4 Доказательство теоремы 6.....................................94
Глава 5 Сравнения 97
5.1 Доказательство теоремы 7.....................................97
5.2 Доказательство теоремы 8....................................100
3
Глава 1
Введение и история задачи
1.1 Первая проблема Эрдеша—Секереша
Настоящая работа посвящена решению ряда рамсеевских задач в комбинаторной геометрии.
В 1935 году П. Эрдеш и Д. Секереш сформулировали следующую проблему (см. [1], [2!).
Первая проблема Эрдеша-Секереша. Для любого целого п > 3 найти минимальное полооісигпельпое числю д(п), такое, что из любого множества точек па плоскости, находящегося в общем поло'жеиии и содержащего по крайней мере д(п) точек, можно выбрать подмпооюество мощности п, элементы которого являются вершинами выпуклого п-угольпика.
Напомним, что множество точек находится в общем положении, если никакие три его элемента не лежат на одной прямой.
Рисунок 1.1: Любое множество из пяти точек содержит выпуклый четырехугольник
Первые результаты по этой задаче были получены Эрдешом и Секерешом в статье [1]. Они доказали существование д(п) для произвольного п, обосновав верхнюю оценку д(п) < Н-1, а также высказали следующую гипотезу:
д(п) =? 2п~2 + 1. (1.1)
Эта гипотеза подтверждена для п < 6. Здесь случай д(3) = 3 очевиден; равенство д{А) = о было доказано Э. Кляйн в 1935 году (см. рис. 1.1, на котором изображены все три принципиально различных способа расположения
4
пяти точек на плоскости); выражение д(Ь) = 9 получил Э. Макай (см. [1], [2], [3]); факт д(6) = 17 был установлен сравнительно недавно Д. Секерешом и JT. Питерсом в [4] с помощью достаточно сложного компьютерного перебора. Кроме того, в 1961 году Эрдеш и Секереш доказали и нижнюю оценку д(п) > 2п~2 + 1 (см. [2]).
В связи с проблемой Эрдеша - Секереша очень часто рассматривают выпуклые ломаные, которые были предложены самими авторами задачи в [1] и которые принято называть "чашками” и "крышками". Напомним их определение. Пусть на плоскости дана система координат. Множество точек
(®1і Уі)? • • • : ір'П'. Уп)
называется п-чашкой, если Х\ < ... < хп и
У\ ~ У2 ^ У'2 - 2/з ^ Уп-1 ~ Уп
Ті 3?2 ^2 Х3 Хц— 1
Это МНОЖЄСТВО будет п-крышкой, если Ті < ... < хп и
У і ~ У2 У 2 - Уз Уп-1 - Уп
Х\ Х2 Х2 Х$ ХП—\ Хп
Понятно, что типичная чашка и типичная крышка устроены так, как показано на рисунке 1.2.
Рисунок 1.2: Чашка и крышка
Вслед за величиной д(п) определим величину /(1,т) как минимальное положительное число, такое, что любое множество точек на плоскости X в общем положении, не содержащее пары точек с одинаковыми абсциссами, содержит либо /-чашку, либо т-крышку, коль скоро \Х\ > /(/,т). Несмотря на то, что задача отыскания величины д(п) является достаточно сложной, задача об /(/, т) была полностью решена Эрдешом и Секерешом, которые в |2] установили равенство
Д/,т) = (*+г!?2 4)-+1- (1-2)
5
Более того, для всех / и т им удалось построить пример множества мощности C+™2~4)j не содержащего ни /-чашки, ни га-крышки. Такое множество мы будем обозначать Т(1,т). Оно строится по индукции, при помощи объединения правильно расположенных множеств Т(1 — 1, т) и Т(1, т — 1) (подробно этот процесс мы опишем далее). Из равенства (1.2), в частности, следует верхняя оценка д(п) < /(п,п) < (2П"724) + 1-
Неравенство д(п) < (2nnJ'2l) + 1 неоднократно улучшалось. Так, в 1998 году было получено сразу три последовательных улучшения. Первое из них принадлежит Ф. Чанг и Р. Грэхему: д(п) < (2^_Г24) (см- И)* Второе улучшение получили Д. Клейтмаи и Л. Пахтер: д(п) < (2”J4) +7 — 2п (см. [б)). Наконец, третье улучшение принадлежит Г. Тоту и П. Вальтру: д(п) < (^735) + 2 (см. [7]). В 2005 году Тот и Вальтр слегка усилили последнее неравенство, заменив его оценкой д(п) < (2*_Гз5) + 1 (здесь п > 5; см. [8]), и это наиболее точный на данный момент результат. Тем самым, гипотеза Эрдеша-Секереша (1.1) до сих пор не доказана и не опровергнута, и даже более того, за все время существования задачи никому не удалось понизить асимптотику верхней оценки. В итоге, имеем:
2n“2 -f 1 < д(п) < ^ ^ ^ +1 (1.3)
1.2 Вторая проблема Эрдеша-Секереша
В 1978 году Эрдеш предложил следующую модификацию первой проблемы (см. [9]).
Вторая проблема Эрдеша-Секереша. Для любого целого п > 3 найти минимальное положительное число h(n), такое, что из любого мпо-жсства точек X па плоскости, находящегося о общем положении и содержащего по крайней мере h(n) точек, можно выбрать подмнооісество мощности п, элементы которого являются вершинами выпуклого и пустого п-угольника, то есть этот п-угольник не содержит внутри себя других точек из X.
Эта проблема изучена, в некотором смысле, более глубоко по сравнению с первой. Так, равенства h(3) = 3 и /і(4) = 5 для нее очевидны (ср. рис. 1.1). Выражение /?,(5) = 10 получил X. Харборт в 1978 году (см. [10]). А в 1983 году Дж. Хортон доказал, что 1г(п) не существует при п > 7 (см. |11]). Вопрос о существовании и значении величины h(6) долгое время оставался открытым. Лишь в 2006 году Т. Геркеп доказал существование /і(6), обосновав верхнюю оценку (см. [12]):
К6) < д(9) < (g3) + 1 = 1717. (1.4)
6
Независимо от него, свои доказательства представили К. Николас (см. (13]) и Вальтр (см. [14)); но их верхние оценки хуже и составляют #(25) и #(15) соответственно.
Тривиальная нижняя оценка /і(б) > #(6) > 17 есть следствие одной из теорем Эрдеша-Секереша. Все последующие улучшения нижней оценки для Д(6) были получены компьютерным перебором. Первое из них найдено Д. Раппопортом в 1985 году /ь(6) > 21 (см. [15]), второе принадлежит М. Овер-марсу, В. Шолтен и И. Винсент и относится к 1988 году: 1ь(б) > 27 (см. |1б|), и наконец третье было получено в 2001 году Овермарсом к(0) > 30 (см. [17], см. рис. 1.3). Это самая лучшая нижняя оценка на данный момент.
( 1. 1260)
( 16, 743)
( 22, 531)
( 37, 0)
( 306, 592)
( 310, 531)
( 366, 552)
( 371, 487)
( 374, 525)
{ 392, 575)
( 396, 613)
( 410, 539)
( 416, 550)
( 426, 526)
( 434, 552)
( 436, 535)
( 446, 565)
( 449, 518)
( 450, 498}
( 453, 542)
( 459, 526)
( 489, 537)
( 492, 502)
( 496, 579)
( 516, 467)
( 552, 502)
( 754, 697)
( 777, 194)
(1259, 320)
Рисунок 1.3: Конструкция Овермарса
Зазор между нижней и верхней оценками в неравенстве 30 < /г(0) <1717 крайне велик, и уменьшение его - важная и нетривиальная задача.
1.3 Третья проблема типа Эрдеша-Секереша и величина /г(п, к)
Две предыдущие классические задачи имеют следующее обобщение
Третья проблема типа Эрдеша-Секереша. Для любых целых п > 3 и к > 0 найти минимальное положительное число Н(п, к), такое, что из
7
любого мпоо/сества точек X на плоскости, находящегося в общем полоо/се-нии и содерэ/сащего по крайней мере /г(п, к) точек, моо/сно выбрать подмно-жество мощности п, элементы которого являются вершинами выпуклого п-угольпика С с условием \(С \ дС) П XI < к, то есть этот п-угольник содержит внутри себя не более к других точек из X.
Для этой задачи, как нетрудно видеть, всегда выполнены неравенства
g(n) < h(n,k) < h(n),
если соответствующие выражения существуют. Более того,
h(n) = h(n, 0) > /г(п, 1) > h(n: 2) > ...
Для малых значений п очевидны следующие результаты:
/i(3, /с) = 3, /г(4, к) = 5, Л(5, 0) = 10, Л(5, > 1) = 9.
Последний результат следует из того факта, что выпуклый пятиугольник с двумя или более точками внутри всегда содержит меньший выпуклый пятиугольник. Что касается других точных значений, то здесь ничего более не известно, в том числе нет никаких верхних и нижних оценок, кроме совсем уж очевидных.
При малых значениях к следует ожидать, что. как и в теореме Хортона (см. [11)), /г(п, к) может не существовать. Напротив, если к достаточно велико, то h(n. к) — д(п) (в обоих случаях можно считать, что к на самом деле является функцией от п, то есть к = к{п)). Тем самым, можно ставить вопрос о максимальных значениях к, при которых /г(гг, к) соответственно не существует или строго больше д{п). Их мы будем обозначать к(п) и к(п) соответственно.
Некоторые результаты получены в статье Б. Сендова (см. [18]). В этой статье с использованием множества Хортона (см. |11|), с помощью которого было доказано несуществование h(7), доказывается несуществование h(n,k) для определенных к при п > 7. Точная формулировка его результата состоит в том, что, если п 4- 2 = 4т 4- г, где т - целое, а г € {0,1,2,3), то
h(n, (г + 4)2m_1 - 4m - г - 1) (1.5)
не существует.
Аналогичные результаты получены в статье Е. Ныкловой (см. [19]). Ей удается слегка улучшить результат Сендова. заменив все четыре константы, соответствующие величине (г+ 4) в выражении (1.5), на несколько большие. В любом случае, из этих результатов следует, что
к(п) > {</2 + о{ 1))". (1.6)
8
- Київ+380960830922