Полный граф с рёбрами 3 цветов

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 22 май 2021, 14:42

Задача с регаты 2021. Не удалось решить.
Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный $k$, такой что для любой раскраски всегда можно выбрать $k$ вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Какие идеи?

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 22 май 2021, 15:34

Обозначим N(k,l,m) число вершин, для которых верно,что либо будет полный подграф из k с первым цветом,либо полный из l вершин со вторым цветом, либо полный из m третьего цвета. Рекурсия по уменьшению суммы k+l+m: Берем одну вершину . Из остальных N(k,l,m)-1 найдется либо N1 которые с ним 1-го цвета, либо N2, которые с ним 2-го цвета, либо N3, которые с ним 3-го цвета. Неравенства:
[math]
[math]
[math]
Чтобы было верно, что найдется, надо [math] Вот и обсчитывать весь такой "тетраэдр Паскаля",получим точный ответ

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 22 май 2021, 16:58

zykov писал(а):Задача с регаты 2021. Не удалось решить.
Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный $k$, такой что для любой раскраски всегда можно выбрать $k$ вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Какие идеи?
Да блин исходная задача-то другая. Из любой в любую добраться,хоть бы с пересадками. Неправильно прочитано мной,и не только мной. Давайте решим и эту (на теорию Рамсея) и исходную

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 22 май 2021, 17:04

Их условие:
В стране 2000 городов, любые два соединены самолётом, поездом или пароходом. Для какого наибольшего k гарантированно можно выбрать k городов и один из видов транспорта так, чтобы из любого из этих k городов можно было этим видом транспорта добраться до любого другого?

Их ответ: 1000
Последний раз редактировалось zykov 22 май 2021, 17:50, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 22 май 2021, 17:06

Вообще, честно говоря - жестко, за 2 часа 25 подобных задач...
Тут над каждой надо изрядно подумать (может кроме некоторых по 100).

Вот все задачи:
Tinkoff2021_Regata_First_step.pdf
(189.85 KiB) Загружено 464 раз

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 22 май 2021, 18:17

zykov писал(а):Source of the post чтобы из любого из этих k городов можно было этим видом транспорта добраться до любого другого?

Я понимал так, что для каждого города есть рейс в другой город из этих k.

Но можно понять, что можно добратся с несколькими пересадками.
Ещё можно тогда понять, что добратся вообще до любого из 2000 городов, но этот вариант отпадает как тривиальный (может быть 3 города, так что из каждого только один вид транспорта и для этих 3 городов все 3 разных вида).

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 22 май 2021, 20:01

Да.
В первой формулировке это чистая теорема Рамсея.
Нужно найти максимальный $k$, такой что $R(k,k,k) \leq 2000$.
Но никто не знает значений $R$ даже для маленьких $k$, кроме ну совсем маленьких (0, 1, может 2).
(Найти перебором их можно, но это нереально долго.)
There are (up to symmetries) only two non-trivial multicolour Ramsey numbers for which the exact value is known, namely R(3, 3, 3) = 17 and R(3, 3, 4) = 30.


Видимо имелась ввиду вторая формулировка - минимум от максимума размеров связных графов по трём цветам и по всем раскраскам.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 22 май 2021, 20:21

zykov писал(а):Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный $k$, такой что для любой раскраски всегда можно выбрать $k$ вершин, так чтобы все рёбра между этими вершинами были одного цвета.

Код: Выбрать все

(k=2)   l   m   N
2   3   3   6
2   3   4   10
2   4   4   20
2   4   5   35
2   5   5   70
2   3   5   15
         
k   l   m   N
3   3   3   17
3   3   4   36
3   4   4   91
4   4   4   272
3   3   5   65
3   4   5   190
4   4   5   651
3   5   5   449
4   5   5   1750
5   5   5   5251

Наоборот в теории Рамсея белых пятен нет,обращайтесь)). Обозначения введены мной выше. Еще одно: N(l,m)=N(2,l,m) двухместная функция
Конечно везде полная симметрия по аргументам.
[math] -отсюда мой первый блок вычислений.
Второй блок вычислений приводит по формуле [math]
(эта формула необходима и достаточна,так как выдает и способ построения контрпримеров.И как видите N(3,3,4)=36 а не 30)
к значениям N(4,4,4)=272, но N(5,5,5)=5251, почему я и защищал интуитивно 4, но также вероятным считал 5

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 23 май 2021, 09:53

Ian писал(а):Наоборот в теории Рамсея белых пятен нет,обращайтесь)).
....
[math]
(эта формула необходима и достаточна,так как выдает и способ построения контрпримеров.И как видите N(3,3,4)=36 а не 30)
...

Статья в вики https://ru.wikipedia.org/wiki/Теорема_Рамсея обсуждалась на старом E-S лет 10 назад, тогда много заинтересованных людей как-то пришли к выводу, что в формуле равенство , по крайней мере для двухместной N(l,m) и значит белых пятен нет...Я это запомнил и базировался. Надо еще проверять, конечно.
Так или иначе, то что в задаче Рамсея N(4,4,4) не больше 272 это точно, ну и легкие неравенства N(5,5,5)>2*N(4,5,5)>4*N(4,4,5)>8*N(4,4,4) ну и какое должно быть точное значение N(4,4,4) чтобы там получалось не больше 2000. 249- маловато

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Полный граф с рёбрами 3 цветов

Сообщение peregoudov » 25 май 2021, 11:51

Поиск по старому форуму (раздел Математика) по ключевому слову "рамсея" выдает только две темы:

Определенный интеграл нашел
Многоугольник

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Полный граф с рёбрами 3 цветов

Сообщение zykov » 25 май 2021, 12:43

Ian писал(а):Source of the post Наоборот в теории Рамсея белых пятен нет

Не знаю, про какие "белые пятна" говорите.
Факт, что точно посчитать например $R(4,4,4)$ нереально долго.
Согласен, что скорее всего можно малой кровью получить грубые оценки сверху и снизу.
И этого может быть достаточно, если одна оценка сверху не более 2000, а следующая оценка снизу больше 2000.

А что собственно по их задаче, где ответ 1000, где речь про размер связных графов?

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 27 май 2021, 10:10

peregoudov писал(а):Поиск по старому форуму (раздел Математика) по ключевому слову "рамсея" выдает только две темы:

Определенный интеграл нашел
Многоугольник
Некорректно сработал поиск. одна тема там не по делу. И главное была еще личная переписка почти с каждым, только важные позитивные результаты из нее потом выносились на всеобщее обозрение. С одной стороны, вроде бы убедились, что рекурсия дает не оценку а критерий. С другой стороны - и в этой теории и в комбинаторике вообще столько правдоподобных но неверных рассуждений проскакивает. И то что не вынесли в общую тему значит все-таки сомневались.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 27 май 2021, 10:16

Есть пример где все связные компоненты всех цветов не более 1000. Разобьаем вершины на 4 группы по 500, A c B, С с D только одним цветом, A с С, B с D только другим, А с D, В с С третьим. Внутри групп неважно.

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Полный граф с рёбрами 3 цветов

Сообщение peregoudov » 27 май 2021, 13:12

Ian писал(а):Source of the post И главное была еще личная переписка почти с каждым
Ну, вашу личную переписку я по понятным причинам скачать не смог (только свою личную). Так что всего того великолепия, о котором вы пишете, ссылаясь на старый форум, к сожалению, не сохранилось... Впрочем, если вы уговорите Соула отдать базу данных...

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Полный граф с рёбрами 3 цветов

Сообщение Ian » 17 июн 2021, 07:30

Ian писал(а):Есть пример где все связные компоненты всех цветов не более 1000. Разобьаем вершины на 4 группы по 500, A c B, С с D только одним цветом, A с С, B с D только другим, А с D, В с С третьим. Внутри групп неважно.

Продолжение.Предположим, любая связная компонента любого цвета менее 1000. Тогда для каждого цвета компонент как минимум три . Каждой вершине присвоим тройку (i,j,k)- номера компонент, которым она принадлежит. Могут быть вершины с одинаковыми тройками. Но у любых двух вершин не могут быть полностью различные тройки,хотя бы одним цветом они соединены. Рассмотрим клетки [math], не менее 3х3 клеток.Каждая вершина в одной из клеток, и клетки с несовпадающими и строкой, и столбцом -имеют одинаковое k .Тогда все клетки имеют одинаковое k, или этому мешает большое количество пустых клеток (тут нестрого)
В общем рассуждения приводят к оптимальной таблице (i,j) 2х2, а k одинаково для клеток одной диагонали, в клетках по 500 вершин
Или ее можно представить как трехмерную таблицу 2х2х2, в которой непустые клетки строго в шахматном порядке


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 15 гостей