Гипотеза Берра – Эрёса

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

Гипотезу доказал Чунгбум Ли. Итак, теперь это теорема.

Определения

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

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

Гипотеза

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

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

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

Известные результаты

Прежде чем полная гипотеза была доказана, она сначала была подтверждена в некоторых особых случаях. Для графов ограниченной степени это было доказано Хваталом и др. (1983) ; их доказательство привело к очень высокому значению cp _{, а} улучшения этой константы были сделаны Итоном (1998) и Грэмом, Рёдлом и Ручински (2000) . В более общем смысле известно, что эта гипотеза верна для p -упорядочимых графов, которые включают графы с ограниченной максимальной степенью, планарные графы графы, не содержащие подразделения K и _p . Это также известно для подразделенных графов, графов, в которых никакие две соседние вершины не имеют степени больше двух.

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

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

Ссылки

• Алон, Нога (1994), «Подразделенные графы имеют линейные числа Рамсея», Journal of Graph Theory , 18 (4): 343–347, CiteSeerX   10.1.1.106.6586 , doi : 10.1002/jgt.3190180406 , MR   1277513 .
• Берр, Стефан А .; Эрдеш, Пауль (1975), «О величине обобщенных чисел Рамсея для графов», Бесконечные и конечные множества (Коллок., Кестхей, 1973; посвящен П. Эрдешу к его 60-летию), Vol. 1 (PDF) , Коллок. Математика. Соц. Янош Бояи, том. 10, Амстердам: Северная Голландия, стр. 214–240, МР   0371701 .
• Чен, Гуантао; Шелп, Ричард Х. (1993), «Графики с линейно ограниченными числами Рамсея», Журнал комбинаторной теории, серия B , 57 (1): 138–149, doi : 10.1006/jctb.1993.1012 , MR   1198403 .
• Хватал, Вацлав ; Рёдль, Войтех; Семереди, Эндре ; Троттер, Уильям Т. младший (1983), «Число Рамсея графа с ограниченной максимальной степенью», Журнал комбинаторной теории, серия B , 34 (3): 239–243, doi : 10.1016/0095-8956 (83 )90037-0 , МР   0714447 .
• Итон, Нэнси (1998), «Числа Рамсея для разреженных графов», Discrete Mathematics , 185 (1–3): 63–75, doi : 10.1016/S0012-365X(97)00184-2 , MR   1614289 .
• Фокс, Джейкоб; Судаков, Бенни (2009), «Два замечания по гипотезе Берра – Эрдеша», Европейский журнал комбинаторики , 30 (7): 1630–1645, arXiv : 0803.1860 , doi : 10.1016/j.ejc.2009.03.004 , MR   2548655 , S2CID   8570007 .
• Грэм, Рональд ; Рёдль, Войтех; Ручинский, Анджей (2000), «О графах с линейными числами Рамсея», Journal of Graph Theory , 35 (3): 176–192, doi : 10.1002/1097-0118(200011)35:3<176::AID-JGT3 >3.0.CO;2-C , MR   1788033 .
• Грэм, Рональд ; Рёдль, Войтех; Ручинский, Анджей (2001), «О двудольных графах с линейными числами Рамсея», Пол Эрдеш и его математика (Будапешт, 1999), Combinatorica , 21 (2): 199–209, doi : 10.1007/s004930100018 , MR   1832445 , S2CID   485716
• Калай, Гил (22 мая 2015 г.), «Чунгбум Ли доказал гипотезу Берра-Эрдёша» , Комбинаторика и многое другое , получено 22 мая 2015 г.
• Ли, Чунгбум (2017), «Числа Рэмси вырожденных графов», Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi : 10.4007/annals.2017.185.3.2 , S2CID   7974973
• Ли, Юшэн; Руссо, Сесил К .; Солтес, Любомир (1997), «Линейные семейства Рамсея и обобщенные подразделенные графы», Discrete Mathematics , 170 (1–3): 269–275, doi : 10.1016/S0012-365X(96)00311-1 , MR   1452956 .
• Рёдль, Войтех; Томас, Робин (1991), «Упорядочиваемость и кликовые подразделения», у Грэма, Рональда ; Нешетржил, Ярослав (ред.), Математика Пауля Эрдеша, II (PDF) , Springer-Verlag, стр. 236–239, МР   1425217 .