Математици доказаха хипотезата за „сандвича“ и пренаписаха десетки теореми наведнъж

Математици са доказали хипотезата на Ким и Ву, която повече от 20 години пречеше на пряката връзка между два от най-важните типа случайни графи. Натали Бихайг, Даниел Илкович и Ричард Монтгомъри изградиха строг „сандвич“, в който сложен случаен редовен граф с голяма вероятност се оказва между два много по-добре изучени биномиални графа с почти същата плътност. Резултатът позволява цели класове вече известни теореми да се пренесат върху регулярните графи, вместо всеки път да се доказват наново.

Пълното доказателство се появи под формата на препринт през октомври 2025 година, а миналия петък списание Quanta публикува подробен анализ на работата на учените. Авторите решиха задачата, която Чон Хан Ким и Ван Ха Ву формулираха през 2004 година.

В математиката графът се състои от върхове и свързващи ги ребра. Тази абстракция позволява да се описват най-разнообразни мрежи – от връзки между компютри до социални контакти. В биномиалния модел G(n,p) всяка възможна двойка върхове получава ребро независимо с вероятност p. Независимостта значително опростява анализа, поради което през десетилетията математиците са натрупали огромен набор от резултати за такива графи. С редовните графи нещата са по-сложни. В d-редовен граф всеки връх трябва да има точно d съседи, поради което изборът на едно ребро влияе върху допустимостта на останалите. Независимостта изчезва, а много методи, които работят добре за G(n,p) престават да се прилагат директно.

Ким и Ву са предположили, че когато d нараства значително по-бързо от log n, един случаен d-редовен граф може с голяма вероятност да се помести между два биномиални графа. Долният граф трябва да се побира изцяло в регулярния, а регулярният, от своя страна, да се побира изцяло в горния. Вероятностите за поява на ребра и в двата външни графа при това се доближават до d/n.

Смисълът на „сандвича“ става по-ясен чрез свойствата, които се запазват при добавяне или премахване на ребра. Ако долният биномиален граф вече притежава свойство, което не изчезва след добавяне на ребра, това свойство автоматично се придобива и от съдържащия го редовен граф. Горният граф позволява да се правят аналогични разсъждения и в обратната посока. Ето защо един резултат за връзката между моделите замества множество отделни доказателства.

Основният проблем не се състоеше в това да се построят три сходни графа поотделно. Математиците е трябвало да свържат случайните процеси така, че разпределенията да останат правилни и едновременно с това да се осъществи вграждането на един граф в друг. Бихайг, Илкович и Монтгомъри решиха задачата, като развиха метода, предложен в по-ранна работа на Пу Гао, Михаил Исаев и Брендан Макей.

За долната половина на „сандвича“ изследователите на практика изграждат успоредно биномиален и редовен граф, като добавят ребра стъпка по стъпка. Ако поредното ребро се появи в биномиалния граф, то се добавя и в регулярния. Когато реброто липсва в биномиалния модел, специална променяща се вероятност определя дали то ще е необходимо за регулярния граф, така че в края на процеса всеки връх да получи точно необходимия брой връзки. Горната половина авторите са получили по огледален начин. Процесът започва с графи, съдържащи всички възможни ребра, след което връзките последователно се премахват, докато регулярният граф не се окаже вътре в биномиалния. Този подход е позволил да се докаже изискваното вграждане във целия диапазон d ≫ log n, заявен в първоначалната хипотеза.

До тази нова работа математиците постепенно са обхващали отделни диапазони от параметри. Гао, Исаев и Макей са получили пълноценен „сандвич“ за достатъчно гъсти редовни графи, а последващите подобрения са довели границата приблизително до d ≫ log4 n. Предишните методи вече позволяваха да се пренесат резултатите за хамилтоновите цикли, хроматичното число, диаметъра, независимите множества и фазовите преходи, но не обхващаха целия режим, предсказан от Ким и Ву.

Новата работа запълва оставащата празнина. Математикът Гил Калаи нарече резултата „метатеорема“, тъй като ценността на доказателството не се състои само в решаването на един-единствен въпрос. Връзката между двата модела превръща обширната библиотека от знания за биномиалните графи в инструмент за изследване на редовните графи, а старите многостранични аргументи в редица случаи могат да бъдат заменени със значително по-кратки заключения.

Практическият ефект не означава, че инженерите вече ще могат с един нов алгоритъм да оптимизират интернет или социалните мрежи. Резултатът се отнася преди всичко към вероятностната комбинаторика. Но случайните графи служат като базови модели при изучаването на големи мрежови структури, поради което по-тясната връзка между двата фундаментални модела дава на математиците универсален начин за анализ на системи, в които броят на връзките между възлите е строго ограничен.