В математике , то гипотеза Burr-Erdős была проблема относительно числа Рамсея из разреженных графов . Гипотеза названа в честь Стефана Берра и Пола Эрдеша и является одной из многих гипотез, названных в честь Эрдеша ; он утверждает, что число Рамсея графов в любом разреженном семействе графов должно линейно расти с увеличением числа вершин графа.
Гипотеза была доказана Чунгбом Ли (таким образом, теперь это теорема). [1]
Определения
Если G представляет собой неориентированный граф , то вырождение из G минимального числа р , такие , что каждый подграф G содержит вершину степени р или меньше. Граф с вырождением p называется p -вырожденным. Эквивалентно, p -вырожденный граф - это граф, который можно свести к пустому графу , многократно удаляя вершину степени p или меньше.
Из теоремы Рамсея следует, что для любого графа G существует наименьшее целое число, число Рамсея группы G , такое, что любой полный граф хотя бы на вершины которых ребра окрашены в красный или синий содержит монохроматический копию G . Например, число Рамсея треугольника равно 6: независимо от того, как ребра полного графа с шестью вершинами окрашены в красный или синий цвет, всегда есть либо красный треугольник, либо синий треугольник.
Гипотеза
В 1973 году Стефан Берр и Пол Эрдёш сделали следующее предположение:
- Для любого целого числа p существует константа c p, так что любой p -вырожденный граф G на n вершинах имеет число Рамсея не более c p n .
То есть, если граф G с n- вершинами является p -вырожденным, то монохроматическая копия G должна существовать в каждом полном графе с двумя краями на c p n вершинах.
Известные результаты
Прежде чем полная гипотеза была доказана, она была сначала решена в некоторых частных случаях. Это было доказано для графов ограниченной степени Chvátal et al. (1983) ; их доказательство привело к очень высокому значению c p , и улучшения этой константы были сделаны Eaton (1998) и Graham, Rödl & Rucínski (2000) . В более общем смысле , гипотеза , как известно, относится к р -arrangeable графов, который включает в себя графы с ограниченной максимальной степени, плоские графики и диаграммы , которые не содержат подразделение из K р . [2] Это также известно для разбитых графов, графов, в которых никакие две соседние вершины не имеют степени больше двух. [3]
Для произвольных графов число Рамсея, как известно, ограничено функцией, которая лишь немного растет сверхлинейно. В частности, Фокс и Судаков (2009) показали , что существует константа с р такое , что для любого р -degenerate п -vertex графа G ,
Заметки
Рекомендации
- Алон, Нога (1994), "подразделенные графики имеют линейные чисел Рамсея", Журнал теории графов , 18 (4): 343-347, DOI : 10.1002 / jgt.3190180406 , МР 1277513.
- Берр, Стефан А .; Эрдеш, Пол (1975), "О величине обобщенных чисел Рамсея для графов", Бесконечные и конечные множества (Коллоквиум, Кестхей, 1973; посвященный П. Эрдешу в день его 60-летия), Vol. 1 (PDF) , коллок. Математика. Soc. Янош Бойяи, 10 , Амстердам: Северная Голландия, стр. 214–240, MR 0371701.
- Чен, Гуантао; Schelp, Ричард Х. (1993), "Графы с линейно ограниченных чисел Рамсея", Журнал комбинаторной теории, Series B , 57 (1): 138-149, DOI : 10,1006 / jctb.1993.1012 , МР 1198403.
- Хватал, Вацлав ; Рёдль, Войтех; Семереди, Эндре ; Trotter, Уильям Т., младший (1983), "О Рэмси число графа с ограниченной максимальной степени", Журнал комбинаторной теории, Series B , 34 (3): 239-243, DOI : 10.1016 / 0095-8956 ( 83) 90037-0 , Руководство по эксплуатации 0714447.
- Итон, Нэнси (1998), «Числа Рамсея для разреженных графов», Дискретная математика , 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.
- Грэм, Рональд ; Рёдль, Войтех; Rucínski, Анджей (2000), "О графах с линейной чисел Рамсея", Журнал теории графов , 35 (3): 176-192, DOI : 10,1002 / 1097-0118 (200011) 35: 3 <176 :: AID-JGT3 > 3.0.CO; 2-C , Руководство по ремонту 1788033.
- Грэм, Рональд ; Рёдль, Войтех; Rucínski, Анджей (2001), "О двудольных графов с числами линейной Рамсея", Эрдёш и его математики (Будапешт, 1999), Combinatorica , 21 (2): 199-209, DOI : 10.1007 / s004930100018 , MR 1832445
- Калаи, Гил (22 мая 2015 г.), «Чунгбам Ли доказал гипотезу Берра-Эрдеша» , « Комбинаторика» и др. , Получено 22 мая 2015 г.
- Ли, Чунгбум (2017), «Числа Рамсея вырожденных графов», Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi : 10.4007 / annals.2017.185.3.2
- Ли, Юшэн; Руссо, Сесил К .; Шолтеса, Любомир (1997), "Ramsey линейные семьи и обобщенные подразделить графы", Дискретная математика , 170 (1-3): 269-275, DOI : 10.1016 / S0012-365X (96) 00311-1 , MR 1452956.
- Рёдль, Войтех; Томас, Робин (1991), «Организуемость и клики», у Грэма, Рональда ; Нешетржил, Ярослав (ред.), Математика Пола Эрдёша, II (PDF) , Springer-Verlag, стр. 236–239, MR 1425217.