Задача Эрдёша—Секереша: продолжение истории

13

Задача Эрдеша – Секереша: продолжение истории

В.КОШЕЛЕВ, А.РАЙГОРОДСКИЙ

Снова в путь

В «Кванте» №2 за этот год была опубликована наша статья «Задача Эрдеша – Секереша о выпуклых многоугольниках» [1]. Там мы рассказывали удивительную (а местами даже романтическую) историю одной из самых красивых и популярных проблем комбинаторной геометрии – историю, которая началась 75 лет назад и которая весьма далека от своего завершения. Читателю, желающему как следует понять истоки того, о чем мы поведем речь в нынешней статье, необходимо, конечно, вооружиться вышеупомянутой статьей, ведь здесь мы лишь напомним краткое содержание «предыдущих серий», а после двинемся в принципиально новые для нас, до сих пор неизведанные области. Итак, основными объектами нашего исследования были множества точек общего положения на плоскости. Напомним, что таковы все множества, никакие три элемента которых не лежат на одной прямой. Нашей целью было отыскание для каждого натурального числа n значения функции g ( n ), которую мы полагали равной наименьшему g такому, что в любом множестве общего положения на плоскости, имеющем мощность g, обязательно есть n точек, являющихся вершинами выпуклого n-угольника. Сперва мы обсудили вопрос о поведении функции g ( n ) при $n \in { 3,4,5,6 }$ и выяснили, что всякий раз $g ( n ) = 2^{n} -^{2} + 1$. Затем мы убедились в том, что вообще при всех $n \ge 3$ величина g ( n ) конечна и что, более того, $g ( n ) \le 4^{n}$, точнее $g ( n ) \le C_{2} nn --_{5}^{2} + 1$ при $n \ge 5$. Наконец, мы показали, что опять-таки при любом $n g ( n ) \ge 2^{n} -^{2} + 1$. Вот, в сущности, и все. Оказывается, однако, что это лишь начало пути. И дело не только в том, что точный вид функции g ( n ) по-прежнему неизвестен (мы лишь можем верить вслед за авторами проблемы, что $g ( n ) = 2^{n} -^{2} + 1 );$ дело еще и в том, что исходная задача допускает ряд весьма естественных, ничуть не менее красивых обобщений и, как принято говорить в науке, модификаций. Именно о них мы теперь и поговорим.

Выпуклые и пустые многоугольники

Модификация задачи Эрдеша – Секереша

Спустя без малого полвека с момента выхода в свет замечательной статьи [2], а точнее в 1978 году, П.Эрдеш предложил слегка видоизменить условие исходной проблемы, которая к тому времени стала классической.

Он задался вопросом: что если мы будем искать в том или ином $множестве^{X}$ общего положения на плоскости не просто вершины выпуклых многоугольников, но вершины таких выпуклых многоугольников, внутри которых нет других точек $множества^{X}$? Такие многоугольники естественно называть пустыми или дырами. На рисунке 1 показан пример дыры и пример не дыры. Введем величину h ( n ), которая послужит аналогом величины g ( n ) в рамках но- Рис 1. Пример дыры и не дыры вой задачи. Что это значит? По идее, все очень просто. Допустим, для данного натурального $n \ge 3$ мы нашли такое число h, что в любом множестве общего положения на плоскости, имеющем мощность h, есть пустой n-угольник и найдется множество общего положения на плоскости, имеющее размер h – 1 и дыр на n вершинах не содержащее. Вот и положим тогда h ( n ) = h. Просто? Не совсем. Дело в том, что сходу не вполне понятно, почему наличие пустых многоугольников в произвольном h-точечном множестве гарантирует нам их присутствие в каждом множестве размера h + 1. Возникает проблема с соблюдением условия пустоты, которого раньше (т.е. при определении величины g ( n ) ) вовсе не было. Иными словами, если прежде мы спокойно говорили о пограничной величине g ( n ), начиная с которой всякое множество соответствующего размера содержало выпуклый многоугольник, то отныне такое спокойствие еще нужно заслужить. По счастью, проблема легко устранима. Утверждение 1. Пусть при некотором h любое множество общего положения на плоскости, имеющее мощность h, содержит выпуклый и пустой n-угольник. Тогда то же самое верно и для каждого множества общего положения размера h + 1. Доказательство. Рассмотрим произвольное множество X мощности $h + 1. Пусть^{H}$ – многоугольник, являющийся его выпуклой оболочкой (см. [1]). Удалим $из^{X}$ любую вершину этого многоугольника. Останется множество размера h, в котором, по нашему предположению, есть выпуклый и пустой n-угольник. Очевидно, выкинутая нами вершина находится вне этого n-угольника. Значит, X содержит выпуклый и пустой n-угольник. Утверждение доказано. Если каждому h, для которого существует множество