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

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

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

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

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

Палеобиологи прочитали протеом жившего больше 20 миллионов лет назад носорога Палеобиологи прочитали протеом жившего больше 20 миллионов лет назад носорога

Ученые выделили фрагменты древних белков из зубной эмали миоценового носорога

N+1
И блондинкой была, и брюнеткой: как выглядели Русалочки во всех экранизациях сказки Андерсена И блондинкой была, и брюнеткой: как выглядели Русалочки во всех экранизациях сказки Андерсена

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

VOICE
Колорадские жабы оказались под угрозой из-за высокого спроса на их психоактивный яд Колорадские жабы оказались под угрозой из-за высокого спроса на их психоактивный яд

Почему снижается численность колорадских жаб

N+1
Не щадя живота своего: что такое висцеральный жир и как от него избавиться Не щадя живота своего: что такое висцеральный жир и как от него избавиться

Чем опасен висцеральный жир и как избавиться от него

Правила жизни
Нехимические зависимости: что это такое, как их распознать и победить Нехимические зависимости: что это такое, как их распознать и победить

Вы просыпаетесь и сразу тянетесь к телефону?

Maxim
Это нужно знать: как стресс влияет на организм человека? Это нужно знать: как стресс влияет на организм человека?

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

ТехИнсайдер
Лайфхаки, которые помогут вырастить лучшие фруктовые деревья Лайфхаки, которые помогут вырастить лучшие фруктовые деревья

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

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

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

ТехИнсайдер
Топ-10 программ для создания презентаций: не только PowerPoint Топ-10 программ для создания презентаций: не только PowerPoint

Плюсы и минусы разных сервисов для создания презентаций

CHIP
«Вишневый сад» по-испански. О победителе Берлинского кинофестиваля «Земля Алькаррас» «Вишневый сад» по-испански. О победителе Берлинского кинофестиваля «Земля Алькаррас»

О важных изменениях устройства цивилизации — в фильме «Земля Алькаррас»

СНОБ
Тренер по сну: как выручить 22 млн рублей на обучающих полезным привычкам ботах Тренер по сну: как выручить 22 млн рублей на обучающих полезным привычкам ботах

Артем Журавлев и Степан Солоднев разработали чат-бота в Telegram «Слипи»

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

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

ТехИнсайдер
«Убила детей, чтобы отомстить мужчине»: Медея — как менялась интерпретация древнегреческого мифа «Убила детей, чтобы отомстить мужчине»: Медея — как менялась интерпретация древнегреческого мифа

Кто же такая Медея: хладнокровная детоубийца или обманутая женщина?

Psychologies
«Преприятный человек» «Преприятный человек»

Почти 200 лет не утихают споры вокруг фигуры Леонтия Дубельта

Дилетант
Александр Чулок: «Ведь не граблями и вилами строить новую экономику» Александр Чулок: «Ведь не граблями и вилами строить новую экономику»

Заглядываем в будущее вместе с экономистом и прогнозистом Александром Чулоком

РБК
Восхождение дракона Восхождение дракона

Как Поднебесной удалось стать центром мирового автопрома?

Robb Report
В человеческом мозге разглядели две системы контроля движений В человеческом мозге разглядели две системы контроля движений

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

N+1
Фантазия, она — моя Фантазия, она — моя

Прокладываем кратчайший путь к самым ярким оргазмам

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

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

Вокруг света
Настройка звука Настройка звука

Звуковые медитации считаются лучшим способом восстановить силы

Grazia
Что такое милиумы на лице: причины, лечение и профилактика Что такое милиумы на лице: причины, лечение и профилактика

Почему возникают милиумы и как можно их убрать?

РБК
Ученые выяснили, почему у берегов Черного моря появляются вихри Ученые выяснили, почему у берегов Черного моря появляются вихри

Шельфовые вихри — основной механизм самоочищения прибрежных зон моря

ТехИнсайдер
Стартапы-умники: что нужно помнить перед запуском наукоемкого продукта Стартапы-умники: что нужно помнить перед запуском наукоемкого продукта

Диптех-проекты привлекают все больше внимания целевой аудитории и инвесторов

Forbes
Шесть вопросов о витаминах и микроэлементах Шесть вопросов о витаминах и микроэлементах

Стоит ли принимать зимой ударные дозы витаминов и минералов?

Здоровье
О чем на самом деле сюрреалистическое кино «Все страхи Бо» с Хоакином Фениксом О чем на самом деле сюрреалистическое кино «Все страхи Бо» с Хоакином Фениксом

Каким получился комедийный хоррор «Все страхи Бо» Ари Астера

СНОБ
Это вам не мусор! Учимся с умом использовать пластиковые хомуты в доме и на даче Это вам не мусор! Учимся с умом использовать пластиковые хомуты в доме и на даче

Хомуты могут быть полезны для хранения продуктов и экспресс-ремонта одежды

ТехИнсайдер
Правила жизни Сергея Рахманинова Правила жизни Сергея Рахманинова

Правила жизни композитора, дирижера и пианиста Сергея Рахманинова

Правила жизни
Человек с железными легкими: как живет Пол Александер, который уже более 68 лет не покидает железную капсулу Человек с железными легкими: как живет Пол Александер, который уже более 68 лет не покидает железную капсулу

Врачи пророчили ему скорую смерть, но, вопреки всему, он жив!

ТехИнсайдер
«Я умен, зол и завистлив»: почему пьесы Александра Островского востребованы сегодня «Я умен, зол и завистлив»: почему пьесы Александра Островского востребованы сегодня

Нина Шалимова рассказывает о феномене драматурга Островского

Forbes
Незаменимый предмет в косметичке: 8 потрясающих лайфхаков с пилочкой для ногтей Незаменимый предмет в косметичке: 8 потрясающих лайфхаков с пилочкой для ногтей

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

ТехИнсайдер
Открыть в приложении