2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Доказательство теоремы Эрдёша о выпуклых многоугольниках
Сообщение09.03.2015, 09:15 

(Оффтоп)

Многоуважаемый Секереш просто не поместился в заголовок темы

Всем известная теорема: для любого $k$ существует такое $n$, что любые $n$ точек на плоскости в общем положении содержат выпуклый $k$-угольник.
Пытаюсь её доказать. Прошу проверить правильность и натолкнуть на мысль. В книге Грэхема рекомендуется использовать теорему Рамсея. Придумалось что-то такое:
по теореме Рамсея, для любого $k$ существует такое $n$, что для любой 2-раскраски 4-элементных множеств хотя бы в одном $k$-элементном множестве все 4-элементные подмножества одноцветны.
Дальше берём нужное $n$ и красим 4-элементные подмножества. Красим в синий цвет выпуклые четырёхугольники, а в красный - остальные четвёрки точек. Значит, у нас есть либо красное в смысле четвёрок $k$-подмножество, либо синее. Но красных в смысле четвёрок быть не может при $k \ge 5$ потому что пять точек всегда содержат выпуклый четырёхугольник.
Таким образом, гарантированно есть синее подмножество, и теорема доказана.

Верно ли я рассуждаю?

 
 
 
 Re: Доказательство теоремы Эрдёша о выпуклых многоугольниках
Сообщение09.03.2015, 17:02 
Аватара пользователя
fractalon в сообщении #987729 писал(а):
...
по теореме Рамсея, для любого $k$ существует такое $n$, что для любой 2-раскраски 4-элементных множеств хотя бы в одном $k$-элементном множестве все 4-элементные подмножества одноцветны.
...
Это прямо в книге Грэхема такая "крутая" формулировка теоремы написана? :shock:

 
 
 
 Re: Доказательство теоремы Эрдёша о выпуклых многоугольниках
Сообщение09.03.2015, 17:40 
Ой, опечатался...
Хотя, я думаю, и так все знают, но ради исправления переформулирую чётко:
$\forall k \exists n$ такое, что в любой 2-цветной раскраске 4-элементых подмножеств $n$-элементного множества оказывается, что в некотором $k$-подмножестве все 4-элементные подмножества одноцветны.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group