Гипотеза Берра – Эрдеша - Burr–Erdős conjecture - Wikipedia

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

Гипотеза была доказана Чунгбом Ли (таким образом, теперь это теорема).^[1]

Определения

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

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

Гипотеза

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

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

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

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

Прежде чем было доказано полное предположение, оно было сначала рассмотрено в некоторых частных случаях. Это было доказано для графов ограниченной степени Chvátal et al. (1983); их доказательство привело к очень высокой стоимости c_п, и улучшения этой константы были сделаны Итон (1998) и Грэм, Редль и Ручинский (2000). В более общем плане известно, что эта гипотеза верна для п-упорядочиваемые графы, включающие графы с ограниченной максимальной степенью, планарные графы и графы, не содержащие подразделение из K_п.^[2] Это также известно для разбитых графов, графов, в которых никакие две соседние вершины не имеют степени больше двух.^[3]

Для произвольных графов число Рамсея, как известно, ограничено функцией, которая лишь немного растет сверхлинейно. Конкретно, Лиса и Судаков (2009) показал, что существует постоянная c_п такое, что для любого п-вырожденный п-вершинный граф грамм,

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

Примечания

1. Ли (2017); Калаи (2015)
2. Рёдль и Томас (1991).
3. Алон (1994); Ли, Руссо и Солтес (1997).

Рекомендации

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