Проблема счастливого конца - Happy ending problem

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ Displaystyle f (N) = 1 + 2 ^ {N-2} quad { mbox {для всех}} N geq 3.}

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

{ Displaystyle е (N) geq 1 + 2 ^ {N-2},}

^[6]

но самая известная верхняя граница, когда N ≥ 7 - это

{ Displaystyle f (N) leq 2 ^ {N + o (N)}.}

^[7]

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

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

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

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

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

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

Примечания

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

внешняя ссылка

[1] Мир обучения и чисел - умноженный на два, Майкл Коулинг, Sydney Morning Herald, 2005-11-07, цитировано 2014-09-04

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

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

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

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

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

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

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

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

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

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

[12] Грюнбаум (2003), Бывший. 6.5.6, стр.120. Грюнбаум связывает этот результат с личным сообщением Мики А. Перлес.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]