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

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

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

Визначення

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

З (теореми Рамсея) випливає, що для будь-якого графа G існує таке ціле ${\displaystyle r(G)}$, зване числом Рамсея для G, що будь-який повний граф з не менш ніж ${\displaystyle 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 вершинами

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

Примітки

1. Choongbum Lee. Ramsey numbers of degenerate graphs // Annals of Mathematics. — 2017. — Т. 185, вип. Issue 3. — С. 791-829. — arXiv:1505.04773. з джерела 24 квітня 2019.
2. Вацлав Хватал (Václav Chvátal), Войцех Редль (Vojtěch Rödl), Ендре Семереді, Вільям Троттер (William Trotter, Jr.). Число Рамсея для графа з обмеженим степенем вершин. // Journal of Combinatorial Theory, Series B. — 1983. — Vol. 34, iss. 3. — P. 239–243. — DOI:10.1016/0095-8956(83)90037-0.
3. Ненсі Ітон (Nancy Eaton). Число Рамсея для розріджених графів // Discrete Mathematics. — 1998. — Т. 185, вип. 1–3. — С. 63–75. — DOI:10.1016/S0012-365X(97)00184-2.
4. Рональд Грем (Ronald Graham), Войцех Редль (Vojtěch Rödl), Анджей Ручинські (Andrzej Rucínski). Графи з лінійними числами Рамсея // Journal of Graph Theory. — 2000. — Т. 35, вип. 3. — С. 176–192. — DOI:10.1002/1097-0118(200011)35:3<176::AID-JGT3>3.0.CO;2-C.
5. Нога Алон (Noga Alon). Subdivided graphs have linear Ramsey numbers // Journal of Graph Theory. — 1994. — Т. 18, вип. 4. — С. 343–347. — DOI:10.1002/jgt.3190180406., Юшенг Лі (Yusheng Li), Сесіль Руссо (Cecil C. Rousseau), Любомир Солтес (Ľubomír Soltés). Ramsey linear families and generalized subdivided graphs // Discrete Mathematics. — 1997. — Т. 170, вип. 1–3. — С. 269–275. — DOI:10.1016/S0012-365X(96)00311-1.
6. Якоб Фокс (Jacob Fox), Бенні Судаков (Benny Sudakov). Два зауваження з приводу гіпотезы Ердеша — Бура // European Journal of Combinatorics : журнал. — 2009. — Vol. 30, iss. 7. — P. 1630–1645. — DOI:10.1016/j.ejc.2009.03.004.

Посилання

• (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.