Как математики сдвинули с мертвой точки диагональное число Рамсея

N+1Наука

Бери ниже

Как математики сдвинули с мертвой точки диагональное число Рамсея

Фёдор Петров

В комбинаторике прямо сейчас происходит много весьма интересных событий, это одна из самых бурно развивающихся областей математики. Но среди них отдельно выделяется новая работа Марсело Кампоса, Саймона Гриффитса, Роберта Морриса (Рио-де-Жанейро) и Джулиана Сахасрабуде (Кембридж), посвященная оценке чисел Рамсея. В чем с этими числами проблема и как ее недавно решили, рассказывает математик Фёдор Петров, профессор СПбГУ и ведущий научный сотрудник ПОМИ РАН.

Числа Рамсея

Чтобы определить числа Рамсея, начнем с задачи, которую решают на школьных математических кружках: докажите, что из любых шести людей найдутся трое попарно знакомых или трое попарно незнакомых (будем считать, что знакомство взаимно).

Возьмем любого из шестерых — назовем его Иваном. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с Иваном, если нет — то тройку попарно незнакомых между собой. Если же Иван знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.

На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединенные ребрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.

Графы для R(3,3) = 6 и R(3,3) = 5. john doe

А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это доказал английский математик Фрэнк Пламптон Рамсей в 1930 году. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n,k) и называется числом Рамсея. Выше мы установили, что R(3,3)=6.

У этого графа R(4,4) = 18 вершин.
Следовательно, здесь найдутся 4 вершины соединенные либо только красными, либо только синими ребрами. Попробуйте найти такую четверку! john doe
Таких четверок в этом графе несколько, вот два из них. john doe

Считать числа Рамсея очень трудно. Известно, что:

  • R(4,3)=9,
  • R(4,4)=18,
  • R(3,5)=14,
  • R(4,5)=25 (это сложно).

А вот R(5,5) уже неизвестно. Известно только, что 43⩽R(5,5)⩽48.

Как говорил математик Пол Эрдёш больше 30 лет назад, если на Землю нападут пришельцы и потребуют в течение года назвать

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Силиконовая трубка с лекарством помогла бороться с раком мочевого пузыря изнутри Силиконовая трубка с лекарством помогла бороться с раком мочевого пузыря изнутри

Ка работает система доставки препарата для лечения рака мочевого пузыря

N+1
«Не отступать от цели, не обвинять всех вокруг и не жалеть себя»: как попасть в список Forbes «Не отступать от цели, не обвинять всех вокруг и не жалеть себя»: как попасть в список Forbes

Какими качествами необходимо обладать, чтобы попасть в список богатейших

Psychologies
Палеогенетики уточили популяционную историю Таримской впадины Палеогенетики уточили популяционную историю Таримской впадины

Как ученые анализировали геномы древних людей из Таримской впадины

N+1
Беседа галериста Алины Крюковой и искусствоведа Ивана Чечота Беседа галериста Алины Крюковой и искусствоведа Ивана Чечота

Алина Крюкова поговорила с Иваном Чечотом об искусстве в эпоху кризиса

СНОБ
Мы выбираем друг друга не случайно Мы выбираем друг друга не случайно

Выбор партнера предопределен всем предшествующим ходом нашей жизни

Psychologies
20 вопросов, которые стоит задать мужчине в конфетно-букетный период 20 вопросов, которые стоит задать мужчине в конфетно-букетный период

На что следует обратить внимание девушке в конфетно-букетный период?

Psychologies
Новый дачный Новый дачный

После долгой зимы любимые дом и сад нуждаются в нашей заботе

Лиза
Мадам Тофана: как Мадам Тофана: как

Тофана — имя целой династии отравительниц

VOICE
ИИ ищет законы природы на основе известных теорий и новых данных. Так работают люди ИИ ищет законы природы на основе известных теорий и новых данных. Так работают люди

Ученые надеются, что скоро ИИ найдет законы, которых они не знают

ТехИнсайдер
Надувной квадрокоптер ударился о стену и отскочил Надувной квадрокоптер ударился о стену и отскочил

Надувная рама убережет дрон от разрушений при столкновениях

N+1
Я, он и его бывшая: реальные истории о манипуляциях и эмоциональной зависимости Я, он и его бывшая: реальные истории о манипуляциях и эмоциональной зависимости

Преследования, угрозы, попытки вернуться... Почему бывшие ведут себя так?

Psychologies
ПАИ с удобствами и без ПАИ с удобствами и без

Какая недвижимость доступна в ЗПИФах розничным инвесторам

Деньги
Погружение с первых страниц: 5 романов с увлекательным сюжетом, которые стоит прочесть Погружение с первых страниц: 5 романов с увлекательным сюжетом, которые стоит прочесть

Рассказываем о книгах, от которых трудно оторваться до самой последней страницы

ТехИнсайдер
«Когда вытаскиваешь наружу свои боли, начинаешь с ними справляться» «Когда вытаскиваешь наружу свои боли, начинаешь с ними справляться»

Театр лечит — уверена актриса Марьяна Спивак

OK!
Перестать читать мысли и концентрироваться на недостатках: 5 способов спасти отношения — советы коуча Перестать читать мысли и концентрироваться на недостатках: 5 способов спасти отношения — советы коуча

Как спасти перспективные отношения от самих себя

Psychologies
Акиньшина - звезда, а где вторая? Что стало с юной актрисой из фильма Акиньшина - звезда, а где вторая? Что стало с юной актрисой из фильма

Как сложилась жизнь исполнительницы роли младшей сестры в фильме "Сестры"?

VOICE
Она валит. Первый тест «убийцы Tesla» BYD Seal Она валит. Первый тест «убийцы Tesla» BYD Seal

На новый седан BYD Seal китайцев большие надежды

РБК
Кто может стать донором крови и костного мозга в России и как это сделать Кто может стать донором крови и костного мозга в России и как это сделать

О простых возможностях стать донором и спасти чью-то жизнь

Forbes
Эксплуатация и сексуализация: за что критикуют детские конкурсы красоты Эксплуатация и сексуализация: за что критикуют детские конкурсы красоты

Как детские конкурсы красоты становятся местом реализации родительских амбиций

Forbes
Эксперты рассказали о ловушках с реверсивным движением: как ездить Эксперты рассказали о ловушках с реверсивным движением: как ездить

Как ездить по дорогам с реверсивным движением и какие ошибки допускают водители?

РБК
Илья Макаров: «Люди не готовы к ошибкам нейросетей» Илья Макаров: «Люди не готовы к ошибкам нейросетей»

Как устроены нейросети, каковы их возможности, риски и перспективы?

РБК
Вы будете удивлены: топ-10 слов, которым нет (или Вы будете удивлены: топ-10 слов, которым нет (или

Просторечия, которые портят нашу жизнь

ТехИнсайдер
7 нескучных методов перебороть себя и начать заниматься спортом 7 нескучных методов перебороть себя и начать заниматься спортом

Чем менее активный образ жизни ведет человек, тем сложнее ему начать двигаться

Правила жизни
Relativity Space отказалась от легкой 3D-печатной ракеты Terran 1 Relativity Space отказалась от легкой 3D-печатной ракеты Terran 1

Космическая компания Relativity Space решила полностью отказаться от Terran 1

N+1
Ближний морской бой: как возникла и развивалась практика брать вражеские суда на абордаж Ближний морской бой: как возникла и развивалась практика брать вражеские суда на абордаж

«Морская пехота» консула Гая Дуилия и пираты Генри Моргана воевали одинаково

Вокруг света
Тайный сын Гитлера? Как воевавший против нацистов француз пытался доказать, что он сын диктатора Тайный сын Гитлера? Как воевавший против нацистов француз пытался доказать, что он сын диктатора

Моральные убеждения некоторых людей не отменяют их желания узнать свои корни

ТехИнсайдер
Адаптация к потеплению: что не так с современной климатической повесткой Адаптация к потеплению: что не так с современной климатической повесткой

Предотвращение глобального потепления: «сначала маску на себя, потом на ребенка»

Forbes
Странная привычка из прошлого: правда ли, что средневековые люди спали сидя? Странная привычка из прошлого: правда ли, что средневековые люди спали сидя?

Что такое "вертикальный сон" и практиковался ли он людьми из Средних веков?

ТехИнсайдер
Ставка на аутентичность: как развивается ресторанная индустрия в Казахстане Ставка на аутентичность: как развивается ресторанная индустрия в Казахстане

О том, как развиваются рестораны в Казахстане и о локальной кухне

Forbes
«Продолжают завоевывать пространство»: как женщины меняют образ жизни и облик городов «Продолжают завоевывать пространство»: как женщины меняют образ жизни и облик городов

Почему без демократии невозможно сделать город удобным

Forbes
Открыть в приложении