Гипотеза Эрдёша — Бура

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

Эта гипотеза была полностью доказана Choongbum Lee в 2017 году (и таким образом теперь она является теоремой)^[1]

ОпределенияПравить

Если G — неориентированный граф, то вырожденность G — это минимальное число p, такое, что любой подграф G содержит вершину степени p или меньше. Граф A c вырожденностью p называется p-вырожденным. p-вырожденность графа можно определить также как возможность свести граф к пустому путём последовательного удаления вершин степени p и меньше.

Из теоремы Рамсея следует, что для любого графа G существует такое целое $\text{[math]}$ $\text{[math]}$ $r(G)$ , называемое числом Рамсея для G, что любой полный граф с не менее чем $\text{[math]}$ $\text{[math]}$ $r(G)$ вершинами, рёбра которого выкрашены в красный и синий цвета, содержит монохромную копию графа G. Например, число Рамсея для треугольника равно 6: независимо от того, каким образом раскрашены рёбра полного графа из шести вершин в красный и синий цвета, всегда найдётся красный или синий треугольник.

ГипотезаПравить

В 1973 году Пол Эрдёш и Стефан Бур высказали следующую гипотезу:

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

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

Промежуточные результатыПравить

До того как гипотеза была полностью доказана, она была доказана в некоторых частных случаях, так, доказательство гипотезы для графов с ограниченной степенью вершин приведено в статье Хватала, Рёдля, Семереди и Троттера^[2]. Их доказательство приводит к очень большому значению c_p. Константа была улучшена в статье Нэнси Итон (Nancy Eaton)^[3] и в статье Рональда Грэма (Ronald Graham)^[4].

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

Известно, что гипотеза верна для расщепленных графов, то есть графов, у которых никакие две соседние вершины не имеют степень, большую двух^[6].

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

\text{[math]}

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

ПримечанияПравить

↑ Choongbum Lee. Ramsey numbers of degenerate graphs // Annals of Mathematics. — 2017. — Т. 185, вып. Issue 3. — С. 791-829. — arXiv:1505.04773. Архивировано 24 апреля 2019 года.
↑ Вацлав Хватал (Václav Chvátal), Войцех Рёдль (Vojtěch Rödl), Эндре Семереди, Вильям Троттер (William Trotter, Jr.). Число Рамсея для графа с ограниченной степенью вершин. (англ.) = The Ramsey number of a graph with bounded maximum degree // Journal of Combinatorial Theory, Series B. — 1983. — Vol. 34, iss. 3. — P. 239–243. — doi:10.1016/0095-8956(83)90037-0.
↑ Нэнси Итон (Nancy Eaton). Число Рамсея для редких графов = Ramsey numbers for sparse graphs // Discrete Mathematics. — 1998. — Т. 185, вып. 1–3. — С. 63–75. — doi:10.1016/S0012-365X(97)00184-2.
↑ Рональд Грэм (Ronald Graham), Войцех Рёдль (Vojtěch Rödl), Анджей Ручински (Andrzej Rucínski). Графы с линейными числами Рамсея = On graphs with linear Ramsey numbers // 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.
↑ Войцех Рёдль (Vojtěch Rödl), Робин Томас (Robin Thomas). Математика Пола Эрдёша, II = The Mathematics of Paul Erdős, II / Под ред. Рональда Грэма (Ronald Graham), Ярослава Нешетрила (Jaroslav Nešetřil). — Springer-Verlag, 1991. — С. 236–239. Архивная копия от 17 апреля 2007 на Wayback Machine
↑ Нога Алон (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.
↑ Якоб Фокс (Jacob Fox), Бенни Судаков (Benny Sudakov). Два замечания по поводу гипотезы Эрдёша–Бура (англ.) = Two remarks on the Burr–Erdős conjecture // 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). Графы с линейно ограниченными числами Рамсея = Graphs with linearly bounded Ramsey numbers // 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) = Paul Erdős and his mathematics (Budapest, 1999) // Combinatorica. — 2001. — Т. 21, вып. 2. — С. 199–209. — doi:10.1007/s004930100018.

[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.). Число Рамсея для графа с ограниченной степенью вершин. (англ.) = The Ramsey number of a graph with bounded maximum degree // 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). Число Рамсея для редких графов = Ramsey numbers for sparse graphs // 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). Графы с линейными числами Рамсея = On graphs with linear Ramsey numbers // 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] Войцех Рёдль (Vojtěch Rödl), Робин Томас (Robin Thomas). Математика Пола Эрдёша, II = The Mathematics of Paul Erdős, II / Под ред. Рональда Грэма (Ronald Graham), Ярослава Нешетрила (Jaroslav Nešetřil). — Springer-Verlag, 1991. — С. 236–239. Архивная копия от 17 апреля 2007 на Wayback Machine

[6] Нога Алон (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.

[7] Якоб Фокс (Jacob Fox), Бенни Судаков (Benny Sudakov). Два замечания по поводу гипотезы Эрдёша–Бура (англ.) = Two remarks on the Burr–Erdős conjecture // European Journal of Combinatorics : журнал. — 2009. — Vol. 30, iss. 7. — P. 1630–1645. — doi:10.1016/j.ejc.2009.03.004.

[1]

[2]

[3]

[4]

[5]

[6]

[7]