[[Image:8-points-no-pentagon.svg|thumb|Восемь точек в общем положении для которых нет выпуклого пятиугольника.]]
[[Image:8-points-no-pentagon.svg|thumb|Восемь точек в общем положении для которых нет выпуклого пятиугольника.]]
В {{sfn|Erdős|1935}} доказано следующее обобщение:
В {{sfn||Erdős|Szekeres|1935}} доказано следующее обобщение:
:'''Теорема.''' Для любого натурального ''N'', всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество ''N'' точек, которые являются вершинами выпуклого многоугольника.
:'''Теорема.''' Для любого натурального ''N'', всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество ''N'' точек, которые являются вершинами выпуклого многоугольника.
Строка 19:
Строка 19:
* ''f''(3) = 3, очевидно.
* ''f''(3) = 3, очевидно.
* ''f''(4) = 5.<ref> То, что доказала Эстер Кляйн.</ref>
* ''f''(4) = 5.<ref> То, что доказала Эстер Кляйн.</ref>
* ''f''(5) = 9.<ref>Согласно {{sfn|Erdős|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{sfn|Kalbfleisch|1970}}.</ref> Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt ''f''(5) > 8; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый многоугольник.
* ''f''(5) = 9. Согласно {{sfn||Erdős|Szekeres|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{harv|Kalbfleisch|Kalbfleisch|Stanton|1970}}. Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt ''f''(5) > 8; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый многоугольник.
* ''f''(6) = 17.<ref>Это было доказано в {{sfn|Szekeres|2006}}. В работе реализован сокращенный компьютерный перебор возможных конфигураций из 17 точек.</ref>
* ''f''(6) = 17.Это было доказано в {{sfn|Szekeres|2006}}. В работе реализован сокращенный компьютерный перебор возможных конфигураций из 17 точек.
* Значения ''f''(''N'') неизвестны для ''N'' > 6.
* Значения ''f''(''N'') неизвестны для ''N'' > 6.
Строка 31:
Строка 31:
== Оценки скорости роста <math> f(N) </math> ==
== Оценки скорости роста <math> f(N) </math> ==
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством.
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством.
Однако наилучшая известная оценка сверху при ''N'' ≥ 7 не является близкой.
Однако наилучшая известная оценка сверху при ''N'' ≥ 7 не является близкой.
:<math>f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right).</math><ref>{{sfn|Tóth|2005}}. Смотри [[биномиальные коэффициенты]] и [[«O» большое и «o» малое]] относительно обозначений и [[Формула Стирлинга|формулу Стирлинга]] для вывода асимптотики.</ref>
:<math>f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right).</math> {{sfn|Tóth|2005}}. Смотри [[биномиальные коэффициенты]] и [[«O» большое и «o» малое]] относительно обозначений и [[Формула Стирлинга|формулу Стирлинга]] для вывода асимптотики.
==Пустые многоугольники==
==Пустые многоугольники==
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении ''пустой'' выпуклый четырехугольник, [[пятиугольник]], и так далее. То есть многоугольник не содержащий внутренних точек.
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении ''пустой'' выпуклый четырехугольник, [[пятиугольник]], и так далее. То есть многоугольник не содержащий внутренних точек.
Если внутри четырехугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами [[Диагональ|диагонали]] мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник.<ref>{{sfn|Harborth|1978}} </ref> Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый [[Правильный семиугольник|семиугольник]].<ref>{{sfn|Horton|1983}}</ref>
Если внутри четырехугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами [[Диагональ|диагонали]] мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник {{sfn|Harborth|1978}}. Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый [[Правильный семиугольник|семиугольник]].{{sfn|Horton|1983}}
Таким образом, задача о пустых многоугольниках не является проблемой [[Теория Рамсея|теории Рамсея]] и в принципе решена.
Таким образом, задача о пустых многоугольниках не является проблемой [[Теория Рамсея|теории Рамсея]] и в принципе решена.
Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым. Но в {{sfn|Nicolás|2007}} и {{sfn|Gerken|2008}} было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более ''f''(9) (предположительно 129) и не менее 30 точек.<ref>{{sfn|Overmars|2003}}.</ref>
Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым. Но в {{sfn|Nicolás|2007}} и {{sfn|Gerken|2008}} было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более ''f''(9) (предположительно 129) и не менее 30 точек.{{sfn|Overmars|2003}}.
| contribution = The Erdős-Szekeres theorem: upper bounds and related results
| pages = 557–568
| publisher = Mathematical Sciences Research Institute Publications, no. 52
| title = Combinatorial and computational geometry
| year = 2005}}.
*{{citation
| last = Valtr | first = P.
| title = On the empty hexagons
| url = http://kam.mff.cuni.cz/~valtr/h.ps
| year = 2006}}.
| year = 2006}}.
{{refend}}
{{refend}}
Версия от 10:28, 21 февраля 2013
Задача со счастливым концом: любое множество из пяти точек содержит вершины выпуклого четырехугольника.
Задача со счастливым концом (названная так Полем Эрдёшем, поскольку её решение завершилось свадьбой Дьёрдя Секереша и Эстер Клейн) формулируется следующим образом:
Теорема со счастливым концом доказывается простым анализом. Если не менее четырех точек образуют выпуклую оболочку, в качестве выпуклого четырехугольника можно выбрать любой набор из четырех точек оболочки. В противном случае мы имеем треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырехугольник.
Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули гипотезу Эрдёша-Секереша - точную формулу для максимального числа вершин выпуклого многоугольника обязательно существующего в множестве из N точек в общем положении.
Восемь точек в общем положении для которых нет выпуклого пятиугольника.
Теорема. Для любого натурального N, всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество N точек, которые являются вершинами выпуклого многоугольника.
Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.
Размер множества как функция числа вершин многоугольника
Пусть f(N) означает минимальное M для которого любое множество any из M точек в общем положении содержит выпуклый N-угольник. Известно что
f(5) = 9. Согласно [2], это первым доказал Э. Макаи; первое опубликованное доказательство появилось в (Kalbfleisch, Kalbfleisch & Stanton 1970). Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt f(5) > 8; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый многоугольник.
f(6) = 17.Это было доказано в [4]. В работе реализован сокращенный компьютерный перебор возможных конфигураций из 17 точек.
Значения f(N) неизвестны для N > 6.
Гипотеза Эрдёша-Секереша о числе выпуклых многоугольников
Исходя из известных значений f(N) для N = 3, 4 и 5, Эрдёш и Секереш предположили, что
для всех
Эта гипотеза не доказана, но известны оценки сверху и снизу.
Оценки скорости роста
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством.
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении пустой выпуклый четырехугольник, пятиугольник, и так далее. То есть многоугольник не содержащий внутренних точек.
Если внутри четырехугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами диагонали мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник [7]. Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый семиугольник.[8]
Таким образом, задача о пустых многоугольниках не является проблемой теории Рамсея и в принципе решена.
Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но в [9] и [10] было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более f(9) (предположительно 129) и не менее 30 точек.[11].
Примечания
↑В данном контексте общее положение означает, что никакие две точки не совпадают и никакие три точки не лежат на одной прямой.
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.
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.
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, JSTOR2975158.
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.
