Проблемы Эрдеша-Секереша в комбинаторной геометрии тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Математический институт им. В.А. Стеклова Российская Академия Наук

003487656

На правах рукописи УДК 514.172.45, 519.146

Кошелев Виталий Анатольевич

ПРОБЛЕМЫ ЭРДЕША-СБКЕРЕША В КОМБИНАТОРНОЙ ГЕОМЕТРИИ

Специальность 01.01.04 — геометрия и топология

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 О ДЕК 2009

Москва - 2009

003487656

Работа выполнена в отделе геометрии и топологии Математического института им. В.А. Стеклова РАН

Научный руководитель:

доктор физико-математических наук, Андрей Михайлович Райгородский доктор физико-математических наук, профессор МГУ Николай Петрович Долбилин

Официальные оппоненты:

доктор физико-математических наук, профессор ЯрГУ

Владимир Леонидович Дольников

кандидат физико-математических наук Тарас Евгеньевич Панов

Ведущая организация:

Санкт-Петербургский Государственный Университет

Защита диссертации состоится 24 декабря 2009 в 14 часов на заседании диссертационного совета Д002.022.03 в Математическом институте им. В.А. Стеклова Российской Академии Наук по адресу: 119991, Москва, ул. Губкина, 8 (9 этаж).

С диссертацией можно ознакомиться в библиотеке Математического института им. В.А. Стеклова РАН.

Автореферат разослан 18 ноября 2009 г.

Председатель диссертационного совета

Д002.022.03 в МИАН член-корреспондент РАН

А. Н. Паршин

Общая характеристика работы

Актуальность темы

Настоящая работа посвящена решению ряда рамсеевских задач в комбинаторной геометрии. Все эти задачи происходят от классической проблемы Эрдеша - Секереша 1935 года.

Теория Рамсея - это, говоря не совсем формально, наука о том, что в очень больших и сложных структурах непременно есть достаточно регулярные подструктуры. В течение XX века выделилась делая совокупность дисциплин, каждую из которых естественно отнести к теории Рамсея. Так, в теории чисел наиболее глубоко изученной рамсеевской проблемой является задача об отыскании длинных арифметических прогрессий в плотных подмножествах натурального ряда1,2. В теории графов и гиперграфов речь идет о так называемых числах Рамсея3,4'5,6,7'8. Наконец, в геометрии рамсеевская проблематика сконцентрирована около задач Нелсона - Эрдеша - Хадвигера о раскрасках метрических пространств9,10 и задач типа Эрдеша - Секереша, которым и посвящена настоящая работа.

По существу, все задачи Эрдеша - Секереша состоят в отыскании минимального натурального числа т, при котором любое множество точек общего положения на плоскости, имеющее мощность т, содержит вершины "достаточно большого и регулярного" многоугольника. Здесь регулярность, как правило, означает выпуклость, к которой в зависимости от задачи добавляются различные дополнительные ограничения на количество внутренних точек многоугольника.

'Р. Грэхэм, Начала теории Рамсея, Москва, "Мир 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 formed logic, Proc. London Math. Soc. Scr. 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. Райгородский, Проблема Борсука и хроматические числа некоторых метрических пространств, Успехи Матем. Наук, X. 56 (2001), Вып. 1, стр. 107 - 146.

10А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.

Проблематика Эрдсша - Секереша возникла в 1935 году11, и за прошедшие с тех пор три четверти века сотни статей и монографий были посвящены ей12,13.

В последние десятилетия стала ясна роль теории Рамсея в теории сложности вычислений и в теории информации. И геометрические аспекты теории также исключительно важны здесь.

Цель работы

Цель исследования состоит в решении ряда задач типа Эрдеша - Секереша.

Основные методы исследования

В диссертации используются методы рамсеевской теории графов и гиперграфов, а также методы элементарной геометрии.

Научная новизна

Все результаты диссертации являются новыми.

Теоретическая и практическая значимость полученных результатов

Диссертация носит теоретический характер. Полученные в ней результаты дают новую информацию о наличии регулярных структур в множествах точек общего положения на плоскости. Кроме того, результаты диссертации могут быть использованы при чтении различных курсов по теории Рамсея и комбинаторной геометрии.

Основные положения диссертации, выносимые на защиту.

1. Изучена величина h(n), равная минимальному числу h, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого и пустого n-угольника. Осуществлена исчерпывающая классификация 463-элементных множеств, каждое из которых непременно содержит вершины выпуклого и пустого шестиугольника. Найдены всего четыре типа таких множеств, для которых существование выпуклого

nP. Erdôs, G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2 (1935), 463 - 470.

12W. Morris, V. Soltan, The Erdôs - 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-точечные множества содержат выпуклый и пустой шестиугольник.

2. Исследована величина h(n,k), равная минимальному числу h, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого п-уголь-ника с не более к точками исходного множества внутри. Доказано, что Л(6,1) < 127.

3. Найдены принципиально новые нижние оценки для минимального числа к, при котором величина h(n, к) не существует.

4. Найдены принципиально новые нижние оценки для минимального числа к, при котором h(n, к) > 2п~2 + 1.

5. Изучены задачи отыскания в множествах общего положения на плоскости специальных выпуклых ломаных, называемых "чашками" и "крышками".

6. Доказан ряд новых верхних оценок для величины h(n, mod q), равной минимальному числу h, такому, что среди любых h точек общего положения на плоскости можно найти п точек, являющихся вершинами выпуклого n-угольника, внутри которого ноль точек исходного множества по модулю q.

Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов

Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на международной конференции "EuroComb 2007" в Севилье (Испания), на международной конференции "Fete of Combinatorics and Computer Science" в Кестхей (Венгрия 2008 г.), на международной конференции "Дискретные модели в теории управляющих систем" (Москва, 2009 г.), на русско-японской конференции "Discrète Geometry and Statistics of Configurations" (Москва, 2009 г.), на международной конференции "EuroComb 2009" в

Бордо (Франция); на семинарах д.ф.-м.н. A.M. Райгородского в МГУ, на семинаре проф. Н.П. Долбилина в МГУ, на семинаре проф. Н.Г. Моще-витина и МГУ, на "Семинаре по Геометрии" в НМУ под руководством проф. Н.П. Долбилина, проф. И.Х. Сабитова и проф. В.Ю. Протасова, на кафедральных семинарах кафедры "Анализ Данных" факультета инноваций и высоких технологий МФТИ под руководством проф. A.M. Райгородского.

Опубликованность результатов

Результаты диссертации опубликованы в шести работах. Список этих работ приведен в конце автореферата.

Структура и объем диссертации

В диссертации пять глав и список литературы. Полный объем 105 страниц, из них 3 страницы занимает список литературы (39 наименований).

Содержание работы

В первой главе диссертации вводятся основные определения, формулируются решаемые в работе задачи, дается обзор известных ранее результатов и, наконец, формулируются новые теоремы.

Итак, напомним, что множество точек находится в общем положении., если никакие три его элемента не лежат на одной прямой. Далее, пусть на плоскости дана система координат. Множество точек

(xi,yi),...,(xn,yn)

называется п-чашкой, если х^ < ... < хп и

У1-У2 ^ У2 - Уз Уп-1 ~ Уп

Х\-Х2 Х2-Х3 "' Хп-1-Хп'

Это множество будет п-крышкой, если Х\ < ... < хп и

У\ - У2 У2 - УЗ Уп-1 - Уп

XI -Х2 Х2-Х3 "' - Хп'

Ниже мы перечислим все задачи, в каждой из которых нам удалось получить новые результаты.

В разделе 1.1 обсуждается история первой проблемы Эрдеша- Секе-реша, с которой, собственно, и началась вся наука.

Первая проблема Эрдеша-Секереша. Для любого целого п> 3 найти минимальное положительное числод(п), такое, что из любого множества точек на плоскости, находящегося в общем положении и содержащего по крайней мере д(п) точек, можно выбрать подмножество мощности п, элементы которого являются вершинами выпуклого п-угольника.

Здесь также определяется величина f(l, т) как минимальное положительное число, такое, что любое множество точек на плоскости X в общем положении, не содержащее пары точек с одинаковыми абсциссами (в фиксированной системе координат), содержит либо /-чашку, либо m-крышку, коль скоро \Х\ > f(l,m).

Раздел 1.2 посвящен истории следующей задачи:

Вторая проблема Эрдеша-Секереша. Для любого целого п > 3 найти минимальное положительное число h{n), такое, что из любого

множества точек X па плоскости, находящегося в общем положении и содержащего по крайней мере h(n) точек, можно выбрать подмножество мощности п, элементы которого являются вершинами выпуклого и пустого п-угольника, то есть этот п-угольник не содержит внутри себя других точек из X.

В разделе 1.3 речь идет о естественном обобщении предыдущей задачи.

Третья проблема типа Эрдеша-Секереша. Для любых целых п > 3 и к > 0 найти минимальное положительное число h(n,k), такое, что из любого множества точек X на плоскости, находящегося в общем положении и содержащего по крайней мере h(n, к) точек, можно выбрать подмножество мощности п, элементы которого являются вершинами выпуклого п-угольника С с условием \ (С \ дС) П Х\ < к, то есть этот п-угольник содержит внутри себя не более к других точек из X.

Здесь вводятся новые важные числовые характеристики. А именно, рассматриваются максимальные к, при которых h(n, к) соответственно не существует или строго больше д(п). Они обозначаются к(п) и к(п) соответственно.

Раздел 1.4 связан с интересным вариантом проблемы Эрдеша - Секе-реша, в рамках которого пустота многоугольника понимается в довольно специфическом смысле.

Четвертая проблема типа Эрдеша-Секереша. Для любых целых чисел п > 3 и q > 2 найти минимальное положительное число h(n,mo&q), такое, что из любого множества точек X на плоскости, находящегося в общем положении и содержащего по крайней мере h(n, mod q) точек, можно выбрать подмножество мощности п, элементы которого являются вершинами выпуклого п-угольника С с условием | (С \ дС) П Х\ = 0 (mod q), то есть этот п-угольник содержит внутри себя другие точки из X в количестве, делящемся на Ч-

В разделе 1.5 рассказывается о многомерных обобщениях всех перечисленных ранее задач.

В разделе 1.6 обсуждаются вторая и третья проблемы Эрдеша - Се-кереша, описывается техника, с помощью которой в дальнейшем дока-

зываются новые верхние оценки для /¿(6) и для /1(6,1). А именно, закладывается фундамент для последующей классификации множеств точек общего положения на плоскости с точки зрения наличия в них выпуклых и пустых шестиугольников или выпуклых шестиугольников с не более чем одной точкой внутри. Введем основные определения.

Для некоторого п зафиксируем произвольное множество X мощности д{п) или более. Без ограничения общности далее предполагается, что п = 8. Заметим, что X содержит по крайней мере один выпуклый восьмиугольник. Отношение вложенности на множестве всех выпуклых восьмиугольников, образованных точками изА^, есть отношение строгого порядка. Поэтому всегда можно говорить о минимальных восьмиугольниках в X. Выберем один из них и обозначим множество его вершин через 71. Положим I' = (сопу(Н) \ 'Н) Г\ X - множество точек из X, лежащих внутри выпуклой оболочки Н. Либо X' пусто (но тогда, впрочем, и обсуждать нечего), либо множество сопу(Х') является выпуклым многоугольником, отрезком ("2-угольником") или точкой ("1-угольником"); обозначим через X множество его вершин (I = д(сопу(Х')) П X). Если \Х\ > 2, то можно определить 3' = (сопу(1) \ X) П X как множество точек из X, находящихся внутри выпуклой оболочки X. Заметим, что если 3} непусто, то сопу{3') также является выпуклым многоугольником (в частности, 1- или 2-угольником), поэтому можно определить 3 как множество его вершин. Аналогичным образом строятся множества /С, С и так далее, причем процесс в какой-то момент оборвется.

Положим г = |1|, з = \3\, ... Скажем, что множество X имеет тип (8, г, ...). В частности, в "вырожденных" случаях возникают типы (8,0, 0,...), (8,г,0,...) и пр.

Заметим, что тип определен неоднозначно. В дальнейшем мы не станем пользоваться возможным многообразием выпуклых восьмиугольников в X. Говоря о типе множества X, мы будем лишь подразумевать, что в X есть выпуклый восьмиугольник, относительно которого X имеет данный тип.

Заметим, что условие 1^1 > д(8) является, в некотором смысле, лишним. Можно было бы говорить, что множество либо соответствует некоторому типу (8, г, ...), либо не соответствует никакому типу аналогичного вида (если в нем нет выпуклых восьмиугольников). Дело в том, что когда мы обсуждаем только множества мощности большей или равной д(8), то любое такое множество обязательно соответствует некоторому

типу. И наконец, ясно, что определение вложенных друг в друга выпуклых оболочек можно дать и для случаев, когда \Н\ ф 8.

Далее, в контексте изучения величин /г(б) и /1(6,1) нас будут интересовать только множества типов (8, г, j, 0,...) и (7, i,j, 0,...). Это связано с тем, что, как показали, независимо друг от друга, П. Вальтр14 и К. Николас15, если мы имеем дело с множествами типа (> 7,i,j, > 1,...), то они всегда содержат выпуклый и пустой шестиугольник. В связи с этим, для краткости мы будем говорить только о случаях (конфигурациях) "вида" (8,i,j). И наконец, назовем вид неисключительным для h(6), если любое множество, которое представляет интересующий нас вид, содержит выпуклый и пустой шестиугольник; и исключительным, если существует пример множества (опять же представляющего нужный вид), который не содержит выпуклого и пустого шестиугольника. Ясно, что это определение можно дать и для других величин, в частности и для h(6,1). Отметим, что Геркен16 изучал множества типа (9,i,j,...) и установил, что все 57 случаев вида (9,i,j) являются неисключительными.

Раздел 1.7 посвящен формулировкам основных новых теорем. Перечислим эти теоремы.

Теорема 1. Для конструкции из вложенных выпуклых оболочек, начинающихся с восьмиугольника, случаи вида (8,7,3), (8,6,2), (8,6,1) и (8,5,1) являются исключительными для h(6), но всегда на расположения, дающие контрпример, имеются "жесткие ограниченияостальные 39 случаев являются неисключительными.

Теорема 2. Справедлива оценка h(Q, 1) < g(7) < 127, и более того, все 31 случаев вида (7,i,j) являются неисключительными дляН{6,1).

Оценка в теореме 2 для д{7) обусловлена известным неравенством17

9(п) < (tt) + I-

Теорема 3. Если п> 7, то для нечетных и четных значений п, соот-

14Р. Valtr, On the empty hexagons, Contemporary Mathematics, 453 (2008), 433 - 442.

15C. Nicolas, The empty hexagon theorem, Discrete Comput. Geom., 38 (2007), N2, 389 - 397.

16T. Gerken, On empty convex hexagons in planar point set, Discrete Comput. Geom., 39 (2008), 239 - 272.

17G. Töth, P. Valtr, The Erdos-Szekeres theorem: upper bounds and related results, Combinatorial and Computational geometry, MSRI Publication 52 (2005), 557 - 568.

ветственно, не существуют:

Иными словами,

к(2г - 1) >

(2г - 1 - 7) (2г — 1 — 7)/2

- 1.

Оценки из теоремы 3 ведут себя как (2 + о(1))п. Все предшествующие

Перед формулировкой теоремы 4 вводится величина к{п), которая представляет собой максимальное к, удовлетворяющее условию

Смысл в том, что18 д(п) > 2п~2 + 1 и гипотетически д(п) = 2"~2 + 1. Однако гипотеза не доказана, и потому неравенство h(n, к) > д(п) мы заменяем указанным неравенством.

Теорема 4. Если п > 6, то

Далее, определяется величина f(l,m,l\,mi) как минимальное положительное число, такое, что из любого множества точек на плоскости, находящегося в общем положении и содержащего по крайней мере/(/, т, ¿1, mi) точек, всегда можно выбрать подмножество, образующее либо I-чашку не более чем с h точками внутри (т.е. внутри соответствующего ¿-угольника), либо m-крышку не более чем с т\ точками внутри.

18Р. Erdös, G. Szekeies, On some extremum problems in elementary geometry, Ann. Univ. Sei. Budapest Eötvös Sect. Math., 3-4 (1961), 53 - 62.

оценки имели вид +o(l))n.

h(n,k) > 2n~2 + 1.

Иными словами,

Теорема 5. Положим с (г) = 2'-Г22-! + — г. Пусть Iq и Шо таковы, что c(Iq) > 0, с(то) > 0. Тогда для любых I >5 и т > 5, при условиях I > /о и тп> то, не существует

tii п \ fl + m-lQ-ma\ . , .(l + m-lo-тЛ Л / у,, т, c(Iq) ^ ^ j-l,c(m0)^ , _ j - 1J .

Теорема 6. Для любых / >4,т>4«а>0 условии, что в аргументах f числа неотрицательны) выполнены неравенства

f -m + l,aj > f(l,m),

/(i.m.a, (^-36)"/ + 1)>/(/'т)'

Теорема 7. Если п > 2q — 1, то имеет место неравенство h(n, mod q) < — 4) + 4).

С учетом известного неравенства д(п) < (2^Г35) + 1, оценка в теореме 7 является экспоненциальной. Все предшествующие оценки представляли собой башни экспонент.

Теорема 8. Если п > q + 2, то для четных и нечетных q, соответственно, имеют место неравенства

/г(п,modq) < Яз(п,п,... ,п),

4-V-/

9

h(n, mod q) < R3(g(n),n,.. ., n).

q-1

Глава 2 посвящена доказательству теоремы 1. В ней разработана тонкая техника, позволившая осуществить нужную классификацию. Глава разбита на три раздела. В разделе 2.1 вводятся вспомогательные определения и обозначения. В разделе 2.2 разбираются неисключительные случаи, а в разделе 2.3 - исключительные.

В главе 3 доказывается теорема 2.

В главе 4 доказываются теоремы 3 - 6 о внутренних точках. Каждой из них посвящен свой раздел.

Наконец, в главе 5 доказываются теоремы 7 и 8 о четвертой проблеме типа Эрдеша - Секереша. Опять-таки, каждой из теорем отведен свой раздел.

Благодарности

Автор глубоко признателен научным руководителям Андрею Михайловичу Райгородскому и Николаю Петровичу Долбилину за постановку задач и постоянное внимание и интерес к работе.

Работы автора по теме диссертации

1. В.А. Кошелеи, О проблеме Эрдеша-Секереша, Доклады Академии Наук, 415 (2007), N6, 734 - 736.

2. В.А. Кошелев, Вокруг проблем Эрдеша-Секереша, Доклады Академии Наук, 426 (2009), N3, 304 - 306.

3. V.A.Koshelev, On the Erdos-Szekeres problem in combinatorial geometry, Electronic Notes in Discrete Mathematics, V. 29 (2007), 175-177.

4. V.A.Koshelev, On Erdos-Szekeres-type problems, Electronic Notes in Discrete Mathematics, V. 34 (2009), 447-451.

5. B.A. Кошелев, Задача Эрдеша-Секереша о пустых шестиугольниках на плоскости, Моделирование и анализ информационных систем, 16 (2009), N2, 21 - 73.

6. В.А. Кошелев, Почти пустые шестиугольники, Фундаментальная и прикладная математика, 14 (2008), N6, 91 - 120.

1. P. Erdos, G. Szekeres, A combinatorial problem in geometry, Compositio Math., 2 (1935), 463 - 470.

2. P. Erdos, G. Szekercs, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest Eotvos Sect. Math., 3-4 (1961), 53 62.

3. 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.

4. G. Szekeres, L. Peters, Computer solution to the 17-point Erdos-Szekeres problem, ANZIAM J., 48 (2006), 151 164.

5. F. Chung, R. Graham, Forced convex n-gons in the plane, Discrete Cornput. Geom., 19 (1998), 367 371.

6. D. Kleitman, L. Pachter, Finding convex sets among points in the plane, Discrete Comput. Geom., 19 (1998) 405 410.

7. G. Toth, P. Valtr, Note on the Erdos Szekeres theorem, Discrete Comput. Geom., 19 (1998), 457 - 459.

8. G. Toth, P. Valtr, The Erdos-Szekeres theorem: upper bounds and related results, Combinatorial and Computational geometry, MSRI Publication 52 (2005), 557 568.

9. P. Erdos, Some more problems in elementary geometry, Austral. Math. Soc. Gaz., 5 (1978), 52 54.

10. H. Harborth, Konvexe Fiinfecke in ebenen Punktmengen, Elem. Math., 33 (1978), 116 118.

11. J.D. Horton, Sets with no empty 7-gons, Canad. Math. Bull., 26 (1983), 482 484.

12. T. Gerken, On empty convex hexagons in planar point set, Discrete Comput. Geom., 39 (2008), 239 272.

13. С. Nicolas, The empty hexagon theorem, Discrete Comput. Geom., 38 (2007), N2, 389 397.

14. P. Valtr, On the empty hexagons, Contemporary Mathematics, 453 (2008), 433 442.

15. D. Rappaport, Computing the largest empty convex subset of a set of points, ACM 0-89791-163-6/85/006/0161, 1985, 161-167.

16. M. Overmars, B. Scholten, I. Vincent, Sets without empty convex 6-gons, Bull. European Assoc. Theor. Comput. Sci., 37 (1989), 160 168.

17. M. Overmars, Finding sets of points without empty convex 6-gons, Discrete Comput. Geom., 29 (2003), 153 158.

18. Бл. Сеидов, Обязательные конфигурации точек на плоскости, Фундаментальная и прикладная математика, 1 (1995), N2, 491 516.

19. Н. Nyklova, Almost empty polygons, Studia Scientiarum Mathematicarum Hungarica, 40 (2003), N3, 269 286.

20. A. Bialostocki, P. Dierker, B. Voxman, Some notes on the Erdos-Szekeres theorem, Discrete Math, 91 (1991), N3, 231 238.

21. F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2, 30 (1930), 264 286.

22. R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, John Wily and Sons, NY, Second Edition, 1990.

23. M. Холл, Комбинаторика, Москва, "Мир", 1970.

24. Y. Саго, On the generalized Erdos-Szekeres conjecture a new upper bound, Discrete Math, 160 (1996), 229 - 233.

25. G. Karolyi, J. Pach, G. Toth, A modular version of the Erdos-Szekeres theorem, Studia Sci. Math. Hungar, 38 (2001), 245 259.

26. P. Valtr, A Sufficient Condition for the Existence of Large Empty Convex Polygons, Discrete Comput. Geom., 28 (2002), N4, 671 682.

27. P. Valtr, Several results related to the Erdos-Szekeres theorem, Doctoral Dissertation, Charles University, Prague, 1996

28. G. Karolyi, Ramsey-remainder for conves sets and the Erdos-Szekeres theorem, Discrete Applied Math., 109 (2001), 163-175.

29. G. Karolyi, P. Valtr, Point configurations in d-space without large subsets in convex position, Discrete Comput. Geom., 30 (2003), 277-286.

30. T. Bisztriczky, V. Soltan, Some Erdos-Szekeres type results about points* in space, Monatsh. Math., 118 (1994), 33-40.

31. T. Bisztriczky, H. Harborth, On empty convex polytopes, J. Geom. 52 (1995), 25-29.

32. P. Valtr, Sets in Ш with no large empty convex subsets, Discrete Math., 108 (1992), 115-124.

33. B.A. Кошелев, О проблеме Эрдеша-Секереша, Доклады Академии Наук, 415 (2007), N6, 734 736.

34. В.А. Кошелев, Вокруг проблем Эрдеша-Секереша,, Доклады Академии Наук, 426 (2009), N3, 304 306.

35. V.A.Koshelev, On the Erdos-Szekeres problem in combinatorial geometry, Electronic Notes in Discrete Mathematics, V. 29 (2007), 175-177.

36. V.A.Koshelev, On Erdos-Szekeres-type problems, Electronic Notes in Discrete Mathematics, V. 34 (2009), 447-451.

37. B.A. Кошелев, Задача Эрдеша-Секереша о пустых шестиугольниках на плоскости, Моделирование и анализ информационных систем, 16 (2009), N2, 21 73.

38. В.А. Кошелев, Почти пустые шестиугольники, Фундаментальная и прикладная математика, 14 (2008), N6, 91 120.

39. В.А. Кошелев, Теорема Эрдеша-Секереша и сравнения, Математические Заметки, в печати.