Теорема Эрдёша — Поза

В теории графов теорема Эрдёша – Поза (Пал Эрдёш и Лайош Поза) утверждает, что существует функция f(k), такая, что для любого натурального числа k любой граф либо содержит k разъединённых по вершинам циклов, либо он имеет разрезающее циклы множество из f(k) вершин, которое пересекает любой цикл. Более того, f(k) = O(k log k) в нотации O Большое. Ввиду этой теоремы, говорят, что циклы имеют свойство Эрдёша – Поза.

Теорема утверждает, что для любого конечного числа k существует некоторое (минимальное) значение f(k), для которого в любом графе, не имеющем k вершинно разъединённых циклов, все циклы могут быть покрыты f(k) вершинами. Это обобщает неопубликованный результат Болобаша, который утверждает, что f(2) = 3. Эрдёш и Поза получили границы c₁k log k < f(k) < c₂k log k в общем случае. Этот результат предполагает, что хотя существует бесконечно много графов без k разъединённых циклов, они распадаются на конечное число просто описываемых классов. Для случая k = 2, Ловаш дал полное описание. Восс доказал, что f(3) = 6 и 9 ≤ f(4) ≤ 12.

Свойство Эрдёша–Поза

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

• G содержит k вершинно разъединённых подграфов, каждый из которых изоморфен графу из F
• G содержит множество вершин C размера, не превосходящего f(k), такое, что G − C не содержит подграфов, изоморфных одному из графов F.

Определение часто формулируется следующим образом. Если обозначить через ν(G) максимальное число вершин непересекающихся подграфов G, изоморфных графам из F и через τ(G) максимальное число вершин, удаление которых из G оставляет граф без графов, изоморфных графам из F, тогда ν(G) ≤ f(τ(G)), для некоторой функции f: N → N, не зависящего от G.

Литература

• Paul Erdős, Lajos Pósa. On independent circuits contained in a graph (англ.) // Canad. Journ. Math. — 1965. — Vol. 17. — doi:10.4153/CJM-1965-035-8.
• Voss Heinz-Jürgen. Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten (англ.) // Mathematische Nachrichten. — 1969. — Vol. 40. — doi:10.1002/mana.19690400104.
• László Lovász. On graphs not containing independent circuits (англ.) // Mat. Lapok. — 1965. — Iss. 16.