- 27,872
- 46
- 8 Ноя 2022
50 лет работы, прогресс на 10⁻²¹ — и это настоящий прорыв.
Математики десятилетиями изучают вопрос, который звучит почти как задачка из детского учебника: сколько точек нужно соединить линиями, чтобы в рисунке неизбежно появился порядок? Не важно, как именно раскрашивать линии и как пытаться спрятать закономерность. Если точек станет достаточно много, внутри схемы всё равно возникнет группа, где все участники связаны между собой одинаковым способом.
Такую задачу изучает теория Рамсея . Представим несколько точек на листе бумаги. Каждая точка соединена линией с каждой другой, а каждую линию можно покрасить в красный или синий цвет. Математиков интересует момент, когда при любой раскраске обязательно появится, например, красный или синий треугольник: три точки, где все три соединяющие линии имеют один цвет.
На маленьком примере всё видно сразу. Пять точек ещё можно соединить и раскрасить так, чтобы одноцветного треугольника не было. Но стоит добавить шестую точку, и избежать красного или синего треугольника уже невозможно. Поэтому число Рамсея для трёх точек равно шести.
Можно задавать более сложные условия. Например, пытаться избежать красной группы из трёх точек и синей группы из четырёх. Восемь точек ещё допускают удачную раскраску, а девять уже заставляют получить один из запрещённых вариантов. Чем больше такие группы, тем труднее понять, где проходит граница между «ещё можно спрятать порядок» и «порядок неизбежен».
Для больших размеров точные ответы почти неизвестны. Поэтому математики доказывают оценки. Одна оценка говорит: сеть такого-то размера ещё можно раскрасить без запрещённого рисунка. Другая говорит: начиная с такого-то размера запрещённый рисунок появится обязательно. Новая работа улучшила именно первую оценку для близкого к классическому случая: исследователи доказали , что удачная раскраска может существовать для чуть более крупных сетей, чем раньше удавалось показать.
История этой задачи тесно связана с Полем Эрдёшем. В 1947 году он предложил подход, который поначалу выглядел странно. Вместо того чтобы строить нужную раскраску вручную, Эрдёш предложил выбрать цвета случайно и посчитать вероятность удачи. Если вероятность получить рисунок без запрещённой группы больше нуля, значит хотя бы один подходящий рисунок точно существует.
Так появился вероятностный метод . Сегодня его используют далеко за пределами теории графов: в дискретной математике, информатике, проверке чисел на простоту, проектировании схем и работе с данными. Метод помогает там, где нужный объект трудно показать руками, но можно доказать, что случайный выбор иногда его создаёт.
С числами Рамсея этот подход дал мощный старт, а затем почти перестал двигаться в самой трудной зоне. Особенно упорно сопротивлялись случаи, где запрещённые красные и синие группы имеют одинаковый или почти одинаковый размер. Эрдёш доказал, что для группы размера k число Рамсея больше примерно 2 в степени k/2. Для k = 1000 это даёт величину около 2^500. За десятилетия оценку удалось поднять лишь примерно до 2^501.
Новая работа изменила не саму идею случайности, а способ выбирать цвета. В классическом варианте каждая линия получает цвет независимо, как при броске монеты. Новый подход связывает цвет линии с геометрией.
Сначала точки случайно размещают на поверхности сферы в пространстве с очень большим числом измерений. Затем смотрят на расстояние между каждой парой точек. Если две точки далеко друг от друга, линию между ними красят в красный цвет. Если близко - в синий. Цвета больше не появляются отдельно друг от друга: весь рисунок зависит от расположения точек на одной общей поверхности.
Такой приём помогает бороться с большими красными группами. Чтобы получить красную группу, нужно много точек, где каждая находится далеко от всех остальных. Геометрия высокой размерности сильно ограничивает такие наборы. Но возникает риск с другой стороны: близкие точки чаще дают синие группы. Поэтому авторам нужно было доказать, что новый способ действительно помогает, а не просто переносит проблему из красного цвета в синий.
Главная часть доказательства опирается на необычное свойство пространств с большим числом измерений. Если провести линии от центра такой сферы к случайно выбранным точкам, большинство линий окажется почти под прямым углом друг к другу. Для обычной трёхмерной сферы такая картина не кажется естественной, но в высокой размерности она становится типичной. Благодаря этому расстояния между точками можно оценивать гораздо строже.
После этих оценок авторы показали: при правильных параметрах остаётся ненулевая вероятность получить раскраску без запрещённых одноцветных групп. Значит нужная раскраска существует. Доказательство заняло около года и выросло в работу примерно на 40 страниц.
Результат не решает главный диагональный случай, где красные и синие группы имеют одинаковый размер. Но он улучшает оценки для почти диагональных чисел Рамсея, например когда запрещённая красная группа примерно вдвое меньше синей. В этой зоне заметного продвижения не было около 50 лет.
Численный выигрыш очень мал. В одной формуле к прежнему основанию степени добавилась величина порядка 10^-21. И вроде как такая прибавка выглядит почти ничтожной, но в теории графов важен сам факт улучшения: старая задача снова поддалась новому приёму.
Работа уже дала продолжение. Другие математики упростили геометрическую модель и ещё немного улучшили оценки. Похожие идеи начали применять к задачам с тремя цветами, где возможных одноцветных ловушек становится больше.
Математики десятилетиями изучают вопрос, который звучит почти как задачка из детского учебника: сколько точек нужно соединить линиями, чтобы в рисунке неизбежно появился порядок? Не важно, как именно раскрашивать линии и как пытаться спрятать закономерность. Если точек станет достаточно много, внутри схемы всё равно возникнет группа, где все участники связаны между собой одинаковым способом.
Такую задачу изучает теория Рамсея . Представим несколько точек на листе бумаги. Каждая точка соединена линией с каждой другой, а каждую линию можно покрасить в красный или синий цвет. Математиков интересует момент, когда при любой раскраске обязательно появится, например, красный или синий треугольник: три точки, где все три соединяющие линии имеют один цвет.
На маленьком примере всё видно сразу. Пять точек ещё можно соединить и раскрасить так, чтобы одноцветного треугольника не было. Но стоит добавить шестую точку, и избежать красного или синего треугольника уже невозможно. Поэтому число Рамсея для трёх точек равно шести.
Можно задавать более сложные условия. Например, пытаться избежать красной группы из трёх точек и синей группы из четырёх. Восемь точек ещё допускают удачную раскраску, а девять уже заставляют получить один из запрещённых вариантов. Чем больше такие группы, тем труднее понять, где проходит граница между «ещё можно спрятать порядок» и «порядок неизбежен».
Для больших размеров точные ответы почти неизвестны. Поэтому математики доказывают оценки. Одна оценка говорит: сеть такого-то размера ещё можно раскрасить без запрещённого рисунка. Другая говорит: начиная с такого-то размера запрещённый рисунок появится обязательно. Новая работа улучшила именно первую оценку для близкого к классическому случая: исследователи доказали , что удачная раскраска может существовать для чуть более крупных сетей, чем раньше удавалось показать.
История этой задачи тесно связана с Полем Эрдёшем. В 1947 году он предложил подход, который поначалу выглядел странно. Вместо того чтобы строить нужную раскраску вручную, Эрдёш предложил выбрать цвета случайно и посчитать вероятность удачи. Если вероятность получить рисунок без запрещённой группы больше нуля, значит хотя бы один подходящий рисунок точно существует.
Так появился вероятностный метод . Сегодня его используют далеко за пределами теории графов: в дискретной математике, информатике, проверке чисел на простоту, проектировании схем и работе с данными. Метод помогает там, где нужный объект трудно показать руками, но можно доказать, что случайный выбор иногда его создаёт.
С числами Рамсея этот подход дал мощный старт, а затем почти перестал двигаться в самой трудной зоне. Особенно упорно сопротивлялись случаи, где запрещённые красные и синие группы имеют одинаковый или почти одинаковый размер. Эрдёш доказал, что для группы размера k число Рамсея больше примерно 2 в степени k/2. Для k = 1000 это даёт величину около 2^500. За десятилетия оценку удалось поднять лишь примерно до 2^501.
Новая работа изменила не саму идею случайности, а способ выбирать цвета. В классическом варианте каждая линия получает цвет независимо, как при броске монеты. Новый подход связывает цвет линии с геометрией.
Сначала точки случайно размещают на поверхности сферы в пространстве с очень большим числом измерений. Затем смотрят на расстояние между каждой парой точек. Если две точки далеко друг от друга, линию между ними красят в красный цвет. Если близко - в синий. Цвета больше не появляются отдельно друг от друга: весь рисунок зависит от расположения точек на одной общей поверхности.
Такой приём помогает бороться с большими красными группами. Чтобы получить красную группу, нужно много точек, где каждая находится далеко от всех остальных. Геометрия высокой размерности сильно ограничивает такие наборы. Но возникает риск с другой стороны: близкие точки чаще дают синие группы. Поэтому авторам нужно было доказать, что новый способ действительно помогает, а не просто переносит проблему из красного цвета в синий.
Главная часть доказательства опирается на необычное свойство пространств с большим числом измерений. Если провести линии от центра такой сферы к случайно выбранным точкам, большинство линий окажется почти под прямым углом друг к другу. Для обычной трёхмерной сферы такая картина не кажется естественной, но в высокой размерности она становится типичной. Благодаря этому расстояния между точками можно оценивать гораздо строже.
После этих оценок авторы показали: при правильных параметрах остаётся ненулевая вероятность получить раскраску без запрещённых одноцветных групп. Значит нужная раскраска существует. Доказательство заняло около года и выросло в работу примерно на 40 страниц.
Результат не решает главный диагональный случай, где красные и синие группы имеют одинаковый размер. Но он улучшает оценки для почти диагональных чисел Рамсея, например когда запрещённая красная группа примерно вдвое меньше синей. В этой зоне заметного продвижения не было около 50 лет.
Численный выигрыш очень мал. В одной формуле к прежнему основанию степени добавилась величина порядка 10^-21. И вроде как такая прибавка выглядит почти ничтожной, но в теории графов важен сам факт улучшения: старая задача снова поддалась новому приёму.
Работа уже дала продолжение. Другие математики упростили геометрическую модель и ещё немного улучшили оценки. Похожие идеи начали применять к задачам с тремя цветами, где возможных одноцветных ловушек становится больше.
- Источник новости
- www.securitylab.ru
