Проблема со счастливым концом

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

В математике « задача счастливого конца » (названная так Полом Эрдёшем, потому что она привела к браку Джорджа Секереса и Эстер Кляйн). ^[1]) представляет собой следующее утверждение:

Теорема - любой набор из пяти точек плоскости в общем положении. ^[2] имеет подмножество из четырех точек, образующих вершины выпуклого четырехугольника .

Это был один из первых результатов, который привел к развитию теории Рэмсея .

Теорему о счастливом конце можно доказать с помощью простого анализа случая: если четыре или более точек являются вершинами выпуклой оболочки , можно выбрать любые четыре такие точки. Если же, наоборот, выпуклая оболочка имеет форму треугольника с двумя точками внутри, то можно выбрать две внутренние точки и одну из сторон треугольника. См. Петерсон (2000) для иллюстрированного объяснения этого доказательства и Моррис и Солтан (2000) для более подробного обзора проблемы.

Гипотеза Эрдеша-Секереша точно утверждает более общую взаимосвязь между количеством точек в множестве точек общего положения и его наибольшим подмножеством, образующим выпуклый многоугольник , а именно, что наименьшее количество точек, для которых любое расположение общего положения содержит выпуклое подмножество $n$ очков это $2^{n-2}+1$ . Это остается недоказанным, но известны менее точные границы.

Большие полигоны

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

Эрдеш и Секерес (1935) доказали следующее обобщение:

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

Доказательство появилось в той же статье, в которой доказывается теорема Эрдеша–Секереша о монотонных подпоследовательностях в числовых последовательностях.

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

$f (3) = 3$ , тривиально.
$ж (4) = 5$ . ^[3]
$ж (5) = 9$ . ^[4] набор из восьми точек без выпуклого пятиугольника На рисунке показан $, демонстрирующий, что f (5) > 8$ ; более сложная часть доказательства — показать, что каждый набор из девяти точек общего положения содержит вершины выпуклого пятиугольника.
$ж (6) = 17$ . ^[5]
Значение $f (N)$ неизвестно для всех $N > 6$ . Согласно результату Эрдеша и Секереша (1935) , $(N) конечно$ известно, что $для всех конечных N.$ f

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

Набор из шестнадцати точек общего положения без выпуклого шестиугольника.

$f(N)=1+2^{N-2}\quad {\text{for all }}N\geq 3.$ Позже они доказали, построив явные примеры, что ^[6] $f(N)\geq 1+2^{N-2}.$ В 2016 году Эндрю Сук ^[7] показали, что для $N \geq 7$ $f(N)\leq 2^{N+o(N)}.$

Сук фактически доказывает, что для достаточно большого N $f(N)\leq 2^{N+6N^{2/3}logN}.$

Впоследствии это было улучшено до: ^[8]

$f(N)\leq 2^{N+O({\sqrt {NlogN}})}.$

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

Возникает также вопрос о том, имеет ли какое-либо достаточно большое множество точек общего положения «пустой» выпуклый четырехугольник, пятиугольник и т. д.то есть тот, который не содержит других входных точек. Исходное решение проблемы счастливого конца можно адаптировать так, чтобы показать, что любые пять точек в общем положении имеют пустой выпуклый четырехугольник, как показано на рисунке, а любые десять точек в общем положении имеют пустой выпуклый пятиугольник. ^[9] Однако существуют сколь угодно большие множества точек общего положения, не содержащие пустого выпуклого семиугольника . ^[10]

Долгое время вопрос о существовании пустых шестиугольников оставался открытым, но Николас (2007) и Геркен (2008) доказали, что каждое достаточно большое множество точек общего положения содержит выпуклый пустой шестиугольник. Более конкретно, Геркен показал, что необходимое количество очков не превышает f (9) для той же функции f, определенной выше, а Николас показал, что необходимое количество очков не превышает f (25). Валтр (2008) предлагает упрощенное доказательство Геркена, которое, однако, требует большего количества баллов: f (15) вместо f (9). Необходимо не менее 30 баллов; существует набор из 29 точек общего положения, в которых нет пустого выпуклого шестиугольника. ^[11] Наконец, на этот вопрос ответили Heule & Scheucher (2024) , которые показали, используя подход решения SAT, что действительно каждый набор из 30 точек в общем положении содержит пустой шестиугольник.

Связанные проблемы

Задача нахождения наборов из n точек, минимизирующих количество выпуклых четырёхугольников, эквивалентна минимизации числа пересечений в прямолинейном рисунке графа полного . Число четырехугольников должно быть пропорционально четвертой степени n , но точная константа неизвестна. ^[12]

Несложно показать, что в многомерных евклидовых пространствах достаточно большие множества точек будут иметь подмножество из k точек, образующее вершины выпуклого многогранника , для любого k, большего размерности: это непосредственно следует из существования выпуклых многогранников. k -угольников в достаточно больших плоских множествах точек путем проектирования многомерного множества точек в произвольное двумерное подпространство. Однако количество точек, необходимых для поиска k точек в выпуклом положении, может быть меньше в более высоких измерениях, чем в плоскости, и можно найти подмножества с более сильными ограничениями. В частности, в d измерениях каждые d + 3 точки общего положения имеют подмножество из d + 2 точек, которые образуют вершины циклического многогранника . ^[13] В более общем смысле, для каждых d и k > d существует число m ( d , k ) такое, что каждый набор из m ( d , k ) точек общего положения имеет подмножество из k точек, образующих вершины соседнего многогранника . ^[14]

Примечания

^ Мир обучения и чисел - умножить на два , Майкл Коулинг , The Sydney Morning Herald , 7 ноября 2005 г., цитировано 4 сентября 2014 г.
^ В этом контексте общее положение означает, что никакие две точки не совпадают и никакие три точки не лежат на одной прямой.
^ Это была первоначальная проблема, доказанная Эстер Кляйн.
↑ Согласно Erdős & Szekeres (1935) , это было впервые доказано Э. Макаем; первое опубликованное доказательство появилось в работе Kalbfleisch, Kalbfleisch & Stanton (1970) .
^ Это было доказано Секересом и Петерсом (2006) . Они провели компьютерный поиск, который исключил все возможные конфигурации из 17 точек без выпуклых шестиугольников, исследовав при этом лишь небольшую часть всех конфигураций.
^ Эрдеш и Секерес (1961)
^ Сук (2016) . См. биномиальный коэффициент и обозначение большого O для обозначений, используемых здесь, а также числа Каталана или приближение Стирлинга для асимптотического разложения.
^ Холмсен и др. (2020) .
^ Харборт (1978) .
^ Хортон (1983)
^ Овермарс (2003) .
^ Шайнерман и Уилф (1994)
^ Грюнбаум (2003) , Ex. 6.5.6, стр.120. Грюнбаум приписывает этот результат частному сообщению Михи А. Перлеса.
^ Грюнбаум (2003) , Ex. 7.3.6, с. 126. Этот результат получается путем применения аргумента теории Рэмсея, аналогичного оригинальному доказательству Секереса, вместе с результатом Перлеса для случая k = d + 2.

Ссылки

Чанг, Франция ; Грэм, Р.Л. (1998), «Вынужденно выпуклые n-угольники на плоскости», Дискретная и вычислительная геометрия , 19 (3): 367–371, doi : 10.1007/PL00009353
Эрдеш, П .; Секерес, Г. (1935), «Комбинаторная задача в геометрии» , Compositio Mathematica , 2 : 463–470.
Эрдеш, П .; Секерес, Г. (1961), «О некоторых экстремальных задачах элементарной геометрии», Ann. унив. наук. Будапешт. Секта Этвёша. Математика. , 3–4 : 53–62 ; перепечатано в Эрдеш, П. (1973), Спенсер, Дж. (редактор), Искусство счета: Избранные произведения , Кембридж, Массачусетс: MIT Press, стр. 680–689.
Геркен, Тобиас (2008), «Пустые выпуклые шестиугольники в наборах плоских точек», Дискретная и вычислительная геометрия , 39 (1–3): 239–272, doi : 10.1007/s00454-007-9018-x
Грюнбаум, Бранко (2003), Кайбель, Фолькер; Клее, Виктор ; Циглер, Гюнтер М. (ред.), Выпуклые многогранники , Тексты для выпускников по математике, том. 221 (2-е изд.), Springer-Verlag , ISBN 0-387-00424-6
Харборт, Хейко (1978), «Выпуклые пятиугольники в наборах плоских точек», Elements of Mathematics , 33 (5): 116–118
Хойле, Марин Дж. Х.; Шойхер, Манфред (2024), «Счастливый конец: пустой шестиугольник в каждом наборе из 30 точек», у Финкбайнера, Бернд; Ковач, Лаура (ред.), Инструменты и алгоритмы для построения и анализа систем , Конспекты лекций по информатике, том. 14570, Springer-Verlag, стр. 61–80, arXiv : 2403.00737 , doi : 10.1007/978-3-031-57246-3_5.
Холмсен, Андреас Ф.; Мохаррад, Хосейн Нассаджян; Пах, Янош ; Тардос, Габор (2020), «Два расширения проблемы Эрдеша-Секереша», Журнал Европейского математического общества (JEMS) , 22 (12): 3981–3995, arXiv : 1710.11415 , doi : 10.4171/001/000 , MR . 4176784
Хортон, JD (1983), «Множества без пустых выпуклых 7-угольников», Canadian Mathematical Bulletin , 26 (4): 482–484, doi : 10.4153/CMB-1983-077-8 , S2CID 120267029
Калбфляйш, доктор медицинских наук; Кальбфляйш, Й.Г .; Стэнтон, Р.Г. (1970), "Комбинаторная задача о выпуклых областях", Proc. Луизианская конференция. Комбинаторика, теория графов и вычисления , Congressus Numerantium, vol. 1, Батон-Руж, Луизиана: Университет штата Луизиана, стр. 180–188.
Клейтман, диджей ; Пахтер, Л. (1998), «Нахождение выпуклых множеств среди точек на плоскости» (PDF) , Discrete and Computational Geometry , 19 (3): 405–410, doi : 10.1007/PL00009358 , заархивировано из оригинала (PDF) на сайте 04 февраля 2022 г. , получено 23 сентября 2019 г.
Моррис, В.; Солтан, В. (2000), «Проблема Эрдеша-Секереша о точках в выпуклом положении — обзор», Бюллетень Американского математического общества , 37 (4): 437–458, doi : 10.1090/S0273-0979-00- 00877-6
Николас, Карлос М. (2007), «Теорема о пустом шестиугольнике», Дискретная и вычислительная геометрия , 38 (2): 389–397, doi : 10.1007/s00454-007-1343-6
Овермарс, М. (2003), «Нахождение наборов точек без пустых выпуклых 6-угольников», Дискретная и вычислительная геометрия , 29 (1): 153–158, doi : 10.1007/s00454-002-2829-x
Петерсон, Иварс (2000), «Самолеты Будапешта» , MAA Online , заархивировано из оригинала 2 июля 2013 г.
Шайнерман, Эдвард Р .; Уилф, Герберт С. (1994), «Прямолинейное число пересечений полного графа и «задача четырех точек» геометрической вероятности Сильвестра», American Mathematical Monthly , 101 (10), Математическая ассоциация Америки: 939–943, doi : 10.2307/2975158 , JSTOR 2975158
Сук, Эндрю (2016), «О задаче выпуклого многоугольника Эрдеша – Секереса», J. Amer. Soc , 30 (4):1047–1053, arXiv : 1604.08657 , doi : 10.1090/jams/869 , S2CID 15732134.
Секерес, Г. ; Петерс, Л. (2006), «Компьютерное решение 17-точечной задачи Эрдеша-Секереша» , ANZIAM Journal , 48 (2): 151–164, doi : 10.1017/S144618110000300X , заархивировано из оригинала 13 декабря 2019 г. , получено 5 января 2007 г.
Тот, Г.; Валтр, П. (1998), «Заметки о теореме Эрдеша-Секереша», Дискретная и вычислительная геометрия , 19 (3): 457–459, doi : 10.1007/PL00009363
Тот, Г.; Валтр, П. (2005), «Теорема Эрдеша-Секереша: верхние оценки и связанные с ними результаты», в Гудмане, Джейкоб Э .; Пах, Янош ; Вельцль, Эмо (ред.), Комбинаторная и вычислительная геометрия (PDF) , Публикации Научно-исследовательского института математических наук, том. 52, Cambridge University Press, стр. 557–568, заархивировано из оригинала (PDF) 28 июля 2019 г. , получено 28 февраля 2015 г.
Валтр, П. (2008), «О пустых шестиугольниках», Гудман, Джейкоб Э .; Пах, Янош ; Поллак, Ричард (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя: Совместная летняя исследовательская конференция AMS-IMS-SIAM, 18–22 июня 2006 г., Сноуберд, Юта , Современная математика, том. 453, Американское математическое общество, стр. 433–442, ISBN. 9780821842393

Внешние ссылки

[1] Мир обучения и чисел - умножить на два , Майкл Коулинг , The Sydney Morning Herald , 7 ноября 2005 г., цитировано 4 сентября 2014 г.

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

[3] Это была первоначальная проблема, доказанная Эстер Кляйн.

[4] Согласно Erdős & Szekeres (1935) , это было впервые доказано Э. Макаем; первое опубликованное доказательство появилось в работе Kalbfleisch, Kalbfleisch & Stanton (1970) .

[5] Это было доказано Секересом и Петерсом (2006) . Они провели компьютерный поиск, который исключил все возможные конфигурации из 17 точек без выпуклых шестиугольников, исследовав при этом лишь небольшую часть всех конфигураций.

[6] Эрдеш и Секерес (1961)

[7] Сук (2016) . См. биномиальный коэффициент и обозначение большого O для обозначений, используемых здесь, а также числа Каталана или приближение Стирлинга для асимптотического разложения.

[FOOTNOTEHolmsenMojarradPachTardos2020-8] Холмсен и др. (2020) .

[9] Харборт (1978) .

[10] Хортон (1983)

[11] Овермарс (2003) .

[12] Шайнерман и Уилф (1994)

[13] Грюнбаум (2003) , Ex. 6.5.6, стр.120. Грюнбаум приписывает этот результат частному сообщению Михи А. Перлеса.

[14] Грюнбаум (2003) , Ex. 7.3.6, с. 126. Этот результат получается путем применения аргумента теории Рэмсея, аналогичного оригинальному доказательству Секереса, вместе с результатом Перлеса для случая k = d + 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]