Гіпотеза Ердеша — Бура

Гіпотеза Ердеша — Бура — математична проблема, що стосується числа Рамсея на розріджених графах. Гіпотезу названо на честь Пала Ердеша та Стефана Бура. Гіпотеза стверджує, що число Рамсея в будь-якому сімействі розріджених графів має майже лінійне зростання залежно від кількості вершин графа.

2017 року Чунбум Лі (Choongbum Lee) повністю довів цю гіпотезу (таким чином, тепер вона є теоремою).

Визначення

Якщо G — неорієнтований граф, то виродженість G — це найменше число p, таке, що будь-який підграф G містить вершину степеня p або менше. Граф A з виродженістю p називають p-виродженим. p-виродженість графа можна визначити також як можливість звести граф до порожнього послідовним видаленням вершин степеня p і менше.

З теореми Рамсея випливає, що для будь-якого графа G існує таке ціле $r(G)$, зване числом Рамсея для G, що будь-який повний граф з не менш ніж $r(G)$ вершинами, ребра якого пофарбовано в червоний та синій кольори, містить монохромну копію графа G. Наприклад, число Рамсея для трикутника дорівнює 6: незалежно від того, як розфарбовано ребра повного графа з шести вершин у червоний та синій кольори, завжди знайдеться червоний або синій трикутник.

Гіпотеза

1973 року Пал Ердеш і Стефан Бур висловили таку гіпотезу:

Для будь-якого цілого p існує константа c_p така, що будь-який p-вироджений граф G на n вершинах має число Рамсея, що не перевищує c_p n.

Таким чином, якщо граф G з n вершинами є p-виродженим, то одноколірна копія графа G повинна існувати в будь-якому пофарбованому двома кольорами графі з c_p n вершинами.

Проміжні результати

До того, як гіпотезу було повністю доведено, вона була доведена для окремих випадків. Так, доведення гіпотези для графів з обмеженим степенем вершин наведено в статті Хватала, Редля, Семереді і Троттера. Їхнє доведення приводить до дуже великого значення c_p. Константу покращено в статті Ненсі Ітон (Nancy Eaton) та в статті Рональда Грема.

Відомо, що гіпотеза правильна для p-обмежених графів, які включають графи з обмеженим найбільшим степенем вершин, планарні графи і графи, що не містять розщеплення K_p (тут під розщепленням розуміється операція, обернена до стягування, тобто заміна дуги двома дугами з доданням вершини).

Відомо, що гіпотеза істинна для розщеплених графів, тобто графів, у яких жодні дві сусідні вершини не мають степеня, більшого за два.

Для довільного графа відомо, що число Рамсея обмежене функцією, яка росте трохи надлінійно. А саме, Фокс і Судаков показали, що існує константа c_p така, що для будь-якого p-виродженого графа G з n вершинами

$r(G)\leqslant 2^{c_{p}{\sqrt {\log n}}}n.$

Посилання

• Стефан Бур (Stefan Burr), Пал Ердеш. Нескінченні та скінченні множини = Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. 1. — Amsterdam : North-Holland, 1975. — Т. 10. — С. 214–240. — (Colloq. Math. Soc. János Bolyai).
• Гуантано Чен (Guantao Chen), Річард Шелп (Richard H. Schelp). Графи з лінійно обмеженими числами Рамсея // Journal of Combinatorial Theory, Series B. — 1993. — Т. 57, вип. 1. — С. 138–149. — DOI:10.1006/jctb.1993.1012..
• Рональд Грем (Ronald Graham), Войцех Редль (Vojtěch Rödl), Анджей Ручинські (Andrzej Rucínski). Пал Ердеш і його математика (Будапешт, 1999) // Combinatorica. — 2001. — Т. 21, вип. 2. — С. 199–209. — DOI:10.1007/s004930100018.