Теорема Эрдеша – Посы

В математической дисциплине теории графов теорема Эрдеша -Посы , названная в честь Пола Эрдеша и Лайоша Посы , связывает два параметра графа:

Размер наибольшего набора вершинно-непересекающихся циклов, содержащихся в графе;
Размер наименьшего набора вершин обратной связи в графе: набор, содержащий одну вершину из каждого цикла.

Мотивация и заявление

Во многих приложениях нас интересует поиск минимального набора вершин обратной связи в графе: небольшого набора, включающего по одной вершине из каждого цикла, или, что то же самое, небольшого набора вершин, удаление которых уничтожает все циклы. Это сложная вычислительная задача; если мы не можем решить ее точно, мы можем вместо этого попытаться найти нижнюю и верхнюю границы размера минимального набора вершин обратной связи.

Один из подходов к нахождению нижних границ — найти в графе набор вершинно-непересекающихся циклов. Например, рассмотрим граф на рисунке 1. Циклы ABCFA и GHIJG не имеют общих вершин. В результате, если мы хотим удалить вершины и уничтожить все циклы в графе, мы должны удалить как минимум две вершины: одну из первого цикла и одну из второго. Эта линия рассуждений обобщает: если мы можем найти $k$ непересекающихся по вершинам циклов в графе, то каждый набор вершин обратной связи в графе должен иметь как минимум $k$ вершин.

К сожалению, в общем случае эта оценка не является точной: если самый большой набор вершинно-непересекающихся циклов в графе содержит $k$ циклов, то из этого не обязательно следует, что существует множество вершин обратной связи размера $k$ . Граф на рисунке 1 является примером этого: даже если мы уничтожим цикл GHIJG, удалив одну из вершин G, H, I или J, мы не сможем уничтожить все четыре цикла ABCFA, ABEFA, BCDEB и CDEFC, удалив еще одна вершина. Любой набор вершин минимальной обратной связи в графе на рисунке 1 имеет три вершины: например, три вершины A, C и G.

Можно построить примеры, в которых разрыв между двумя величинами - размером наибольшего набора вершинно-непересекающихся циклов и размером наименьшего набора вершин обратной связи - сколь угодно велик. Теорема Эрдеша-Посы гласит, что, несмотря на это, знание одной величины устанавливает нижние и верхние границы другой величины. Формально теорема утверждает, что существует функция $f:\mathbb {N} \rightarrow \mathbb {N}$ такой, что для каждого положительного целого числа $k$ каждый граф либо

содержит набор из $k$ вершинно-непересекающихся циклов, или
имеет набор вершин обратной связи, состоящий не более чем из $f (k)$ вершин.

Например, предположим, что мы определили, что для графа на рисунке 1 существует набор из 2 непересекающихся вершин циклов, но нет набора из 3 непересекающихся вершин циклов. Наш предыдущий аргумент гласит, что наименьший набор вершин обратной связи должен иметь как минимум 2 вершины; Теорема Эрдеша – Посы гласит, что наименьшее множество вершин обратной связи должно иметь не более $f (3)$ вершин.

В принципе, многие функции $f$ могут удовлетворять теореме. С целью обсуждения границ того, насколько большим $f (k)$ должно быть , мы определяем функцию Эрдеша-Посы , чтобы дать для каждого положительного целого числа $k$ наименьшее значение $f (k),$ для которого справедливо утверждение теоремы.

Границы функции Эрдеша–Посы

Помимо доказательства существования функции $f (k)$ , Эрдёш и Поса (1965) получили оценки $c 1 k log k < f (k) < c 2 k log k$ для некоторых констант $c 1$ и $c 2$ . В обозначениях Big O f $(k) = Θ(k log k)$ .

Предыдущий неопубликованный результат Белы Боллобаса гласил, что $f (2) = 3$ : проще говоря, любой граф, который не содержит двух непересекающихся вершинных циклов, имеет набор вершин обратной связи, состоящий не более чем из трех вершин. Одним из примеров, показывающих, что $f (2) \geq 3,$ является $K 5$ , полный граф на 5 вершинах. Здесь, поскольку любой цикл должен содержать не менее трех вершин, а всего вершин всего 5, любые два цикла должны перекрываться хотя бы в одной вершине. С другой стороны, набор только из двух вершин не может быть набором вершин обратной связи, поскольку остальные три вершины образуют цикл: набор вершин обратной связи должен содержать как минимум три вершины.

Результат о том, что $f (2) = 3,$ был впервые опубликован Ловасом (1965) , который также дал полную характеристику случая $k = 2$ пример $K 5$ : то есть он описал графы, которые, как и приведенный выше , делают не содержать двух вершинно-непересекающихся циклов. Позже Восс (1969) доказал, что $f (3) = 6$ и $9 ⩽ f (4) ⩽ 12$ .

Недвижимость Эрдеш-Поса

Семейство $F$ графов или гиперграфов определяется как обладающее свойством Эрдеша – Посы, если существует функция $f:\mathbb {N} \rightarrow \mathbb {N}$ такой, что для любого (гипер-)графа $G$ и любого целого числа $k$ верно одно из следующих условий:

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

Это определение часто формулируют следующим образом. Если обозначить через $ν (G)$ максимальное число вершинных непересекающихся подграфов $G,$ изоморфных графу в $F$ , а через $τ (G)$ минимальное количество вершин, удаление которых из $G$ оставляет граф без подграфа, изоморфного графу в $F$ , то $τ (G) \leq f (ν (G))$ , для некоторой функции $f:\mathbb {N} \rightarrow \mathbb {N}$ зависит от $Г.$ не

Перефразированная в этой терминологии, теорема Эрдеша-Посы утверждает, что семейство $F$ , состоящее из всех циклов, обладает свойством Эрдеша-Посы с ограничивающей функцией $f (k) = Θ(k log k)$ . Робертсон и Сеймур (1986) значительно обобщили это. Для данного графа $H$ пусть $F$ ( $H$ ) обозначает семейство всех графов, содержащих $H$ в качестве минора . Как следствие своей второстепенной теоремы о сетке , Робертсон и Сеймур доказали, что $F$ ( $H$ ) обладает свойством Эрдеша–Посы тогда и только тогда, когда $H$ — плоский граф . Более того, теперь известно, что соответствующая ограничивающая функция равна $f (k) = Θ(k),$ если $H$ — лес ( Fiorini, Joret & Wood 2013 ), тогда как $f (k) = Θ(k log k)$ для всех остальных плоский граф $H$ ( Камес ван Батенбург и др., 2019 ).

Когда мы принимаем $H$ в качестве треугольника, семейство $F$ ( $H$ ) состоит из всех графов, содержащих хотя бы один цикл, а множество вершин $C$ такое, что $G - C$ не имеет подграфа, изоморфного графу в $F$ ( $H$ ), в точности набор вершин обратной связи. Таким образом, частный случай, когда $H$ — треугольник, эквивалентен теореме Эрдеша–Посы.

Ссылки

Эрдеш, Пол ; Поса, Лайош (1965). «О независимых цепях, содержащихся в графе» . Канадский математический журнал . 17 : 347–352. дои : 10.4153/CJM-1965-035-8 . S2CID 123981328 .
Робертсон, Нил ; Сеймур, Пол (1986). «Минор графа. V. Исключение плоского графа» . Журнал комбинаторной теории, серия B. 41 : 92–114. дои : 10.1016/0095-8956(86)90030-4 .
Восс, Хайнц-Юрген (1969). «Свойства графов, не содержащих k + 1 неузловых циклов». Математические новости . 40 (1–3): 19–25. дои : 10.1002/mana.19690400104 .
Ловас, Ласло (1965). «О графах, не содержащих независимых контуров». Мэтт. Листы . 16 : 289–299.
Камес ван Батенбург, Воутер; Хьюнь, Тони; Жоре, Гвенаэль; Раймонд, Жан-Флоран (2019). «Точная функция Эрдеша-Посы для плоских миноров» . Достижения комбинаторики . 2 : 33 стр. arXiv : 1807.04969 . дои : 10.19086/aic.10807 .
Фиорини, Самуэль; Жоре, Гвенаэль; Вуд, Дэвид Р. (2013). «Исключенные малые леса и собственность Эрдеш-Поса». Комбинаторика, теория вероятностей и вычисления . 22 (5): 700–721. arXiv : 1204.5192 . дои : 10.1017/S0963548313000266 . S2CID 122708 .

См. также