Гіпотеза Ердеша — Бура
Гіпотеза Ердеша — Бура — математична проблема, що стосується числа Рамсея на розріджених графах. Гіпотезу названо на честь Пала Ердеша та Стефана Бура. Гіпотеза стверджує, що число Рамсея в будь-якому сімействі розріджених графів має майже лінійне зростання залежно від кількості вершин графа.
2017 року Чунбум Лі (Choongbum Lee) повністю довів цю гіпотезу (таким чином, тепер вона є теоремою)[1].
Визначення
Якщо G — неорієнтований граф, то виродженість G — це найменше число p, таке, що будь-який підграф G містить вершину степеня p або менше. Граф A з виродженістю p називають p-виродженим. p-виродженість графа можна визначити також як можливість звести граф до порожнього послідовним видаленням вершин степеня p і менше.
З теореми Рамсея випливає, що для будь-якого графа G існує таке ціле , зване числом Рамсея для G, що будь-який повний граф з не менш ніж вершинами, ребра якого пофарбовано в червоний та синій кольори, містить монохромну копію графа G. Наприклад, число Рамсея для трикутника дорівнює 6: незалежно від того, як розфарбовано ребра повного графа з шести вершин у червоний та синій кольори, завжди знайдеться червоний або синій трикутник.
Гіпотеза
1973 року Пал Ердеш і Стефан Бур висловили таку гіпотезу:
- Для будь-якого цілого p існує константа cp така, що будь-який p-вироджений граф G на n вершинах має число Рамсея, що не перевищує cp n.
Таким чином, якщо граф G з n вершинами є p-виродженим, то одноколірна копія графа G повинна існувати в будь-якому пофарбованому двома кольорами графі з cp n вершинами.
Проміжні результати
До того, як гіпотезу було повністю доведено, вона була доведена для окремих випадків. Так, доведення гіпотези для графів з обмеженим степенем вершин наведено в статті Хватала, Редля, Семереді і Троттера[2]. Їхнє доведення приводить до дуже великого значення cp. Константу покращено в статті Ненсі Ітон (Nancy Eaton)[3] та в статті Рональда Грема[4].
Відомо, що гіпотеза правильна для p-обмежених графів, які включають графи з обмеженим найбільшим степенем вершин, планарні графи і графи, що не містять розщеплення Kp (тут під розщепленням розуміється операція, обернена до стягування, тобто заміна дуги двома дугами з доданням вершини).
Відомо, що гіпотеза істинна для розщеплених графів, тобто графів, у яких жодні дві сусідні вершини не мають степеня, більшого за два[5].
Для довільного графа відомо, що число Рамсея обмежене функцією, яка росте трохи надлінійно. А саме, Фокс і Судаков[6] показали, що існує константа cp така, що для будь-якого p-виродженого графа G з n вершинами