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

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
Гнилая ниточка. Как одна «абсолютно счастливая женщина» справлялась с алкогольной зависимостью в семье Гнилая ниточка. Как одна «абсолютно счастливая женщина» справлялась с алкогольной зависимостью в семье

Алевтина Кондратьевна всю жизнь боролась с пьянством в семье

СНОБ
Генетики выявили мужчин армянского происхождения в средневековом Болгаре Генетики выявили мужчин армянского происхождения в средневековом Болгаре

Палеогенетики секвенировали ДНК похороненных у стен средневекового Болгара

N+1
Что будет, если перестать чистить зубы Что будет, если перестать чистить зубы

Как часто и правильно нужно чистить зубы?

ТехИнсайдер
Пять языков любви Пять языков любви

Секрет прочных отношений

kiozk originals
Всему не свое время Всему не свое время

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

Weekend
Волосы на заколках: 7 вещей, которые нужно знать о безвредной альтернативе наращиванию Волосы на заколках: 7 вещей, которые нужно знать о безвредной альтернативе наращиванию

Для чего нужны волосы на заколках и кому они подойдут?

VOICE
Как понять, что ваша работа с психотерапевтом эффективна? Как понять, что ваша работа с психотерапевтом эффективна?

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

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

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

Psychologies
«Террорист победил»: как революционеры-радикалы боролись с властью в царской России «Террорист победил»: как революционеры-радикалы боролись с властью в царской России

История терроризма в царской России XIX-XX веков

Forbes
Как сделать утро добрым: 5 главных правил — советы для женщин Как сделать утро добрым: 5 главных правил — советы для женщин

Как создать легкую атмосферу утром?

Psychologies
Почему может быть опасно носить чужие украшения? Почему может быть опасно носить чужие украшения?

Есть определённые нюансы ношения украшений, которые ранее принадлежали другим

VOICE
«Я хочу того, на что есть право у каждого человека»: каково это — быть аутистом «Я хочу того, на что есть право у каждого человека»: каково это — быть аутистом

Отрывок из книги «Искатели закономерностей» об аутизме

Psychologies
Двойной агент Двойной агент

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

Grazia
5 знаковых коллабораций композиторов и художников 5 знаковых коллабораций композиторов и художников

Выдающиеся примеры союза искусств за последние полстолетия

Правила жизни
Дарья Беглова: «Хочется, чтобы в Переделкино оставался медлительный ритм» Дарья Беглова: «Хочется, чтобы в Переделкино оставался медлительный ритм»

Дом творчества Переделкино не только место силы, но и территория забвения

Psychologies
Почему легкие свистят и стоит ли переживать по этому поводу? Почему легкие свистят и стоит ли переживать по этому поводу?

Почему появляется свист при дыхании?

ТехИнсайдер
Поймай его, если сможешь: 15 лучших фильмов Кристофера Уокена Поймай его, если сможешь: 15 лучших фильмов Кристофера Уокена

Запутанная фильмография актера Кристофера Уокена, в которой мы разобрались

Правила жизни
Рынок комбикормов вырос вопреки проблемам Рынок комбикормов вырос вопреки проблемам

Топ-25 крупнейших компаний выпустили более 21 млн т продукции

Агроинвестор
5 самых захватывающих фэнтези-детективов 5 самых захватывающих фэнтези-детективов

Существуют ли увлекательные истории на стыке фэнтези и детективов?

Maxim
«Носы у нас обеих крупные, но непохожие»: Мариэтта Цигаль-Полищук о роли Раневской «Носы у нас обеих крупные, но непохожие»: Мариэтта Цигаль-Полищук о роли Раневской

Актриса Мариэтта Цигаль-Полищук — о творческом пути и влиянии матери на карьеру

Forbes
Лазерное шоу для рапса Лазерное шоу для рапса

Дроны с красным светом активизируют фотосинтез у культурных растений

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

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

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

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

Psychologies
Здоровье дороже Здоровье дороже

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

Деньги
«Все считали, что меня опекает состоятельный муж, но за нашу жизнь я расплатилась сполна» «Все считали, что меня опекает состоятельный муж, но за нашу жизнь я расплатилась сполна»

«Каждый человек, который приходит в твою жизнь, становится учителем»

Psychologies
Самую точную модель качания на качелях проверили на японских девушках Самую точную модель качания на качелях проверили на японских девушках

Ученые построили самую полную на сегодня механическую модель качания на качелях

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

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

Men Today
Полет на Маркс: фантастические проекты советских авангардистов Полет на Маркс: фантастические проекты советских авангардистов

Авангардистам редко удавалось осуществить свои утопические фантазии на практике

Правила жизни
5 малоизвестных книг братьев Стругацких, которые стоит прочитать 5 малоизвестных книг братьев Стругацких, которые стоит прочитать

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

Правила жизни
Открыть в приложении