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

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

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

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

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

Детский плач в возрасте пяти месяцев связали с наследственностью Детский плач в возрасте пяти месяцев связали с наследственностью

Генетические факторы отвечают за 70 процентов плача

N+1
Нарцисс и карьера: как излишнее самолюбование вредит работе Нарцисс и карьера: как излишнее самолюбование вредит работе

Чем опасен нарциссизм на рабочем месте

Psychologies
Как появилась Вселенная? Ответ может скрываться в водах Байкала Как появилась Вселенная? Ответ может скрываться в водах Байкала

Ключ к разгадке сотворения Вселенной может находиться в глубинах Байкала

ТехИнсайдер
Как украшения влияют на человека: выбираем правильные акскессуары Как украшения влияют на человека: выбираем правильные акскессуары

Аксессуары способны полностью изменить ваш стиль

VOICE
5 сверхспособностей, которые станут доступны людям уже через 5 лет по версии футурологов 5 сверхспособностей, которые станут доступны людям уже через 5 лет по версии футурологов

Какие «суперспособности» станут реальностью уже к 2030 году — и какой ценой?

Maxim
Ждули: почему российские женщины выходят замуж за заключенных Ждули: почему российские женщины выходят замуж за заключенных

Ждули: разбираемся в истоках феномена и объясняем, при чем тут стереотипы

Forbes
Все, что важно знать о кори и прививке от нее Все, что важно знать о кори и прививке от нее

Что нужно знать о кори и как защитить себя и своих близких во время вспышек кори

РБК
Гидра: удивительное животное, которое почти невозможно убить Гидра: удивительное животное, которое почти невозможно убить

Гидра — что это за животное и почему оно так названо?

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

Смертельная опасность — обычное дело в космонавтике

Maxim
Родители думали, что 14-летняя Наташа стала жертвой киллера. Но она скрывалась у своего парня Родители думали, что 14-летняя Наташа стала жертвой киллера. Но она скрывалась у своего парня

Все считали, что девочка пострадала от рук киллера, но на суде открылась правда

ТехИнсайдер
10 абсурдистских фильмов эпохи перестройки 10 абсурдистских фильмов эпохи перестройки

Крах исторических нарративов влечет за собой крах большого нарратива в искусстве

Weekend
Что полнеет — бедра, руки или живот? Посмотри в зеркало и определи причину лишнего веса Что полнеет — бедра, руки или живот? Посмотри в зеркало и определи причину лишнего веса

Как ускорить процесс постепенного похудения?

VOICE
Максимально быстрый интернет на даче: как этого добиться Максимально быстрый интернет на даче: как этого добиться

Как сделать так, чтобы интернет на даче был максимально быстрым

CHIP
Анемия вне сезона Анемия вне сезона

У каждой второй женщины и каждого третьего мужчины обнаруживается анемия

Лиза
Витамин D: почему он так важен и как не пропустить его дефицит — советы нутрициолога Витамин D: почему он так важен и как не пропустить его дефицит — советы нутрициолога

Все, что вам необходимо знать о витамине D

Psychologies
Ученая бессмыслица Ученая бессмыслица

«Киприанов пир» как образец эрудитски-виртуозного абсурдизма

Weekend
Наташа Королева: «Как только мне не хватает знаний, я иду учиться» Наташа Королева: «Как только мне не хватает знаний, я иду учиться»

Наташа Королева рассказала о своих любимых хитах, кулинарии и отношениях с мужем

Лиза
Ошибка выживавшего Ошибка выживавшего

Как опыт нелюбви сделал Виктора Шкловского настоящим писателем

Weekend
Не то же, но похоже Не то же, но похоже

Чем опасны бьюти-подделки и как отличить оригинальную косметику от реплик?

VOICE
Смотри и слушай. На что нужно обращать внимание при осмотре внедорожника с пробегом Смотри и слушай. На что нужно обращать внимание при осмотре внедорожника с пробегом

Универсальный набор рекомендаций, который поможет провести осмотр бэушки

4x4 Club
Томат, авокадо и гранат: 13 антивозрастных продуктов — включите в рацион Томат, авокадо и гранат: 13 антивозрастных продуктов — включите в рацион

Хотите, чтобы никто не догадался, сколько вам лет, без пластической операции?

Psychologies
«Класс-2007»: австралийский сериал о том, могут ли женщины выжить после апокалипсиса «Класс-2007»: австралийский сериал о том, могут ли женщины выжить после апокалипсиса

Как сериал «Класс-2007» нормализует исключительно женский состав

Forbes
Может ли человечество колонизировать другую планету и сколько времени это займет? Может ли человечество колонизировать другую планету и сколько времени это займет?

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

ТехИнсайдер
Хит на все времена: 11 лучших ролей Хита Леджера Хит на все времена: 11 лучших ролей Хита Леджера

От хулигана Патрика до доктора Парнаса: лучшие роли Хита Леджера

Правила жизни
Какие права на квадроцикл нужны и можно ли ездить без прав Какие права на квадроцикл нужны и можно ли ездить без прав

Нужны ли права для управления квадроциклом и как их получить?

РБК
Заживает втрое быстрее: найден способ ускорить лечение ран с помощью электричества Заживает втрое быстрее: найден способ ускорить лечение ран с помощью электричества

В перспективе такой способ лечения ран может спасти тысячи жизней

Вокруг света
Цена вопроса: что происходит с премиальными модными брендами в России Цена вопроса: что происходит с премиальными модными брендами в России

Что такое товары категории премиум и насколько они востребованы на рынке сейчас

Forbes
Терапия фотосессией: как заново познакомиться с собой на съемке Терапия фотосессией: как заново познакомиться с собой на съемке

Как процесс фотосессии может раскрыть человека заново

Psychologies
Как младенцы учат язык взрослых? Поразительное объяснение ученых! Как младенцы учат язык взрослых? Поразительное объяснение ученых!

Маленькие дети учат язык своих родителей, основываясь на просодии

ТехИнсайдер
Российские экранизации иностранных книг, которые получились лучше западных Российские экранизации иностранных книг, которые получились лучше западных

Советский и русский кинематограф порой дарил нам шедевры

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