Wikipédia

Théorème de Dilworth

Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth[1], caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.

Énoncé modifier

Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables. Le théorème de Dilworth établit, pour un ordre fini, l'existence d'une antichaîne A et d'une partition de l'ensemble ordonné en une famille P de chaînes, telles que A et P aient même cardinal. Pour de tels A et P, A est nécessairement une antichaîne de cardinal maximum (puisque toute antichaîne a au plus un élément dans chaque membre de P) et P est nécessairement une partition en chaînes de cardinal minimum (puisque toute partition en chaînes a au moins une chaîne par élément de A). La largeur de l'ordre partiel (i.e. la taille maximum d'une antichaîne) peut donc être redéfinie comme le cardinal commun de A et P, ou comme la taille minimum d'une partition en chaînes.

Une généralisation de ce théorème établit qu'un ordre (non nécessairement fini) est de largeur finie w si et seulement s'il peut être partitionné en w chaînes, mais pas moins.

Preuve par récurrence modifier

La preuve suivante, par récurrence sur la taille de l'ensemble partiellement ordonné S, s'inspire de celle de Galvin[2].

Le résultat est immédiat si S est vide. Supposons donc S non vide, notons a l'un de ses éléments maximaux, et appliquons l'hypothèse de récurrence à l'ensemble ordonné T = S \ {a}. Il existe, pour un certain entier k, une partition de T en k chaînes C1, … , Ck, et une antichaîne A0 de T de cardinal k. Pour chaque i de 1 à k, il existe dans Ci des éléments appartenant à au moins une antichaîne de T de taille k (par exemple : les éléments communs à Ci et A0) ; soient xi le plus grand d'entre eux et Ai une telle antichaîne associée. Alors, l'ensemble A = {x1, … , xk} est une antichaîne. En effet, pour tous indices i et j distincts, il existe au moins un y commun à Ai et Cj, et un tel élément vérifie y ≤ xj (par définition de xj), donc xi ≱ xj (puisque xi ≱ y).

Revenons à S et distinguons deux cas.

  • Si a majore l'un des xi, soit K la chaîne {a} ∪ {z ∈ Ci | z ≤ xi}. Alors, par choix de xi, S \ K n'a pas d'antichaîne de taille k. L'hypothèse de récurrence implique alors que S \ K peut être partitionné en k – 1 chaînes, puisque A \ {xi} est une antichaîne de taille k – 1 de S \ K. Ceci partitionne S en k chaînes, comme souhaité.
  • Sinon, A ∪ {a} est une antichaîne de taille k + 1 de S (puisque a est maximal dans S), or S est partitionné en k + 1 chaînes, {a}, C1, … , Ck, ce qui termine la preuve.

Équivalence avec le théorème de Kőnig modifier

 
Le théorème de Dilworth se déduit de celui de Kőnig : à partir d'un ordre partiel, on construit un graphe biparti, et un couplage fournit une partition en chaînes.

Comme beaucoup d'autres résultats de combinatoire, parmi lesquels le lemme des mariages de Hall[3], le théorème de Dilworth est équivalent au théorème de Kőnig sur les couplages d'un graphe biparti.

Pour déduire du théorème de Kőnig le théorème de Dilworth, pour un ensemble partiellement ordonné S à n éléments, on définit un graphe biparti G = (U, V, E) par : U = V = S et un élément u de U est joint à un élément v de V par une arête de G lorsque u < v dans S. D'après le théorème de Kőnig, il existe dans G un couplage M et un transversal C de même cardinal m. Soit A l'ensemble des éléments de S qui ne correspondent à aucun sommet de C ; alors A a au moins n – m éléments (éventuellement plus, si C contient des sommets dans U et V correspondant au même élément de S). Par définition d'un transversal, chaque arête a une extrémité dans C, et donc A est une antichaîne. Soit P la famille des chaînes formées en plaçant x et y dans la même chaîne chaque fois qu'ils sont joints par une arête de M ; alors P a n – m chaînes. On a donc construit une antichaîne et une partition en chaînes de même cardinal.

Réciproquement, pour déduire du théorème de Dilworth le théorème de Kőnig, pour un graphe biparti G = (U, V, E), on ordonne les sommets de G en posant : u < v si et seulement si u est dans U, v dans V, et une arête de E les relie. D'après le théorème de Dilworth, il existe une antichaîne A et une partition en chaînes P de même taille. Mais les seules chaînes non triviales sont ici les paires d'éléments correspondant aux arêtes du graphe, donc les chaînes non triviales de P forment un couplage. Le complémentaire de A forme un transversal de même cardinal que ce couplage.

Ce lien avec les couplages de graphes bipartis permet de calculer la largeur de tout ordre partiel fini en temps polynomial.

Généralisation aux ordres partiels infinis modifier

Sur un ensemble infini T, un ordre est encore de largeur inférieure ou égale à un entier w (si et) seulement si T est réunion de w chaînes disjointes.

En effet un ensemble ordonné S est réunion de w chaînes disjointes si et seulement s'il existe une coloration par w couleurs du graphe d'incomparabilité de S (le graphe non orienté dont les sommets sont les éléments de S et les arêtes relient les paires d'éléments incomparables). Par conséquent, si la largeur de l'ordre sur T est inférieure ou égale à w alors, pour toute partie finie S de T (de largeur a fortiori majorée par w), il existe, d'après la version finie du théorème de Dilworth, une coloration par w couleurs du graphe d'incompatibilité de S. D'après le théorème de De Bruijn-Erdős, le graphe d'incomparabilité de T est alors, lui aussi, « w-colorable », donc T est réunion de w chaînes disjointes[4].

Cependant, le théorème ne s'étend pas aux ordres de largeur infinie : pour tout cardinal infini κ, il existe un ordre dont toute antichaîne est finie mais dont toutes les partitions en chaînes sont de taille au moins κ[4].

Micha Perles[5] étudie des analogues du théorème de Dilworth dans le cas infini.

Théorème dual de Mirsky modifier

Le théorème de Mirsky (en), dual de celui de Dilworth, établit que dans un ordre partiel, la taille maximum des chaînes, si elle est finie, est égale à la plus petite taille d'une partition en antichaînes[6]. La preuve en est bien plus simple : pour tout élément x, soit N(x) la taille maximum des chaînes dont x est le plus grand élément, alors les N–1({i}) forment une partition en n antichaînes, si n est la taille maximum des chaînes.

Perfection des graphes de comparabilité modifier

Le graphe de comparabilité d'un ensemble ordonné est le graphe non orienté dont les sommets sont les éléments de l'ensemble et les arêtes relient les paires d'éléments comparables. Une clique dans ce graphe correspond donc à une chaîne, et un stable à une antichaîne. Tout sous-graphe induit d'un graphe de comparabilité est lui-même un graphe de comparabilité : celui de l'ordre restreint à ses sommets.

Un graphe non orienté est parfait si, dans tout sous-graphe induit, le nombre chromatique est égal à la taille de la plus grande clique. Tout graphe de comparabilité est parfait : c'est essentiellement le théorème de Mirsky, reformulé en termes de théorie des graphes[7]. D'après le théorème des graphes parfaits de Lovász, le complémentaire de tout graphe parfait est aussi parfait. Par conséquent, le complémentaire de tout graphe de comparabilité est parfait ; c'est une reformulation du théorème de Dilworth en termes de théorie des graphes[7], ce qui en fournit une autre preuve.

Largeur d'ordres particuliers modifier

  • Le treillis booléen Bn est l'ensemble des parties d'un ensemble X à n éléments – essentiellement {1, 2, … , n} – ordonné par inclusion. Le théorème de Sperner assure que la taille maximum des antichaînes de Bn est celle obtenue en choisissant, comme parties non comparables de X, celles de taille médiane :
     
    L'inégalité de Lubell-Yamamoto-Meshalkin concerne aussi les antichaînes d'un ensemble de parties et peut être utilisée pour démontrer ce théorème.
  • Si l'on ordonne les entiers de l'intervalle [1, 2n] par divisibilité, le sous-intervalle [n + 1, 2n] forme une antichaîne de cardinal n. Il est d'autre part facile de partitionner cet ordre en n chaînes en prenant, pour chaque entier impair m de [1, 2n], la chaîne des nombres de la forme m2i. D'après le théorème de Dilworth, cet ordre est donc de largeur n.
  • Le théorème d'Erdős-Szekeres sur les sous-suites monotones peut être interprété comme une application du théorème de Dilworth à des ordres partiels de dimension d'ordre (en) égale à 2[8].
  • La « dimension convexe » d'un antimatroïde (en) est le plus petit nombre de chaînes nécessaires pour définir cet antimatroïde, et le théorème de Dilworth peut servir à démontrer que ce nombre est égal à la largeur d'un ordre partiel associé, ce qui conduit à un algorithme en temps polynomial pour le calcul de la dimension convexe[9].

Notes et références modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dilworth's theorem » (voir la liste des auteurs).
  1. ↑ (en) Robert P. Dilworth, « A Decomposition Theorem for Partially Ordered Sets », Ann. Math., vol. 51, no 1,‎ , p. 161-166 (DOI 10.2307/1969503).
  2. ↑ (en) Fred Galvin, « A proof of Dilworth's chain decomposition theorem », Amer. Math. Month., vol. 101, no 4,‎ , p. 352-353.
  3. ↑ (en) D. R. Fulkerson, « Note on Dilworth’s decomposition theorem for partially ordered sets », Proc. Amer. Math. Soc., vol. 7, no 4,‎ , p. 701-702 (lire en ligne).
  4. ↑ a et b (en) Egbert Harzheim, Ordered sets, Springer, coll. « Advances in Mathematics » (no 7), , 386 p. (ISBN 978-0-387-24219-4, lire en ligne), p. 60, Theorem 5.6.
  5. ↑ (en) Micha A. Perles, « On Dilworth's theorem in the infinite case », Isr. J. Math., vol. 1, no 2,‎ , p. 108-109 (DOI 10.1007/BF02759806).
  6. ↑ (en) Leon Mirsky (en), « A dual of Dilworth's decomposition theorem », Amer. Math. Month., vol. 78, no 8,‎ , p. 876-877 (DOI 10.2307/2316481).
  7. ↑ a et b (en) Claude Berge et Václav Chvátal, Topics on Perfect Graphs, Amsterdam/New York, Elsevier, coll. « Annals of Discrete Mathematics » (no 21), (ISBN 978-0-444-86587-8, lire en ligne), viii.
  8. ↑ (en) J. Michael Steele, « Variations on the monotone subsequence theme of Erdős and Szekeres », dans David Aldous, Persi Diaconis, Joel Spencer et J. Michael Steele, Discrete Probability and Algorithms, Springer, coll. « IMA Volumes in Mathematics and its Applications » (no 72), (lire en ligne), p. 111-131.
  9. ↑ (en) Paul H. Edelman et Michael E. Saks, « Combinatorial representation and convex dimension of convex geometries », Order, vol. 5, no 1,‎ , p. 23-32 (DOI 10.1007/BF00143895).

Voir aussi modifier

Article connexe modifier

Liens externes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Théorème_de_Dilworth&oldid=197957927 ».