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

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

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

Определения

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

Это следует из Теорема Рамсея что для любого графика грамм существует наименьшее целое число ${ Displaystyle г (G)}$, то Число Рамсея из грамм, так что любой полный график по крайней мере ${ Displaystyle г (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.}$

Примечания

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