Mineurs de graphes et de matroïdes

Classes de graphes et de matroïdes closes par mineur

Soit φ une classe de graphe. On dit que φ est une classe de graphes close par mineur si pour tout graphe G ∈ φ , tous les mineurs de G appartiennent à φ . Un mineur exclu pour la classe φ est un graphe E tel que E 6∈ φ et pour tout mineur strict (i.e. un mineur strictement plus petit) H de E, H ∈ φ . De nombreuses et importantes classes de graphes sont closes par mineur, notamment les graphes planaires (et plus généralement les graphes plongeables dans les surface) ainsi que certaines classes de graphes topologiques (arbres, graphes planaires externes, graphes sans entrelacs, sans noeuds, …).

Un bel ordre ≤ sur un ensemble X est un ordre partiel sur X tel que, pour toute suite (xi)i∈N d’éléments de X, il existe i et j tels que i < j et xi ≤ xj . On dira qu’une classe est {bien-quasi-ordonnée} pour la relation ≤ si ≤ est un bel ordre pour cette classe. Une question importante était de savoir si la relation de mineur formait un bel ordre pour la classe des graphes. Kruskal a montré que c’était le cas pour les arbres.

Théorème 2.1 (Kruskal, 1960, [43]) Les arbres finis sont bien-quasi-ordonnés par la relation de mineur

Mais le théorème fondamental dans la théorie des mineurs de graphes est le suivant, qui généralise le théorème précédent à l’ensemble des graphes.

Théorème 2.2 (Robertson & Seymour, 2004, [59]) Les graphes sont bien-quasi-ordonnés pour la relation de mineur

En particulier cela implique l’inexistence d’antichaînes infinies où une antichaîne est dans ce cas un ensemble de graphes A tels que pour tout H et G dans A, si H est un mineur de G alors les graphes H et G sont isomorphes. Autrement dit, il ne peut exister un ensemble infini d’éléments incomparables pour la relation de mineur. On peut  donc reformuler le Théorème 2.2 de la manière suivante.

Théorème 2.3 (Robertson & Seymour, 2004, [59]) Toute classe de graphe close par mineur est caractérisée par un ensemble fini de mineurs exclus.

Néanmoins la preuve de ce théorème n’est pas constructive et ne permet donc pas de donner la liste des mineurs exclus. La liste est connue uniquement pour certaines classes de graphes closes par mineur. On donne un petit aperçu de telles caractérisations.

Théorème 2.4 (Folklore) Un graphe est un arbre si et seulement s’il ne contient pas K3 comme mineur

Théorème 2.5 (Chartrand & Harary, 1967, [16]) Un graphe est planaire externe si et seulement s’il ne contient pas K4 ou K2,3 comme mineur

La liste ne serait pas complète sans la célèbre caractérisation des graphes planaires dûe à Kuratowski et Wagner.

Théorème 2.6 (Wagner, 1937, [80]) Un graphe est planaire si et seulement s’il ne contient pas K5 ou K3,3 comme mineur.

La preuve de ce théorème se base sur le théorème suivant de Kuratowski .

Théorème 2.7 (Kuratowski, 1930, [15]) Un graphe est planaire si et seulement s’il ne contient pas une subdivision K5 ou K3,3 comme sous-graphe.

Notons que cette dernière caractérisation ne fait pas intervenir la relation d’inclusion comme mineur mais comme subdivision. En particulier, toute classe caractérisée par un ensemble fini de mineurs exclus M peut être aussi caractérisée par un ensemble S de sous-graphes exclus à subdivision près. Pour cela on considère toutes les combinaisons possibles de remplacement des sommets du mineur par un arbre ne contenant pas de sommets de degré 2 et dont le nombre de feuilles correspond au degré du sommet du mineur. Comme il n’existe qu’un nombre fini de tels arbres et qu’il n’y a qu’un nombre fini de mineurs, alors cette liste est finie. Il est maintenant facile de prouver que tout graphe contenant un élément deM comme mineur contient aussi une subdivision d’un élément de S comme sous-graphe.

Ce dernier théorème a plusieurs généralisations possibles. L’une consiste à regarder les graphes plongés dans les surfaces de genre g . En effet l’ensemble des graphes plongeables dans une surface de genre g fixé est une famille de graphes close par mineur. Archdeacon et Huneke [5] ont montré que dans le cas des surfaces non orientées, cette famille est caractérisée par un ensemble fini de mineurs exclus. Robertson et Seymour [58] l’ont ensuite montré dans le cas des surfaces orientées. Ce dernier théorème joue un rôle prépondérant dans la preuve de leur théorème de structure des graphes sans mineur H. Néanmoins caractériser explicitement les mineurs exclus pour les graphes plongeables dans les surfaces de genre g reste très difficile du fait de l’explosion du nombre de mineurs exclus. Par exemple, Glover, Huneke et Wang [30] ont montré qu’un graphe était plongeable dans le plan projectif si et seulement s’il ne contenait pas un des 35 mineurs exclus pour cette classe. Dans le cas orienté, le nombre de mineurs exclus est encore plus grand : le nombre de mineurs exclus pour la classe des graphes plongeables dans le tore est supérieur à 16000 et la liste n’est probablement pas exhaustive [29].

Une autre possibilité de généraliser le théorème de Wagner est de généraliser la notion de planarité en dimension supérieure. Une telle généralisation pourrait être de considérer les graphes sans entrelacs. Le théorème suivant montre que dans ce cas-là, le nombre de mineurs exclus reste raisonnable.

Théorème 2.8 (Robertson, Seymour & Thomas, 1930, [15]) Un graphe est sans entrelacs si et seulement s’il ne contient pas de graphe de la famille de Petersen comme mineur (cf. Figure 2.1).

Une telle caractérisation pour les graphes sans noeuds reste ouverte. Ce type de caractérisation par mineurs exclus peut s’étendre aux matroïdes. Un cas intéressant de famille close par mineur correspond à l’ensemble des matroïdes représentables sur un corps F. En effet, l’opération de supression d’un élément correspond alors à la supression d’une colonne et donc préserve la représentabilité du matroïde.