Взгляд на задачу о знакомствах с точки зрения теории графов.

[pcyanide]

Хорошо известен следующий факт: «Из 6 человек найдется либо трое попарно знакомых, либо трое попарно незнакомых.» (Классическое доказательство можно найти без проблем.)

Попытался доказать с помощью теоремы Мантеля (Турана) такими рассуждениями.

Каждому человеку поставим в соответствие вершину полного графа. Синими ребрами соединяем знакомых, красными незнакомых. Полный граф имеет $\binom{6}{2} = 15 $ ребер. Если утверждение неверно, графы, составленные из синих и красных ребер не имеют треугольников, поэтому согласно теореме Мантеля (Турана), число синих и красных ребер не больше $\left(\frac{6}{2}\right)^2=9$ каждое, что в сумме дает дает не более 18 ребер. Противоречия, как видно не получается. Действительно, максимум в теореме Мантеля всегда чуть больше половины общего количества ребер, даже если в графе нечетное количество вершин.

Может быть тогда «факт о знакомстве» является следствием какого-то другого положения из теории графов? Неужели эта задача не имеет аналогов?

[provincialka]

Так-то это частный случай чисел Рамсея. Связаны ли они ещё с чем-нибудь не знаю... Но там есть некая теория, незаконченная.

[grizzly]

pcyanide в сообщении #1275019 писал(а):

Неужели эта задача не имеет аналогов?

Разные задачи про знакомства? таких немало. Посмотрите, для примера, эту тему. Там тоже школьная задача про знакомства (но посложнее) и решения были самые разные -- в том числе с какими-то графами (без необходимости использовать тяжёлую артиллерию).

Ещё вот эта статья из Кванта может Вас заинтересовать.

[pcyanide]

Спасибо, provincialka, а также grizzly за ссылку на статью из «Кванта». Действительно, речь идет о числах Рамсея.

Поставим вопрос таким образом: для заданного $k$ найти $n$, что из любых $n$ человек найдется либо $k$ попарно знакомых, либо $k$ попарно незнакомых.

Ответ на это дает число Рамсея $R(k,k)$ и теорема Рамсея, утверждающая, в частности, что такие числа существуют для любого $k$. В упомянутой статье М.Гарднера приводятся значения R(3,3)=6, R(4,4)=18, $R(5,5)\in[38,67]$. Статья в Википедии приводит доказательство теоремы, а также современную, более точную оценку: $R(5,5)\in[43,48]$, кроме того $R(6,6)\in[102,165]$, $R(7,7)\in[205,540]$, и т.д.

Не понимаю одно: поскольку границы для чисел известны, и количество возможных графов из заданного количества вершин конечно, почему бы не поручить это компьютеру? В наш век субсветовых компьютерных скоростей получить ответ удастся быстрее, чем найти очередной bit coin . Конечно, не решает задачу в общем виде, но все же может навести на мысль. Никто ведь не жалеет об уйме компьютерного времени (когда оно было довольно дорогим!), затраченного, чтобы опровергнуть большую теорему Ферма (а если нет, то увеличить показатель степени, для которого она верна), прежде чем она была доказана.

Между прочим, в указанной статье из Википедии упоминается попытка (причем, судя по описанию, успешная) в 1997 году с помощью компьютера доказать, что R(5,5)=43. Однако, по-видимому никто не воспринимает это всерьез, если по-прежнему в таблице нет точного значения.

Кстати, откуда следует, что R(4,4)=18 ? Есть простое доказательство?

[Sender]

pcyanide в сообщении #1275905 писал(а):

наш век субсветовых компьютерных скоростей получить ответ удастся быстрее, чем найти очередной bit coin .

Ну да, сколько там рёбер в полном 43-вершинном графе, 903? Всего-то перебрать $2^{903}$ различных графов.

[pcyanide]

Sender в сообщении #1275929 писал(а):

Ну да, сколько там рёбер в полном 43-вершинном графе, 903? Всего-то перебрать $2^{903}$ различных графов.

Примерно такие же доводы в лекции Райгородского. Однако, если организовать дело так же хорошо, как поиск bit coins, (каждому компьютеру по куску и использованием графических карт), то должно получиться. Наверное единственная проблема — получить грант но это дело. Еще в 1995 году с помощью компьютера было доказано, что $R(4,5) = 25$

Кстати, лекция Райгородского очень хороша для начинающих (не знаю, какая там аудитория, по-видимому, школьники, судя по тому с каким скептицизмом докладчик упоминает натуральные логарифмы). Все настолько просто, что иногда приходилось пропускать куски, чтобы не уснуть . Однако при все этом он ухитрился доказать основные формулы, такие как $R(s,t) \le R(s,t-1)+R(s-1,t)$ и $R(s,t) \le C_{s+t-2}^{t-1}$.

[Sender]

pcyanide в сообщении #1275943 писал(а):

каждому компьютеру по куску и использованием графических карт

Сколько всего компьютеров в мире? Ну хорошо, каждому перебирать не $2^{903}$, а жалкие $2^{870}$ графов.

-- Пн дек 18, 2017 11:43:38 --

Для начала можно потренироваться на шахматах, ведь, если верить вики, там не более, чем $2^{155}$ уникальных позиций.

[grizzly]

pcyanide в сообщении #1275905 писал(а):

Кстати, откуда следует, что R(4,4)=18 ? Есть простое доказательство?

Ну если на той же вики-странице показано, что $R(4,4)\le 18$ и дана ссылка на граф $R(4,4,17)$, куда уж проще. Другое дело, что найти эту раскраску было непросто, наверное.

pcyanide в сообщении #1275943 писал(а):

если организовать дело [...] то должно получиться.

Поскольку статьи по поиску чисел Рамсея большей частью основаны на алгоритмах, в них зачастую приводятся оценки вычислительной трудоёмкости в CPU-годах, посмотрите. Пока что мозги, которые улучшают эти алгоритмы и работают на биотопливе, обходятся дешевле.

[pcyanide]

grizzly в сообщении #1275949 писал(а):

Ну если на той же вики-странице показано, что $R(4,4)\le 18$ и дана ссылка на граф $R(4,4,17)$, куда уж проще.

Действительно! Мне надо было просто внимательнее читать. Спасибо.