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

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]

Navigation