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

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

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

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

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

[править | править код]

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

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

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

[править | править код]

Исходя из известных значений для , Эрдёш и Секереш предположили, что:

для всех .

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

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

[править | править код]

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

, (Erdős & Szekeres 1961)

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

, (Tóth & Valtr 2005)

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

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

[править | править код]
Пустые многоугольники

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

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

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

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

Примечания

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

Литература

[править | править код]
  • 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.