Задача со счастливым концом

Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении^[1] имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.

История

Этот результат комбинаторной геометрии назван Палом Эрдёшем «задачей со счастливым концом», поскольку решение проблемы завершилось свадьбой Дьёрдя Секереша и Эстер Клейн (венг. Eszter Klein). Известна также как «теорема Эрдёша — Секереша о выпуклых многоугольниках».

Обобщения результата на произвольное число точек являются предметом интереса математиков XX и XXI веков.

Доказательство

Если не менее четырёх точек образуют выпуклую оболочку, в качестве выпуклого четырёхугольника можно выбрать любой набор из четырёх точек оболочки. В противном случае имеется треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырёхугольник.

Многоугольники с произвольным числом вершин

Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули «гипотезу Эрдёша — Секереша» — точную формулу для максимального числа вершин выпуклого многоугольника, обязательно существующего в множестве из заданного числа точек в общем положении.

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

В (Erdős & Szekeres 1935) доказано следующее обобщение: для любого натурального $N$ , всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество $N$ точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.

Размер множества как функция числа вершин многоугольника

Пусть $f(N)$ означает минимальное $M$ , для которого любое множество из $M$ точек в общем положении содержит выпуклый $N$ -угольник. Известно, что:

$f(3)=3$ , очевидно.
$f(4)=5$ , доказала Эстер Секереш.
$f(5)=9$ , согласно (Erdős & Szekeres 1935), это первым доказал Э. Макаи; первое опубликованное доказательство появилось в (Kalbfleisch, Kalbfleisch & Stanton 1970). Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что $f(5)>8$ ; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник.
$f(6)=17$ , это было доказано в (Szekeres & Peters 2006). В работе реализован сокращённый компьютерный перебор возможных конфигураций из 17 точек.
Значения $f(N)$ неизвестны для $N>6$ .

Гипотеза Эрдёша — Секереша о минимальном числе точек

Исходя из известных значений $f(N)$ для $N=3,4,5$ , Эрдёш и Секереш предположили, что:

f(N)=1+2^{N-2}

для всех

N

.

Эта гипотеза не доказана, но известны оценки сверху и снизу.

Оценки скорости роста f(N)

Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством:

f(N)\geq 1+2^{N-2}

, (Erdős & Szekeres 1961)

Однако наилучшая известная оценка сверху при $N\geq 7$ не является близкой:

f(N)\leq {2N-5 \choose N-2}+1=O\left({\frac {4^{N}}{\sqrt {N}}}\right)

, (Tóth & Valtr 2005)

(использованы биномиальные коэффициенты).

Вариации и обобщения

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

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

Если внутри четырёхугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами диагонали, мы получим два четырёхугольника, один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырёхугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник (Harborth 1978). Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый семиугольник.(Horton 1983)

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

Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но сначала в (Nicolás 2007) и (Gerken 2008) было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник, потом оценку сверху довели до f(9) (предположительно 129), а оценку снизу — до 30 точек.(Overmars 2003). И, наконец, в 2024 году получен окончательный результат — 30-точечная конфигурация обязательно содержит пустой шестиугольник.

Примечания

↑ В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.

Литература

Chung, F.R.K.; Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry, 19 (3): 367—371, doi:10.1007/PL00009353.
Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463—470.
Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3—4: 53—62. Reprinted in: Erdős, P. (1973), Spencer, J. (ed.), The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, pp. 680—689.
Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete and Computational Geometry, 39 (1—3): 239—272, doi:10.1007/s00454-007-9018-x.
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (eds.), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, ISBN 0-387-00424-6.
Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elem. Math., 33 (5): 116—118.
Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482—484, doi:10.4153/CMB-1983-077-8.
Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 1, Baton Rouge, La.: Louisiana State Univ., pp. 180—188.
Kleitman, D.J.; Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry, 19 (3): 405—410, doi:10.1007/PL00009358.
Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society, 37 (04): 437—458, doi:10.1090/S0273-0979-00-00877-6.
Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry, 38 (2): 389—397, doi:10.1007/s00454-007-1343-6.
Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry, 29 (1): 153—158, doi:10.1007/s00454-002-2829-x.
Peterson, Ivars (2000), "Planes of Budapest", MAA Online, Архивировано из оригинала 21 января 2001.
Scheinerman, Edward R.; Wilf, Herbert S. (1994), "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability", American Mathematical Monthly, 101 (10), Mathematical Association of America: 939—943, doi:10.2307/2975158, JSTOR 2975158.
Szekeres, G.; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem", ANZIAM Journal, 48 (02): 151—164, doi:10.1017/S144618110000300X Архивная копия от 13 декабря 2019 на Wayback Machine.
Tóth, G.; Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry, 19 (3): 457—459, doi:10.1007/PL00009363.
Tóth, G.; Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52, pp. 557—568.
Valtr, P. (2006), On the empty hexagons.

Ссылки

Happy ending problem Архивная копия от 25 сентября 2006 на Wayback Machine and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
Weisstein, Eric W. Happy End Problem (англ.) на сайте Wolfram MathWorld.

[1] В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.

[1]