Каждое из ребер полного графа с 17 вершинами покрашено в один из трех цветов. Докажите, что есть три вершины, все ребра между которыми - одного цвета.

задан 2 Апр '14 23:14

изменен 2 Апр '14 23:20

Deleted's gravatar image


126

Это широко известная задача (из серии "задача Рамсея"). Сначала надо доказать это утверждение для 6 вершин и 2 цветов. Делается это за счёт того, что из любой вершины исходят три одноцветных. А для 17 вершин и 3 цветов из вершины (любой) исходят по меньшей мере 6 рёбер одного цвета. После чего задача сводится к предыдущей: рассматривается граф с вершинами в концах этих рёбер. См. также здесь.

(3 Апр '14 0:28) falcao

@falcao: а можно сразу для 17 вершин теорему Рамсея применить?

(3 Апр '14 13:39) kirill1771

@kirill1771: а в какой формулировке Вы берёте теорему Рамсея? Она в общем виде гарантирует некоторую оценку, без уточнения, чему она равна. В любом случае придётся доказывать, что число 17 подходит. То есть это не свести к фактам общего характера, потому что сами они доказываются через тот приём, который здесь применяется.

(3 Апр '14 14:04) falcao

@falcao: формулировка такая: "Пусть даны числа $%a_1,a_2...a_n$%. Тогда существует такое число $%R$%, что, как бы мы ни покрасили рёбра полного графа на $%R$% вершинах в $%n$% цветов, найдётся либо полный подграф 1-го цвета на $%a_1$% вершинах, либо полный подграф 2-го цвета на $%a_2$% вершинах, … либо полный подграф $%n$%-го цвета на $%a_n$% вершинах."

(3 Апр '14 14:28) kirill1771

@kirill1771: это один из частных случаев общей теоремы Рамсея. Но из него не следует, что то число, о котором идёт речь, равно именно 17. В таком виде теорема гарантирует только то, что при достаточно большом числе вершин графа всё будет выполняться. Так или иначе, конкретный анализ здесь должен присутствовать.

(3 Апр '14 18:01) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×599

задан
2 Апр '14 23:14

показан
1482 раза

обновлен
3 Апр '14 18:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru