Analyse calculatoire des théorèmes d'ensemble fin
1 : Institut Camille Jordan
Centre National de la Recherche Scientifique, Institut Camille Jordan
Les théorèmes d'ensemble fin affirment que pour tout coloriage des n-uplets d'entiers naturels, il existe un ensemble infini d'entier sur lequel les n-uplets évident une couleur. En particulier, les théorèmes d'ensemble fin restreints aux 2-coloriages sont plus connus sous le nom de théorème de Ramsey. Ces théorèmes peuvent être vus comme des problèmes mathématiques, où une instance est un coloriage des n-uplets, et une solution d'une instance est un ensemble infini d'entiers. Nous étudierons l'aspect calculatoire des théorèmes d'ensemble fin, et en particulier leur capacité à calculer des degrés de Turing et des fonctions à croissance rapide. C'est un travail commun avec Peter Cholak.