- 13,850
- 20
- 8 Ноя 2022
Как найти друзей на шумной вечеринке?
Математики из Калифорнийского университета в Сан-Диего, Жак Верстрате и Сэм Маттеус, сделали прорыв в теории Рэмси, разгадав загадку чисел Рэмси, волновавшую ученых с 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" и доступны для предварительного просмотра на Для просмотра ссылки Войдиили Зарегистрируйся .
Математики из Калифорнийского университета в Сан-Диего, Жак Верстрате и Сэм Маттеус, сделали прорыв в теории Рэмси, разгадав загадку чисел Рэмси, волновавшую ученых с 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
