Теорема Эрдеша – Посы - Erdős–Pósa theorem

В математической дисциплине теория графов, то Теорема Эрдеша – Посы, названный в честь Пол Эрдёш и Lajos Pósa, заявляет, что существует функция $ж (k)$ так что для каждого положительное число $k$ , каждый граф либо содержит не менее $k$ вершинно-непересекающийся циклы или у него есть набор вершин обратной связи не более $ж (k)$ вершины, пересекающие каждый цикл. Более того, $ж (k) = Θ (k бревно k)$ в смысле Обозначение Big O. В силу этой теоремы говорят, что циклы имеют Erdős – Pósa недвижимость.

Теорема утверждает, что для любого конечного числа $k$ есть подходящее (наименьшее) значение $ж (k)$ , со свойством, что в каждом графе без набора $k$ вершинно-непересекающиеся циклы, все циклы могут быть покрыты не более чем $ж (k)$ вершины. Это обобщило неопубликованный результат Béla Bollobás, в котором говорится, что $ж (2) = 3$ . Эрдеш и Поса (1965) получил оценки $c 1 k бревно k < ж (k) < c 2 k бревно k$ для общего случая. По делу $k = 2$ , Ловас (1965) дал полную характеристику. Восс (1969) доказано $ж (3) = 6$ и $9 \leq ж (4) \leq 12$ .

Erdős – Pósa недвижимость

Семья $F$ графиков или гиперграфы определяется как обладающее свойством Эрдеша – Посы, если существует функция $ж : ℕ \to ℕ$ такое, что для любого (гипер-) графа $грамм$ и каждое целое число $k$ верно одно из следующего:

$грамм$ содержит $k$ вершинно-непересекающиеся подграфы, каждый изоморфный графу в $F$ ; или же
$грамм$ содержит набор вершин $C$ размером не более $ж (k)$ такой, что $грамм - C$ не имеет подграфа, изоморфного графу в $F$ .

Это определение часто формулируется следующим образом. Если обозначить через $ν (грамм)$ максимальное количество вершинных непересекающихся подграфов $грамм$ изоморфен графу в $F$ и по $τ (грамм)$ минимальное количество вершин, удаление которых из $грамм$ оставляет граф без подграфа, изоморфного графу в $F$ , тогда $τ (грамм) \leq ж (ν (грамм))$ , для некоторой функции $ж : ℕ \to ℕ$ не в зависимости от $грамм$ .

Перефразированная в этой терминологии, теорема Эрдеша – Поса утверждает, что семейство $F$ состоящий из всех циклов, обладает свойством Эрдеша – Посы с ограничивающей функцией $ж (k) = Θ (k бревно k)$ . Робертсон и Сеймур (1986) значительно обобщили это. Учитывая график $ЧАС$ , позволять $F$ ( $ЧАС$ ) обозначают семейство всех графов, содержащих $ЧАС$ как незначительный. Как следствие их малая теорема о сетке, Робертсон и Сеймур доказали, что $F$ ( $ЧАС$ ) обладает свойством Эрдеша – Посы тогда и только тогда, когда $ЧАС$ это планарный граф. Более того, теперь известно, что соответствующая ограничивающая функция есть $ж (k) = Θ (k)$ если $ЧАС$ это лес (Фиорини, Джорет и Вуд 2013 ), пока $ж (k) = Θ (k бревно k)$ для любого другого плоского графа $ЧАС$ (Cames van Batenburg et al. 2019 г. ). Частный случай, когда $ЧАС$ является треугольником, что эквивалентно теореме Эрдеша – Посы.

Теорема Эрдеша – Посы - Erdős–Pósa theorem

Erdős – Pósa недвижимость

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

Смотрите также