Гіпотеза сендвіча Кіма — Ву (, також sandwich conjecture) — колишня математична гіпотеза в теорії випадкових графів, сформульована 2004 року південнокорейським математиком Чон Хан Кімом і в’єтнамсько-американським математиком Ван Ву. Вона стверджувала, що випадковий -регулярний граф за можна зі спільним розподілом розмістити між двома біноміальними випадковими графами з майже такою самою густиною ребер.
Гіпотеза пов'язує дві основні моделі випадкових графів. У моделі кожне можливе ребро з'являється незалежно з імовірністю , тоді як у випадковому регулярному графі кожна вершина має рівно сусідів, через що появи різних ребер залежать одна від одної. Сендвіч дає змогу переносити багато результатів із простішої для аналізу моделі на випадкові регулярні графи.
У жовтні 2025 року Наталі Бегаг, Даніель Ількович і Річард Монтгомері оприлюднили доведення гіпотези для всього передбаченого діапазону . Результат завершив понад двадцятирічну послідовність часткових доведень.
Передумови
У біноміальному випадковому графі задано вершин, а кожне з можливих ребер додається незалежно з імовірністю . Незалежність ребер дає змогу безпосередньо використовувати стандартні ймовірнісні оцінки та робить цю модель однією з найкраще досліджених у теорії випадкових графів.
Граф , натомість, вибирають рівномірно з усіх простих -регулярних графів на позначених вершинах; при цьому має бути парним. Наявність одного ребра впливає на можливість появи інших, оскільки степінь кожної вершини наприкінці повинен дорівнювати точно . Через ці залежності багато задач для значно складніші, ніж відповідні задачі для .
Якщо взяти , середній степінь вершини в приблизно дорівнює . Кім і Ву запропонували значно сильніший зв'язок, ніж просто близькість середніх степенів: вони припустили, що обидві моделі можна побудувати на одному ймовірнісному просторі так, щоб один граф фактично містився в іншому.
Формулювання
Нехай задовольняє
тобто при . Гіпотеза стверджувала, що існують
і
а також спільний розподіл випадкових графів , для якого
і
Отже, з імовірністю, що прямує до одиниці, випадковий регулярний граф одночасно містить трохи рідший біноміальний граф і сам міститься в трохи густішому. Назва «сендвіч» походить від цього подвійного включення.
Умова істотна. Коли очікуваний степінь у має порядок лише , степені окремих вершин можуть відхилятися від середнього на сталу частку, що перешкоджає настільки тісному включенню між біноміальним і регулярним графами.
Значення
Основна перевага сендвіча полягає в перенесенні властивостей між моделями. Нехай деяка властивість графа є монотонно зростаючою: якщо вона виконується для графа, то зберігається після додавання ребер. Тоді з
випливає, що будь-яка така властивість графа виконується і для . Прикладом є існування гамільтонового циклу або заданого підграфа.
Верхнє включення
аналогічно дає контроль над властивостями, що зберігаються при видаленні ребер. Обидві сторони сендвіча разом дозволяють оцінювати й числові параметри графа, зокрема хроматичне число, число незалежності та діаметр, порівнюючи їх із відповідними параметрами біноміальних графів близької густини.
Гіпотеза тому мала характер загального інструмента: замість окремого складного доведення для кожної властивості випадкового регулярного графа можна в багатьох випадках використати вже відомий результат для і перенести його через включення.
Історія
Кім і Ву
Кім і Ву сформулювали гіпотезу у статті Sandwiching random graphs: universality between random graph models, опублікованій 2004 року в журналі Advances in Mathematics. У тій самій роботі вони довели послаблений варіант для
Нижню частину сендвіча — включення біноміального графа у випадковий регулярний — вони отримали без дефекту. Для верхньої частини замість точного включення було отримано обмеження на максимальний степінь графа, утвореного ребрами , відсутніми у .
Цього вже було достатньо для перенесення низки монотонних властивостей, однак повного сендвіча результат не давав.
Одностороннє вкладення
У 2017 році Анджей Дудек, Алан Фріз, Анджей Руцинський і Матас Шилейкіс значно розширили діапазон, у якому можна побудувати нижню частину сендвіча. Вони дослідили випадкові регулярні гіперграфи й показали включення відповідної моделі Ердеша — Реньї у випадковий регулярний гіперграф; для звичайних графів це охопило режим .
Результат стосувався лише включення
тому питання про щільний біноміальний надграф залишалося відкритим.
Повний сендвіч для великих степенів
У 2019 році Пу Гао, Михайло Ісаєв і Брендан Маккей оприлюднили роботу, в якій уперше отримали точні включення з обох сторін для широкого діапазону великих степенів. Вони довели гіпотезу для ; подальша журнальна версія охопила, зокрема, густий режим
Ті самі автори згодом значно знизили потрібний степінь, довівши сендвіч для . Таким чином, перед остаточним розв'язанням залишався проміжок між передбаченим Кімом і Ву порядком і четвертим степенем логарифма.
Доведення гіпотези
У 2023 році Бегаг, Ількович і Монтгомері почали шукати спосіб поширити на решту діапазону процедуру спільної побудови, розвинену в попередніх роботах Гао, Ісаєва і Маккея. 23 жовтня 2025 року вони оприлюднили препринт A proof of the Kim-Vu sandwich conjecture, в якому довели твердження для всіх
Це точно відповідає асимптотичному діапазону, сформульованому Кімом і Ву 2004 року. Отже, після більш ніж двадцяти років часткових результатів гіпотезу було доведено в повному обсязі.
Ідея доведення
Доведення Бегаг, Ільковича і Монтгомері аналізує природну процедуру спільної побудови випадкового біноміального та випадкового регулярного графів. Для нижньої частини сендвіча ребра поступово додають так, щоб кожне ребро, прийняте до біноміального графа, одночасно належало регулярному графу. Додаткові ребра регулярного графа вибирають із залежними від поточного стану ймовірностями, необхідними для збереження правильного розподілу кінцевого -регулярного графа.
Для верхньої частини використовують споріднену конструкцію у зворотному напрямку: процес починається з графів із великою кількістю ребер, після чого ребра послідовно видаляються так, щоб у кінці регулярний граф містився в біноміальному графі з параметром .
Основна технічна проблема полягає в оцінюванні умовної ймовірності того, що конкретне ребро належить рівномірно випадковому регулярному доповненню вже побудованої частини графа. Автори контролюють ці ймовірності за допомогою перемикань між регулярними графами та підрахунку чергованих шляхів. Такий контроль дозволяє підтримувати потрібну спільну побудову аж до режиму .
Результат не означає, що і мають однаковий розподіл. Він встановлює існування спеціального спільного розподілу, за якого три графи мають свої правильні маргінальні розподіли й водночас із високою ймовірністю задовольняють вкладення .
Наслідки
Після доведення гіпотези результати про біноміальні випадкові графи можна систематично застосовувати до випадкових регулярних графів у всьому режимі , якщо відповідна властивість або параметр сумісні з сендвічем.
Зокрема, для монотонних властивостей нижнього або верхнього включення часто достатньо самого по собі. Для параметрів, значення яких необхідно обмежити одночасно зверху і знизу, використовують обидві частини сендвіча. У попередніх роботах цей підхід застосовували до гамільтоновості, хроматичного числа, діаметра, числа незалежності, появи заданих підграфів і порогових явищ у випадкових графах.
Доведення також дало нові інструменти для дослідження інших моделей із залежними ребрами. Після розв'язання початкової гіпотези дослідники розглядають сильніші варіанти спільної побудови та сендвічі між іншими класами випадкових регулярних і біноміальних структур.
Див. також
Випадковий граф Регулярний граф Модель Ердеша — Реньї Імовірнісний метод Гамільтонів граф
Примітки