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

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
«Когорта добромыслящих» «Когорта добромыслящих»

Специализированная политическая полиция появилась по «обдуманному плану»

Дилетант
Когда медицина перестает быть бумажной: как Москва лечит людей и спасает деревья Когда медицина перестает быть бумажной: как Москва лечит людей и спасает деревья

Как электронная медицина спасает сотни деревьев?

Правила жизни
Физический труд и духовный отдых: 4 российских обители, которые принимают паломников Физический труд и духовный отдых: 4 российских обители, которые принимают паломников

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

Вокруг света
Летают ли авиалайнеры над Северным полюсом: да, и это стоит сделать хотя бы раз в жизни Летают ли авиалайнеры над Северным полюсом: да, и это стоит сделать хотя бы раз в жизни

Почему летать через Северный полюс до сих пор рискованно

ТехИнсайдер
Танатофобия: как страх смерти проявляется в теле и что с ним делать Танатофобия: как страх смерти проявляется в теле и что с ним делать

Что делать, если нормальный страх смерти становится фобией?

Psychologies
Древние цивилизации на Инде погубила 200-летняя засуха Древние цивилизации на Инде погубила 200-летняя засуха

Что разрушило цивилизацию бронзового века на реке Инд?

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

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

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

В XX веке в Италии шили одежду из тканей, изготовленных из цельного молока

VOICE
Смотримся в черное зеркало: как нейросети уже используются в моде и что будет дальше Смотримся в черное зеркало: как нейросети уже используются в моде и что будет дальше

Заменят ли нейросети дизайнеров, стилистов и фотографов?

Правила жизни
На каком масле жарить и еще 5 вопросов о жирах, полезных и не очень На каком масле жарить и еще 5 вопросов о жирах, полезных и не очень

Полезные жиры — залог стройного тела, но какие жиры считать полезными?

Правила жизни
Под грифом “секретно” Под грифом “секретно”

Дмитрий Путылин расследует дело о потерянных кубиках

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

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

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

Как пережить смену локации с минимальными потерями и влиться в новую культуру

Psychologies
Что не так с ответственностью бизнеса за утечки данных Что не так с ответственностью бизнеса за утечки данных

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

Forbes
Комплекс матери Терезы: проверь, не слишком ли ты добрая (это мешает жить!) Комплекс матери Терезы: проверь, не слишком ли ты добрая (это мешает жить!)

Приходится ли тебе время от времени слышать «Ну ты прямо мать Тереза!»?

VOICE
Сыроедение! Сыроедение!

Так ли безупречно сыроедение?

Здоровье
100-летние сестры рассказали, как поддерживать остроту ума в глубокой старости. Стоит узнать! 100-летние сестры рассказали, как поддерживать остроту ума в глубокой старости. Стоит узнать!

Ширли Ходс и Рут Свидлер — о правильном и здоровом старении

ТехИнсайдер
Кружок по выживанию Кружок по выживанию

Что делать, если коллега пытается сделать всё, чтобы ты лишилась работы?

VOICE
О дивный тленный мир: 10 фильмов и книг, которые затрагивают тему смерти О дивный тленный мир: 10 фильмов и книг, которые затрагивают тему смерти

Каждый задумывается о том, что происходит во время гибели

ТехИнсайдер
Морские огурцы могут разорвать собственную задницу и обвить врага комком липких внутренностей Морские огурцы могут разорвать собственную задницу и обвить врага комком липких внутренностей

Морские огурцы только кажутся легкой мишенью для голодных хищников

ТехИнсайдер
Как ускорить борьбу с табакокурением Как ускорить борьбу с табакокурением

Почему нужно различать потребление никотина и затяжку сигаретой

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

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

Forbes
«Страна гейш»: почему в западном обществе столько мифов про японских женщин «Страна гейш»: почему в западном обществе столько мифов про японских женщин

Как взглянуть на Японию без патриархальных стереотипов

Forbes
25 коротких фактов вокруг фильмов «Рокки Бальбоа»: сценарий за несколько дней, статуя герою и выбитые пальцы 25 коротких фактов вокруг фильмов «Рокки Бальбоа»: сценарий за несколько дней, статуя герою и выбитые пальцы

Все, что нужно знать о фильме, перевернувшем карьеру Сильвестра Сталлоне

Maxim
Настройка звука Настройка звука

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

Grazia
«Поп Гапон и японские винтовки» «Поп Гапон и японские винтовки»

15 поразительных историй времен дореволюционной России

N+1
Мировой отец! Донор спермы в Нидерландах врал в опросах и стал отцом 550 детей за 16 лет Мировой отец! Донор спермы в Нидерландах врал в опросах и стал отцом 550 детей за 16 лет

Донор не должен быть отцом более 25 детей, но один мужчина обошел это условие

ТехИнсайдер
Интерес, эмпатия и гиперконцентрация: 10 признаков настоящей влюбленности — чек-лист психолога Интерес, эмпатия и гиперконцентрация: 10 признаков настоящей влюбленности — чек-лист психолога

Легкое увлечение или безумная влюбленность?

Psychologies
Сохранить свое: как переписать имущество Сохранить свое: как переписать имущество

Что нужно знать о том, как сохранить свое имущество сегодня?

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