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

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

Определения

Если G — не ориентированный граф , то вырожденность G — это минимальное число p , такое, что любой подграф G содержит вершину степени p или меньше. Граф A c вырожденностью 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) и в статье Рональда Грэма (Ronald Graham) .

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

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

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

${\displaystyle 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). Графы с линейно ограниченными числами Рамсея = Graphs with linearly bounded Ramsey numbers // Journal of Combinatorial Theory, Series B. — 1993. — Т. 57 , вып. 1 . — С. 138–149 . — doi : . .
• Рональд Грэм (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 : .