Théorème d'Erdős-Pósa

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/8 k log k.

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 a 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 a 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:

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.

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(K₂) 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).