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

NewsMaker

I'm just a script
Премиум
13,579
20
8 Ноя 2022
Как найти друзей на шумной вечеринке?


w3mkmcfo4gr1rj7xj44mj05ojeqdf1o1.jpg


Математики из Калифорнийского университета в Сан-Диего, Жак Верстрате и Сэм Маттеус, сделали прорыв в теории Рэмси, разгадав загадку чисел Рэмси, волновавшую ученых с 1930-х годов.

Теория Рэмси, занимающаяся исследованием порядка в хаосе, предполагает, что в достаточно большом графе всегда найдется упорядоченность. Например, в группе из шести человек всегда можно обнаружить трех, знакомых друг с другом, или трех, незнакомых между собой. Это выражается как r(3,3) и равно шести - факт, который Верстрате называет "абсолютной истиной".

Далее ученые стремились решить более сложные задачи, такие как r(4,4) и r(4,t), где количество неподключенных точек переменно. Решение для r(4,4) было найдено еще в 1930-х годах и составляет 18, однако r(5,5) до сих пор остается неизвестным.

Верстрате и его коллега из Университета Иллинойса в Чикаго, Дхрув Мубайи, обнаружили, что псевдослучайные графы могут помочь в решении этих давних задач. Используя псевдослучайные графы, они решили задачу r(3,t) в 2019 году, а затем, привлекая знания из разных областей математики, Верстрате и Маттеус нашли решение и для r(4,t).

Они установили, что для гарантированного обнаружения четырех знакомых друг с другом или t незнакомых людей на вечеринке необходимо примерно t^3 участников. Это открытие - приблизительное, но очень близкое к точному ответу.

Результаты их исследований сейчас находятся на рассмотрении в "Annals of Mathematics" и доступны для предварительного просмотра на Для просмотра ссылки Войди или Зарегистрируйся .
 
Источник новости
www.securitylab.ru