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

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
Оценивая преимущество: нетранзитивные позиции в шахматах Оценивая преимущество: нетранзитивные позиции в шахматах

Всегда ли можно однозначно сказать, чья позиция на шахматной доске сильнее?

Наука и жизнь
Как увидеть парад планет 21 января 2025 года? Интересные факты и простой ответ! Как увидеть парад планет 21 января 2025 года? Интересные факты и простой ответ!

Шесть планет встанут в ровный ряд на небе, — и вот как их можно увидеть!

ТехИнсайдер
Музыкальная пауза: история народного хита Музыкальная пауза: история народного хита

Вспоминаем историю главной песни Михаила Круга

Правила жизни
Как уговорить близкого с зависимостью обратиться за помощью: 6 верных шагов Как уговорить близкого с зависимостью обратиться за помощью: 6 верных шагов

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

Psychologies
Эффект наращивания: 5 домашних способов отрастить длинные и крепкие ногти Эффект наращивания: 5 домашних способов отрастить длинные и крепкие ногти

Простые рецепты целебных масок для фантастического роста ногтей

VOICE
Как быстро и надежно удалить историю в браузере: сетевые хитрости Как быстро и надежно удалить историю в браузере: сетевые хитрости

Как очистить историю браузера в пару кликов?

ТехИнсайдер
Русский дом Русский дом

Основательница ludi_architects и владелец CUBE X познакомились на выставке

Собака.ru
«Я стал совсем западником. Каждый день бреюсь»: о чем писал Родченко жене из Парижа «Я стал совсем западником. Каждый день бреюсь»: о чем писал Родченко жене из Парижа

Отрывок из книги «В Париже. Из писем домой» Александра Родченко

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

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

РБК
На пути к другим галактиками: восемь лучших фильмов про космос На пути к другим галактиками: восемь лучших фильмов про космос

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

Forbes
Cоцсети негативно сказываются на психике и кошельке человека? Еще как! Объяснение эксперта Cоцсети негативно сказываются на психике и кошельке человека? Еще как! Объяснение эксперта

Как постоянное влияние медиа меняет поведение людей

ТехИнсайдер
Топ-7 лучших автомобилей для дрифта Топ-7 лучших автомобилей для дрифта

Предлагаем наш вариант подборки топовых дрифткаров

РБК
Культура труда Культура труда

Арт-индустрия готова многое предложить тем, кто решится связать с ней свою жизнь

VOICE
Если верна теория, которой уже два века, после 2073 года некоторые люди доживут до 140 лет Если верна теория, которой уже два века, после 2073 года некоторые люди доживут до 140 лет

Сколько лет люди будут жить в будущем?

ТехИнсайдер
Стильно, комфортно Стильно, комфортно

Современный интерьер с классическими декоративными приёмами

SALON-Interior
Почему мы наказываем себя и как перестать это делать? Почему мы наказываем себя и как перестать это делать?

Всегда считаете себя виноватыми в любой ситуации?

Psychologies
«Во всем ищу позитивные стороны!» «Во всем ищу позитивные стороны!»

Владимир Жеребцов — о том, почему девушки охотно ведутся на всяких проходимцев

OK!
Рыба гниет с головы: татарская притча о лжи и пороке Рыба гниет с головы: татарская притча о лжи и пороке

Одна из притч из книги Татьяны Муравьевой «Мифы Поволжья»

Psychologies
Могут ли собаки улыбаться или смеяться Могут ли собаки улыбаться или смеяться

Что означает собачья «улыбка»?

ТехИнсайдер
«Елена Андреевна — это роль на вырост» «Елена Андреевна — это роль на вырост»

Светлана Колпакова в спектакле «Дядя Ваня» открывается зрителям с новой стороны

OK!
6 продуктов, от которых советуют отказаться нейробиологи для здоровья мозга 6 продуктов, от которых советуют отказаться нейробиологи для здоровья мозга

Наши пищевые привычки также играют большую роль в здоровье мозга

ТехИнсайдер
Белый сервиз Малевича и другие дизайн-решения советских авангардистов Белый сервиз Малевича и другие дизайн-решения советских авангардистов

Как идеи авангардистов воплощались в предметах, используемых в быту

Правила жизни
«А король-то голый!»: в поисках «настоящего» тестостерона «А король-то голый!»: в поисках «настоящего» тестостерона

Тестостерону придаются в мужском организме все мыслимые и немыслимые функции

Maxim
Столица закатов: гид по Нижнему Новгороду Столица закатов: гид по Нижнему Новгороду

Гид по лучшим пешим маршрутам, барам, ресторанам Нижнего Новгорода

Forbes
«Я понимаю, что все это наше русское, родное, а все-таки не привыкну никак» «Я понимаю, что все это наше русское, родное, а все-таки не привыкну никак»

Как Островский превращает всеобщее человеческое в национальное загадочное

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

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

Правила жизни
Зачем нам чувства? Понятно о науке: объяснения психиатра Зачем нам чувства? Понятно о науке: объяснения психиатра

Как у нас возникают эмоции и для чего они нам нужны?

Psychologies
Как отправить большой файл: 6 способов Как отправить большой файл: 6 способов

Как отправить большой файл, не оплачивая подписки на облака и файлообменники

CHIP
7 способов избежать рака яичников 7 способов избежать рака яичников

Рак яичников — это серьезная болезнь. Как ее предупредить?

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