PROFILPELAJAR.COM

En théorie des graphes, le théorème d'Erdős-Pósa, nommé après Paul Erdős et Lajos Pósa (en), relie dans un graphe la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set).

Énoncé

Théorème d'Erdős–Pósa^[1] — Il existe une fonction $f : N \to 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 \leq f (4) \leq 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) \geq 1 / 8 k 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 \to 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 (K 2)$ 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).

Notes et références

↑ ^{a et b} Paul Erdős et Lajos Pósa, « On independent circuits contained in a graph », Canad. Journ. Math, vol. 17,‎ 1965, p. 347–352 (DOI 10.4153/CJM-1965-035-8)
↑ Un graphe est une forêt s'il est acyclique, autrement dit si c'est un arbre ou une union d'arbres disjoints.
↑ László Lovász, « On graphs not containing independent circuits », Mat. Lapok, vol. 16,‎ 1965, p. 289–299
↑ ^{a et b} Heinz-Jürgen Voss, « Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten », Mathematische Nachrichten, vol. 40,‎ 1969, p. 19–25 (DOI 10.1002/mana.19690400104)
↑ Neil Robertson et Paul Seymour, « Graph minors. V. Excluding a planar graph », Journal of Combinatorial Theory, Series B, vol. 41,‎ 1986, p. 92–114 (DOI 10.1016/0095-8956(86)90030-4)
↑ Samuel Fiorini, Gwenaël Joret et David R. Wood, « Excluded Forest Minors and the Erdős–Pósa Property », Combinatorics, Probability and Computing, vol. 22, n^o 5,‎ 2013, p. 700–721 (DOI 10.1017/S0963548313000266, arXiv 1204.5192, S2CID 122708)
↑ 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,‎ 2019, p. 33pp (DOI 10.19086/aic.10807 )