Théorème d'Erdős–Pósa[1] — Il existe une fonction f : N → N telle que pour tout graphe G et tout entier positif k, l'un des énoncés suivants soit vrai :
G contient au moins k cycles sommet-disjoints ; ou
G a un ensemble X de sommets, de taille au plus f(k), tel que G − X est une forêt[2].
De plus, f(k) = O(k log k).
Estimation de la fonction f
Ce théorème généralise un résultat non publié de Béla Bollobás selon lequel f(2) = 3. Lovász a donné une description complète des graphes ne contenant pas 2 cycles disjoints[3]. Voss a prouvé[4] que f(3) = 6 et 9 ≤ f(4) ≤ 12.
Pour un k général, Erdős et Pósa ont montré[1] que toute fonction f satisfaisant l'énoncé du théorème ci-dessus est telle que f(k) = Ω(k log k).
Voss a également obtenu[4] la majoration f(k) = (2 + o(1)) k log k et la minoration f(k) ≥ 1/8k log k.
Propriété d'Erdős-Pósa
Par analogie avec le théorème, on dit qu'une famille F de graphes a la propriété d'Erdős–Pósa s'il existe une fonction f: N → N telle que pour tout graphe G et tout entier positif k, l'un des énoncés suivants est vrai :
G contient k sous-graphes sommet-disjoints, chacun isomorphe à un graphe de F ; ou
G a un ensemble X de sommets, de taille au plus f(k), tel que G − X n'a pas de sous-graphe isomorphe à un graphe de F.
La (plus petite) fonction f dans la définition ci-dessus est appelée borne pour la propriété d'Erdős–Pósa de la famille F.
Avec cette terminologie, le théorème d'Erdős–Pósa se reformule comme suit : la famille F de tous les cycles a la propriété d'Erdős et Pósa, avec borne f(k) = Θ(k log k).
Étant donné un graphe H, notons F(H) la classe de tous les graphes qui contiennent H comme mineur. En corollaire du théorème d'exclusion de grille, Robertson et Seymour ont démontré une généralisation considérable du théorème d'Erdős et Pósa :
Théorème[5] — F(H) a la propriété d' Erdős–Pósa si et seulement si H est un graphe planaire.
Il a ensuite été démontré que la borne correspondante est f(k) = Θ(k) si H est une forêt[6] et qu'elle est f(k) = Θ(k log k) pour tout autre graphe H planaire[7]. Le cas particulier où H est un triangle est équivalent au théorème d'Erdős et Pósa.
Relation à d'autres théorèmes
On peut voir le théorème d'Erdős–Pósa comme un cousin du théorème de Kőnig qui, exprimé dans le formalisme décrit ci-dessus, revient à dire que dans les graphes bipartis, F(K2) a la propriété d'Erdős-Pósa avec borne f(k) = k. Il en est de même pour le théorème de Menger, qui lui aussi relie un nombre maximum d'objets disjoints dans un graphe (dans ce cas des chemins) au nombre minimum de sommets à retirer pour détruire tous ces objets (un séparateur).
↑Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret et Jean-Florent Raymond, « A tight Erdős-Pósa function for planar minors », Advances in Combinatorics, vol. 2, , p. 33pp (DOI10.19086/aic.10807)
