Введение к работе
Актуальность темы
Настоящая работа посвящена решению ряда рамсеевских задач в комбинаторной геометрии. Все эти задачи происходят от классической проблемы Эрдеша - Секереша 1935 года.
Теория Рамсея - это, говоря не совсем формально, наука о том, что в очень больших и сложных структурах непременно есть достаточно регулярные подструктуры. В течение XX века выделилась целая совокупность дисциплин, каждую из которых естественно отнести к теории Рамсея. Так, в теории чисел наиболее глубоко изученной рамсеевской проблемой является задача об отыскании длинных арифметических прогрессий в плотных подмножествах натурального ряда1'2. В теории графов и гиперграфов речь идет о так называемых числах Рамсея3'4'5'6'7'8. Наконец, в геометрии рамсеевская проблематика сконцентрирована около задач Нелсона - Эрдеша - Хадвигера о раскрасках метрических пространств9'10 и задач типа Эрдеша - Секереша, которым и посвящена настоящая работа.
По существу, все задачи Эрдеша - Секереша состоят в отыскании минимального натурального числа т, при котором любое множество точек общего положения на плоскости, имеющее мощность т, содержит вершины "достаточно большого и регулярного" многоугольника. Здесь регулярность, как правило, означает выпуклость, к которой в зависимости от задачи добавляются различные дополнительные ограничения на количество внутренних точек многоугольника.
1Р. Грэхэм, Начала теории Рамсея, Москва, "Мир 1984.
2R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, John Wiley and Sons, NY, Second Edition, 1990.
3F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2, 30 (1930), 264 - 286.
4H. Алон, Дж. Спенсер, Вероятностный метод, Москва: Бином. Лаборатория знаний, 2007.
5П. Эрдеш и Дж. Спенсер, Вероятностные методы в комбинаторике, Москва, "Мир 1976.
6М. Холл, Комбинаторика, Москва, "Мир 1970.
7А.М. Райгородский, Вероятность и алгебра в комбинаторике, Москва, МЦНМО, 2008.
8В. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.
9A.M. Райгородский, Проблема Борсука и хроматические числа некоторых метрических пространств, Успехи Матем. Наук, Т. 56 (2001), Вып. 1, стр. 107 - 146. 10А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.
Проблематика Эрдеша - Секереша возникла в 1935 году , и за прошедшие с тех пор три четверти века сотни статей и монографий были посвящены ей12'13.
В последние десятилетия стала ясна роль теории Рамсея в теории сложности вычислений и в теории информации. И геометрические аспекты теории также исключительно важны здесь.
Цель работы
Цель исследования состоит в решении ряда задач типа Эрдеша - Секереша.
Основные методы исследования
В диссертации используются методы рамсеевской теории графов и гиперграфов, а также методы элементарной геометрии.
Научная новизна
Все результаты диссертации являются новыми.
Теоретическая и практическая значимость полученных результатов
Диссертация носит теоретический характер. Полученные в ней результаты дают новую информацию о наличии регулярных структур в множествах точек общего положения на плоскости. Кроме того, результаты диссертации могут быть использованы при чтении различных курсов по теории Рамсея и комбинаторной геометрии.
Основные положения диссертации, выносимые на защиту.
1. Изучена величина h(n), равная минимальному числу /г, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого и пустого п-угольника. Осуществлена исчерпывающая классификация 463-элсмснтных множеств, каждое из которых непременно содержит вершины выпуклого и пустого шестиугольника. Найдены всего четыре типа таких множеств, для которых существование выпуклого
nP. Erdos, G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2 (1935), 463 - 470. 12 W. Morris, V. Soltan, The Erdos - Szekeres problem on points in convex position, Bulletin (new series) of the Amer. Math. Soc, 37 (2000), N4, 437 - 458.
13P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.
и пустого шестиугольника не гарантируется. Все остальные типы всегда содержат выпуклый и пустой шестиугольник. Тем самым почти все 463-точечные множества содержат выпуклый и пустой шестиугольник.
Исследована величина h(n,k), равная минимальному числу /г, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого п-уголь-ника с не более к точками исходного множества внутри. Доказано, что /г(6,1) < 127.
Найдены принципиально новые нижние оценки для минимального числа к: при котором величина h(n, к) не существует.
Найдены принципиально новые нижние оценки для минимального числа к: при котором h(n, к) > 2п~2 + 1.
Изучены задачи отыскания в множествах общего положения на плоскости специальных выпуклых ломаных, называемых "чашками" и "крышками".
Доказан ряд новых верхних оценок для величины h(n, mod q), равной минимальному числу /г, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого n-угольника, внутри которого ноль точек исходного множества по модулю q.
Все результаты диссертации получены соискателем самостоятельно.
Апробация результатов
Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на международной конференции "EuroComb 2007" в Севилье (Испания), на международной конференции "Fete of Combinatorics and Computer Science" в Кестхей (Венгрия 2008 г.), на международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2009 г.), на русско-японской конференции "Discrete Geometry and Statistics of Configurations" (Москва, 2009 г.), на международной конференции "EuroComb 2009" в
Бордо (Франция); на семинарах д.ф.-м.н. A.M. Райгородского в МГУ, на семинаре проф. Н.П. Долбилина в МГУ, на семинаре проф. Н.Г. Моще-витина в МГУ, на "Семинаре по Геометрии" в НМУ под руководством проф. Н.П. Долбилина, проф. И.Х. Сабитова и проф. В.Ю. Протасова, на кафедральных семинарах кафедры "Анализ Данных" факультета инноваций и высоких технологий МФТИ под руководством проф. A.M. Райгородского.
Опубликованность результатов
Результаты диссертации опубликованы в шести работах. Список этих работ приведен в конце автореферата.
Структура и объем диссертации