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

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

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

История

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

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

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

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

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

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

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

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

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

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

$f(3)=3$ , очевидно.
$f(4)=5$ , доказала Эстер Секереш.
$f(5)=9$ , согласно ( ), это первым доказал Э. Макаи; первое опубликованное доказательство появилось в ( ). Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что $f(5)>8$ ; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник.
$f(6)=17$ , это было доказано в ( ). В работе реализован сокращённый компьютерный перебор возможных конфигураций из 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}

, ( )

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

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

, ( )

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

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

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

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

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

Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но в ( ) и ( ) было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более f (9) (предположительно 129) и не менее 30 точек.( ).

Примечания

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

Литература

; (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry , 19 (3): 367—371, doi : .
Erdős, P. ; (1935), , Compositio Math , 2 : 463—470 .
Erdős, P. ; (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 : .
Grünbaum, Branko (2003), Kaibel, Volker; ; (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", , 26 (4): 482—484, doi : .
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 .
; Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry , 19 (3): 405—410, doi : .
Morris, W.; Soltan, V. (2000), , Bulletin of the American Mathematical Society , 37 (04): 437—458, doi : .
Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry , 38 (2): 389—397, doi : .
(2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry , 29 (1): 153—158, doi : .
Peterson, Ivars (2000), , 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 , Mathematical Association of America, 101 (10): 939—943, doi : , JSTOR .
; Peters, L. (2006), , , 48 (02): 151—164, doi : от 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 : .
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), .