Lemme de Higman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le lemme de Higman est un résultat de la théorie des ordres qui affirme que, pour un ensemble X muni d'un bel ordre, l'ensemble X^* des mots finis sur X muni de l'ordre sous-mot est également un bel ordre. C'est un cas particulier du théorème de Kruskal sur les arbres, qui se généralise à son tour en le théorème de Robertson-Seymour sur les graphes.

Ce lemme est dû à Graham Higman qui l'a publié en 1952[1].

Notes et références[modifier | modifier le code]

  1. (Higman 1952)

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]