Русская Википедия:Гипотеза Эрдёша — Бура
Гипотеза Эрдёша — Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах. Гипотеза названа в честь Пала Эрдёша и Стефана Бура. Гипотеза утверждает, что число Рамсея в любом семействе разреженных графов должно иметь почти линейный рост в зависимости от числа вершин графа.
Эта гипотеза была полностью доказана Choongbum Lee в 2017 году (и таким образом теперь она является теоремой)[1]
Определения
Если G — неориентированный граф, то вырожденность G — это минимальное число p, такое, что любой подграф G содержит вершину степени p или меньше. Граф A c вырожденностью p называется p-вырожденным. p-вырожденность графа можно определить также как возможность свести граф к пустому путём последовательного удаления вершин степени p и меньше.
Из теоремы Рамсея следует, что для любого графа G существует такое целое <math>r(G)</math>, называемое числом Рамсея для G, что любой полный граф с не менее чем <math>r(G)</math> вершинами, рёбра которого выкрашены в красный и синий цвета, содержит монохромную копию графа G. Например, число Рамсея для треугольника равно 6: независимо от того, каким образом раскрашены рёбра полного графа из шести вершин в красный и синий цвета, всегда найдётся красный или синий треугольник.
Гипотеза
В 1973 году Пол Эрдёш и Стефан Бур высказали следующую гипотезу:
- Для любого целого p существует константа cp, такая, что любой p-вырожденный граф G на n вершинах имеет число Рамсея, не превышающее cp n.
Таким образом, если граф G с n вершинами является p-вырожденным, то монохроматическая копия графа G должна существовать в любом окрашенном двумя цветами графе с cp n вершинами.
Промежуточные результаты
До того как гипотеза была полностью доказана, она была доказана в некоторых частных случаях, так, доказательство гипотезы для графов с ограниченной степенью вершин приведено в статье Хватала, Рёдля, Семереди и Троттера[2]. Их доказательство приводит к очень большому значению cp. Константа была улучшена в статье Нэнси Итон (Nancy Eaton)[3] и в статье Рональда Грэма (Ronald Graham)[4].
Известно, что гипотеза верна для p-ограниченных графов, которые включают в себя графы с ограниченной максимальной степенью вершин, плоские графы и графы, не содержащие расщепления Kp (здесь под расщеплением понимается операция, обратная стягиванию, то есть замена дуги на две дуги с добавлением вершины)[5].
Известно, что гипотеза верна для расщепленных графов, то есть графов, у которых никакие две соседние вершины не имеют степень, большую двух[6].
Для произвольного графа известно, что число Рамсея ограничено функцией, которая растет слегка сверхлинейно. А именно, Фокс и Судаков[7] показали, что существует константа cp, такая, что для любого p-вырожденного графа G с n вершинами
- <math>r(G) \leqslant 2^{c_p \sqrt{\log n}} n.</math>
Примечания
Ссылки
