Через 80 років математики модернізують метод Ердіша

· Наука

Через 80 років математики модернізують метод Ердіша

Математики після 80 років вдосконалили відомий метод Ердіша, що революціонізував теорію графів.

Після 80 років математики вдосконалили відомий «Метод Ердіша»

У 1947 році блукаючий угорський математик Поль Ердіш представив те, що згодом стане одним з найпотужніших інструментів математики. Він прагнув довести існування певного типу об’єкта — в даному випадку мережі, що складається з взаємопов’язаних вузлів. Але дивно, що його довід не вказував, як її побудувати. Натомість він показав, що, якщо ви розглянете всі можливі мережі і оберете одну випадково, шанси знайти мережу з бажаною властивістю більші за нуль. Це означає, що бажана мережа десь існує, навіть якщо ви майже нічого про неї не знаєте.

Підхід Ердіша, відомий як ймовірнісний метод, був простим, але революційним. До його появи, «якщо я кажу вам, що певні об’єкти існують, ви скажете мені: „Покажи мені“», — зазначив Бенні Судаков, математик Швейцарського федерального технологічного інституту в Цюриху. «Але певні об’єкти такі незвичайні, що нам важко усвідомити, що вони взагалі існують».

Техніка Ердіша подолала цю труднощі, продемонструвавши, що випадковість може бути використана у способах, про які математики ніколи не уявляли. «Це було просто вражаюче — використовувати випадковість», — сказав Джоел Спенсер з Нью-Йоркського університету. «Тепер це базовий рівень».

Сьогодні ймовірнісний метод використовується в математиці і комп’ютерних науках — для визначення, чи є число простим, для проєктування кращих схем, або для очищення даних без упровадження упереджень.

Дослідники зміцнили цю техніку різними способами. Але початкова сфера дії ймовірнісного методу — запитання про мережі, яке Ердіш намагався вирішити — за вісім десятиліть зазнала дуже мало прогресу. Протягом восьми десятиліть математики не могли істотно поліпшити рішення, яке запропонував Ердіш.

Але тепер це нарешті починає змінюватися.

Голос у пустелі

Уявіть мережу вузлів — граф, у якому кожна пара вузлів з’єднана ребром.
alt

Тепер розфарбуйте кожне ребро або в червоний, або в синій колір, але з одним попередженням: не створюйте великих кластерів вузлів, всі з'єднаних ребрами одного кольору. Ці заборонені структури називаються монохроматичними клік. Ось монохроматична клік, що складається з трьох вузлів, яку математики називають клікою розміру 3:

Якщо ваш граф має достатньо вузлів, уникнути створення монохроматичної кліки буде неможливо, незалежно від того, як ви розфарбуєте ребра. Наприклад, якщо ви хочете уникнути кліки розміру 3, ваш граф може мати не більше п’яти вузлів. Граф з шістьма вузлами завжди міститиме одну:

Математики стверджують, що «число Рамсі» для кліки розміру 3, позначене R(3), дорівнює 6. Числа Рамсі вимірюють, як великі графи можуть ставати, перш ніж заборонений шаблон неминуче з’явиться.

Ви також можете мати числа Рамсі для червоних і синіх кліків різного розміру. Наприклад, ви можете розфарбувати граф з восьми вузлів, щоб він не мав червоних кліків розміру 3 або синіх кліків розміру 4. Але, якщо ви додасте ще один вузол до графу, ви будете змушені створити принаймні одну червону або синю кліку. Отже, число Рамсі R(3, 4) дорівнює 9.

Коли кліки, які ви хочете уникнути, стають більшими, проблема стає дедалі важчою для розв'язання. Математики змогли обчислити лише кілька з найменших чисел Рамсі. «Дуже важко створити щось, що не має структури», — сказав Поль Хорн з Університету Денвера. «Можливо, тому що ми люди і підпорядковані своїм упередженням».

Тому математики витратили десятиліття, намагаючись знайти кращі апроксимації чисел Рамсі. Саме це Ердіш намагався зробити, коли представив свій ймовірнісний метод у 1947 році. Замість того, щоб будувати графи без кліків безпосередньо, він розглянув всі можливі способи розфарбувати граф, а потім показав, що принаймні деяка ненульова частка з них повинна бути безкліковою.

Ердіш використав цей аргумент, щоб довести, що, якщо ви забороните червоні і сині кліки розміру k, число Рамсі R(k) повинно бути більшим за $latex \sqrt{2}^k$. Числа Рамсі для однакових за розміром червоних і синіх кліків називаються діагональними числами Рамсі. Ердіш міг аналогічно отримати нижню межу для «не діагональних» чисел Рамсі R(k, l), у яких забороняються червоні кліки розміру k і сині кліки розміру l.

Доказ складався всього з кількох рядків. Але він був абсолютно несподіваним.

Спочатку математики не хотіли слідувати його прикладу. Вони хотіли конкретних прикладів. «Протягом багатьох років Ердіш був як голос у пустелі», — сказав Спенсер. «Він отримував ці дивовижні результати, використовуючи випадковість, і люди ніколи раніше цього не робили».

Але незабаром ймовірнісний метод довів свою цінність. Тепер це одна з найпоширеніших технік у «дискретній» математиці, дослідженні об’єктів (як графи), які є окремими, а не безперервними. І вона проникла з математики в фізику і комп’ютерні науки. «Випадковість, я думаю, просто допомагає нам дістатися до чогось, що інакше було б дуже ефемерним», — зазначив Хорн.

Нещодавно математики змогли адаптувати метод Ердіша, щоб отримати кращі оцінки чисел Рамсі, де заборонені кліки сильно відрізняються за розміром. Наприклад, у 2025 році Хорн і троє колег використали оновлену версію методу Ердіша, щоб довести більш точну нижню межу для R(3, l), де l зростає довільно великою. (Ця робота, в свою чергу, призвела до великих зрушень у теорії графів.)

Але коли мова йшла про числа Рамсі, де заборонені кліки не відрізнялися за розміром — особливо діагональні числа Рамсі, об'єкт первинного інтересу Ердіша, — ймовірнісний метод зупинився. Припустимо, ви забороняєте кліки розміру 1,000. Ердіш показав, що R(1,000) повинен бути більшим за близько 2500. Вісім десятиліть зусиль змінили цю межу до приблизно 2501. Подібно, з 1970-х років прогрес залишався на місці для не діагональних чисел Рамсі, де заборонені червоні та сині кліки відносно великі.

Тоді з'явився аспірант без особливих знань у теорії Рамсі.

Корельоване розфарбування

Вудзє Шен провів свої перші кілька семестрів в Університеті Цинхуа, зосередившись головним чином на геометрії та топології. Але навесні 2024 року він натрапив на статтю про числа Рамсі, яка захопила його.

Він знав, як працює метод Ердіша: ви кидаєте монету, щоб визначити колір кожного ребра вашого графа: герб — ребро червоне, решка — синє. Потім ви обчислюєте ймовірність того, що отримаєте розфарбування без кліків. Але це обчислення стає дуже складним для більших графів. Шен замислився, чи існує випадкова модель, яка могла б виробляти розфарбування без кліків більш ефективно, ніж підхід Ердіша.

З урахуванням підготовки Шена, не дивно, що модель, яку він запропонував, включала геометрію. Зазвичай розфарбування графів не передбачає геометрії: для matematicians важливо лише, які вузли з’єднані червоним ребром, а які — синім. Що вузли сидять близько один до одного чи розкидані по простору, не має значення.

Але Шен хотів використати геометрію, щоб допомогти йому вирішити, які ребра розфарбувати червоним, а які — синім. Зокрема, він хотів використовувати геометрію високовимірних сфер — тобто наборів точок, які рівновіддалені від однієї центральної точки.

Ці сфери «повністю псують наші інтуїції», сказав Девід Конлон з Каліфорнійського технологічного інституту. Багато з наших уявлень про те, як виглядає сфера, більше не вірні у високих вимірах: високо-вимірна сфера має малий об’єм і величезну поверхневу площу, а більшість її точок знаходиться на екваторі. Це «досить складно для роботи», — додав Судаков.

Але Шен і двоє колег — Цзі Ма, який відвідував Цинхуа, щоб викладати в осінньому семестрі, та аспірант Ма Шенцзє Цзе — захотіли спробувати. Їхній метод: спочатку розмістіть вузли один за одним на поверхні високо-вимірної сфери. Вибирайте позицію кожного вузла випадково — будь-яка точка на сфері підходить, і розміщення кожного вузла не вплине на розміщення жодного іншого вузла.

Коли ви розмістили всі вузли, розфарбуйте кожне ребро на основі відстані між вузлами. Якщо дві точки розташовані на відстані більше ніж певна фіксована відстань (що буде відбуватися з ймовірністю менше за 1/2), розфарбуйте ребро, що з’єднує їх, в червоний. Якщо вони ближче, розфарбуйте ребро в синій колір.

З цим підходом графи, які створили Ма, Шен і Цзе, менше ймовірно формують червону кліку. Це тому, що для формування великої червоної кліки вам потрібно багато вузлів, які всі далеко один від одного. Оскільки простору на сфері обмежено, це малоймовірно.

Але є підводний камінь. За тим же принципом, цей метод також виробляє більшу частку розфарбувань з синіми кліками, ніж у Ердіша. «Є компроміс, що виглядає так, ніби він дійсно допомагає в одному кольорі, але зовсім не допомагає в іншому», — сказав Конлон. «Навіщо цим займатися?»

Незважаючи на це, Ма, Шен і Цзе були сповнені надії. Вони протестували свій метод на менших графах, і він, здавалося, працював: серед десятків тисяч поганих розфарбувань, які він згенерував, була все ж ненульова ймовірність отримати добре розфарбування без кліків. Це заспокоїло їх, що переваги можуть переважити витрати, навіть для значно більших графів.

Вони почали намагатися довести це. Ключем виявилася дуже дивна геометрія високо-вимірних сфер.

В кінцевому рахунку, щоб показати, що вони можуть уникнути кліків певного розміру, Ма, Шен і Цзе повинні були обмежити ймовірність того, що їхні випадково розміщені вузли формують кластери, які всі далеко один від одного або всі близько один до одного. Вони усвідомили, що якщо провести лінії від кожного вузла до центру сфери, то ці лінії майже всі будуть перпендикулярними або близькими до перпендикулярних. Це не відбувається, якщо ви випадково розміщуєте вузли на знайомій двовимірній сфері: більшість вузлів не лежать на перпендикулярних лініях. Але команда змогла довести, що це справедливо в набагато вищих вимірах, з якими вони працювали.

Це, в свою чергу, обмежило, як далеко вузли можуть бути один від одного — тим самим обмежуючи їх шанси сформувати монохроматичну кліку.

Після року і 40 сторінок щільних обчислень тріо опублікувало свою статтю в липні 2025 року. Вони покращили нижню межу Ердіша для чисел Рамсі — але лише коли заборонені сині кліки є більшими, ніж червоні. Коли сині кліки такі ж малі, як червоні, переваги нового підходу зникають.

Проте, коли ви хочете уникнути червоних кліків, які, наприклад, удвічі менші за блакитні, Ма, Шен і Цзе змогли підвищити швидкість зростання Ердіша з $latex ((\sqrt{5} + 1)/2)^k$ до $latex ((\sqrt{5} + 1)/2 + 10^{-21})^k$. Незважаючи на те, що зміна незначна, їхній доказ є першим поліпшенням для близькодіагональних чисел Рамсі за 50 років.

«Це щасливий випадок, і ми відчуваємо, що всі наші зусилля винагороджуються», — сказав Ма. «Але це було важко протягом тривалого часу».

«Це трохи шокуюче, що звичайна річ працює для звичайної проблеми», — сказав Джуліан Сахасрабудхе з Університету Кембриджа. Їхня техніка, на його думку, «була прихована на видному місці».

Ймовірнісна майданчик

Доказ Ма, Шена і Цзе вже згенерував хвилю подальшого прогресу. У грудні 2025 року Судаков і двоє його аспірантів різко спростили модель розфарбування команди, поліпшивши їх нові межі ще більше. Інші з тих пір використали цю модель для оцінки чисел Рамсі, що включають три кольори, а не два.

Це відповідає довгій історії ймовірнісного методу. Протягом останніх 80 років математики займалися вдосконаленням методики Ердіша, знаходячи все нові способи змішувати додаткову структуру, щоб підвищити її потужність. Неминуче, ці нові техніки довели свою корисність в інших галузях. «Це дуже родюча площадка для ідей», — зазначив Судаков.

Отже, робота Ма, Шена і Цзе є останньою главою в цій багаторічній історії. Але це також перша з тих, що за довгий час знову звертається до близькодіагональних чисел Рамсі.

Нове внесення команди — геометричний підхід — може призвести до більшого прогресу у цій впертій проблемі. Хоча ймовірнісний метод ще не вдосконалено, «він зараз дійсно дуже потужний», — сказав Спенсер. «Це дійсно так змінилося».

Оригінал: www.quantamagazine.org

Про Що? — новини науки, технологій і світу