Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Об альбоме Фреда Фрита см. The Happy End Problem .
Проблема счастливого конца: каждый набор из пяти точек общего положения содержит вершины выпуклого четырехугольника

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

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

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

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

Гипотеза Эрдеша – Секереса точно устанавливает более общую взаимосвязь между количеством точек в множестве точек общего положения и его наибольшим выпуклым многоугольником, а именно, что наименьшее количество точек, для которых любое устройство общего положения содержит выпуклое подмножество точек . Это остается недоказанным, но известны менее точные оценки.

Большие полигоны [ править ]

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

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

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

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

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

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

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

Позже они доказали, построив явные примеры, что

[6]

но самая известная верхняя граница при N ≥ 7 равна

[7]

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

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

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

Связанные проблемы [ править ]

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

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

Заметки [ править ]

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

Ссылки [ править ]

  • Чанг, ФРК ; Грэм, Р.Л. (1998), "Принудительно выпуклые n-угольники на плоскости", Дискретная и вычислительная геометрия , 19 (3): 367–371, DOI : 10.1007 / PL00009353.
  • Erdős, P .; Секерес, Г. (1935), "Комбинаторная задача геометрии" , Compositio Mathematica , 2 : 463–470.
  • Erdős, P .; Секерес, Г. (1961), "О некоторых экстремальных задачах элементарной геометрии", Ann. Univ. Sci. Будапешт. Eötvös Sect. Математика. , 3–4 : 53–62. Перепечатано в: Erdős, P. (1973), Spencer, J. (ed.), The Art of Count: Selected Writings , Cambridge, MA: MIT Press, pp. 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), «Konvexe Fünfecke in ebenen Punktmengen», Elemente der Mathematik , 33 (5): 116–118.
  • Horton, JD (1983), "Множества с не пустыми выпуклыми 7-угольников", Canadian математический вестник , 26 (4): 482-484, DOI : 10,4153 / CMB-1983-077-8.
  • Kalbfleisch, JD; Kalbfleisch, JG ; Стэнтон, RG (1970), "Комбинаторная задача на выпуклых областях", Proc. Louisiana Conf. Комбинаторика, теория графов и вычисления , Congressus Numerantium, 1 , Батон-Руж, штат Луизиана: Университет штата Луизиана, стр. 180–188.
  • Клейтман, диджей ; Пахтер, Л. (1998), «Нахождение выпуклых множеств среди точек на плоскости» (PDF) , Дискретная и вычислительная геометрия , 19 (3): 405–410, DOI : 10.1007 / PL00009358.
  • Моррис, В .; Солтан, В. (2000), "Проблема Эрдеша-Шекереса по точкам выпуклого обследования позиционно-A", Бюллетень Американского математического общества , 37 (04): 437-458, DOI : 10,1090 / S0273-0979-00- 00877-6.
  • Николас, Карлос М. (2007), "Теорема пустой шестиугольник", Дискретная и вычислительная геометрия , 38 (2): 389-397, DOI : 10.1007 / s00454-007-1343-6.
  • Овермарса, M. (2003), "Нахождение множества точек , не пусто выпуклых 6-угольников", Дискретные и вычислительной геометрии , 29 (1): 153-158, DOI : 10.1007 / s00454-002-2829-х.
  • Петерсон, Иварс (2000), "Самолеты Будапешта" , MAA Online , заархивировано из оригинала 2 июля 2013 г..
  • Шайнерман, Эдвард Р .; Уилф, Герберт С. (1994), «Прямолинейное число пересечения полного графа и« четырехточечная проблема »Сильвестра геометрической вероятности», American Mathematical Monthly , Mathematical Association of America, 101 (10): 939–943, doi : 10.2307 / 2975158 , JSTOR  2975158.
  • Сук, Эндрю (2016), "О проблеме выпуклого многоугольника Эрдеша – Секереша", J. Amer. Математика. Soc. , Arxiv : 1604,08657 , DOI : 10,1090 / джемы / 869.
  • Секерес, Г .; Петерс, L. (2006), "Компьютерное решение 17-бальной задачи Erdős-Шекереса" , ANZIAM Journal , 48 (02): 151-164, DOI : 10,1017 / S144618110000300X.
  • Tóth, G .; Валтр П. (1998), «Заметка о теореме Эрдеша-Секереса», Дискретная и вычислительная геометрия , 19 (3): 457–459, DOI : 10.1007 / PL00009363.
  • Tóth, G .; Валтр П. (2005), «Теорема Эрдеша-Секереса: оценки сверху и связанные результаты», в Goodman, Jacob E .; Пах, Янош ; Вельцль, Эмо (ред.), Комбинаторная и вычислительная геометрия (PDF) , Публикации научно-исследовательского института математических наук, 52 , Cambridge University Press, стр. 557–568.
  • Валтр, П. (2008), «О пустых шестиугольниках», в Goodman, Jacob E .; Пах, Янош ; Ричард Поллак (ред.), Опросы по дискретной и вычислительной геометрии: двадцать лет спустя: совместная летняя исследовательская конференция AMS-IMS-SIAM, 18-22 июня 2006 г., Snowbird, Юта , Contemporary Mathematics, 453 , American Mathematical Society, стр. 433–442, ISBN 9780821842393.

Внешние ссылки [ править ]

  • Проблема счастливого конца и теоретико-Рамсеевское доказательство теоремы Эрдеша-Секереса о PlanetMath
  • Вайсштейн, Эрик В. "Проблема счастливого конца" . MathWorld .