Théorème de Kruskal

Carte Commune · n° 203332

En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre. Ce théorème est un cas particulier du théorème de Robertson-Seymour, dont il a constitué une des motivations. En utilisant ce théorème, Harvey Friedman a pu définir des entiers « incompréhensiblement grands », qu'il a utilisé pour obtenir des résultats nouveaux d'indécidabilité.

Lire sur Wikipédia