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

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 лет назад, если на Землю нападут пришельцы и потребуют в течение года назвать

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

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

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

Царь ненастоящий! Царь ненастоящий!

Почему ученые отвергли гипотезу об идентификации останков Филиппа II

N+1
Жизнь без партнера: возможно ли оставаться счастливыми — 3 мифа об одиночестве Жизнь без партнера: возможно ли оставаться счастливыми — 3 мифа об одиночестве

Как сохранять самоощущение, если мы почти потеряли надежду встретить партнера?

Psychologies
Тысячи сомиков-шмелей вскарабкались по водопадам Тысячи сомиков-шмелей вскарабкались по водопадам

Почему южноамериканские сомики-шмели необычно ведут себя у водопадов

N+1
Безотцовщина: как разрыв с одним из родителей влияет на ребенка Безотцовщина: как разрыв с одним из родителей влияет на ребенка

Как помочь ребенку при разлуке со значимым взрослым

Forbes
«Тест на старика»: а вы сможете его пройти? «Тест на старика»: а вы сможете его пройти?

Если у вас есть пять минут, предлагаем испытать свои силы в тесте на старика

Maxim
«Я ему теперь никто?»: что делать, если близкий друг начал вас игнорировать «Я ему теперь никто?»: что делать, если близкий друг начал вас игнорировать

Как быть, если непонятно, на что друг обиделся, а поговорить не выходит?

Psychologies
Принимай каждый день Принимай каждый день

Отношения со своим «я» – как ни крути, самые важные в жизни

VOICE
«Болевые точки»: как они влияют на нас и наши отношения «Болевые точки»: как они влияют на нас и наши отношения

Откуда берутся «болевые точки»?

Psychologies
Советский киноавангард в лицах: главные режиссеры и фильмы той эпохи Советский киноавангард в лицах: главные режиссеры и фильмы той эпохи

Первые советские режиссеры-авангардисты

Правила жизни
Как расстаться, если партнер все еще любит вас? Как расстаться, если партнер все еще любит вас?

Как вести себя при расставании, чтобы не причинить друг другу еще большей боли?

Psychologies
Идеология «умственных плотин» Идеология «умственных плотин»

Россия колебалась между общеевропейским путём развития и своим «особым путём»

Дилетант
Всему не свое время Всему не свое время

Как Владимир Казаков реанимировал обэриутский абсурд в эпоху застоя

Weekend
Т9 на стероидах: способен ли искусственный интеллект заменить финансовых аналитиков Т9 на стероидах: способен ли искусственный интеллект заменить финансовых аналитиков

Cможет ли ИИ заменить финансового аналитика и помочь инвесторам зарабатывать?

Forbes
«Прыжок веры» в реальной жизни: сумасшедший трюк каскадера «Прыжок веры» в реальной жизни: сумасшедший трюк каскадера

Что такое «Прыжок веры» и можно ли его исполнить в реальной жизни?

ТехИнсайдер
Пустота, игры с огнем и дзюдо: каким был художник Ив Кляйн Пустота, игры с огнем и дзюдо: каким был художник Ив Кляйн

Вы могли не знать его имени, но вы видели этот цвет — гипнотизирующий синий

Правила жизни
Как наладить сексуальную жизнь после рождения ребенка: 5 советов новоиспеченным родителям Как наладить сексуальную жизнь после рождения ребенка: 5 советов новоиспеченным родителям

Как побороть кризис интимной жизни после рождения ребенка? Несколько советов

Psychologies
Как экстраверту и интроверту ужиться вместе: 5 подсказок — постройте гармоничные отношения Как экстраверту и интроверту ужиться вместе: 5 подсказок — постройте гармоничные отношения

Как партнерам с разными темпераментами достичь взаимопонимания?

Psychologies
«Книга слизи. Скользкий след в истории Земли» «Книга слизи. Скользкий след в истории Земли»

Как слизь обеспечивает защиту нашего желудка и кишечника от патогенов

N+1
«Кто не сдал на подарки?»: почему нас так раздражают родительские чаты «Кто не сдал на подарки?»: почему нас так раздражают родительские чаты

Почему родительские чаты превратились в настоящую боль?

Psychologies
«Все мы уникальны и важны»: как осознать безусловную ценность — мнение психолога «Все мы уникальны и важны»: как осознать безусловную ценность — мнение психолога

Почему мы сомневаемся в собственной ценности и что с этим делать

Psychologies
Что такое скин-сайклинг: все о методе, который обещает преобразить кожу за 4 дня Что такое скин-сайклинг: все о методе, который обещает преобразить кожу за 4 дня

Что цикличный уход за кожей завоевывает все больше поклонников

Правила жизни
Классические внедорожники, которые заслуживают возрождения Классические внедорожники, которые заслуживают возрождения

Легендарные внедорожники, которым нужно дать второй шанс

4x4 Club
Jeep Compass. Жизнь в стиле Grand Cherokee Jeep Compass. Жизнь в стиле Grand Cherokee

Jeep Compass, чтобы плыть дальше, чистит себя под Jeep Grand Cherokee

4x4 Club
Секс и менопауза: правда и мифы Секс и менопауза: правда и мифы

С приходом менопаузы сексуальная жизнь женщины не заканчивается

Psychologies
Количеством или качеством: как китайские бренды электроники пришли в Россию Количеством или качеством: как китайские бренды электроники пришли в Россию

Разбираемся, как Китай меняет ландшафт российского IT-сектора

РБК
Как карта ляжет Как карта ляжет

Точки на планете, воспоминания о которых не потускнеют даже через много лет!

Grazia
Секрет вечной молодости: как Сергей Воронов решил омолодить все человечество пересадкой обезьяньих яиц Секрет вечной молодости: как Сергей Воронов решил омолодить все человечество пересадкой обезьяньих яиц

Громкие и страшные опыты профессора Воронова

ТехИнсайдер
Проломленный череп и не только: причины, по которым британские монархи попадали в больницу Проломленный череп и не только: причины, по которым британские монархи попадали в больницу

Здоровье не купишь, и даже сильные мира сего не застрахованы от травм и болезней

VOICE
«Я выбираю себя» «Я выбираю себя»

Ида Галич — о том, считает ли себя звездой она сама

OK!
«Я люблю слишком сильно»: как уменьшить «громкость» чувств «Я люблю слишком сильно»: как уменьшить «громкость» чувств

Могут ли люди усиливать или ослаблять чувство любви?

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