Résumé - Théorèmes de type Ramsey pour les permutations séparables

Théorèmes de type Ramsey pour les permutations séparables

2025-07-10 10:14:22

{"Quentin Le Houérou","Ludovic Patey"}

{math.LO,"03D32, 03B30 (Primary) 05D10, 03F30 (Secondary)"}

Ce papier de Quentin Le Houérou et Ludovic Patey explore les propriétés computationnelles des théorèmes de type Ramsey, se concentrant sur ceux impliquant des motifs transitifs, en particulier ceux correspondant aux permutations séparables. Les auteurs fournissent une analyse complète de ces théorèmes, établissant des connexions entre leurs caractéristiques computationnelles et l'existence de jeux homogènes infinis dans les modèles standards. Le papier commence par introduire le concept du théorème de Ramsey pour les paires (RT2k), qui stipule que pour toute coloration des arêtes d'un clique infini en utilisant k couleurs, il existe une sous-clique infinie monochromatique. Les auteurs étendent ensuite ce concept aux théorèmes de type Ramsey qui impliquent d'éviter des motifs de coloration finis spécifiques plutôt que des sous-cliques monochromatiques. L'objet principal du papier est les motifs interdits transitifs, qui ne contiennent pas les motifs non-transitifs (1). Ces motifs sont en correspondance un à un avec des permutations, et la classe des permutations séparables joue un rôle crucial dans l'étude des caractéristiques computationnelles de ces assertions de type Ramsey. Les auteurs prouvent que l'évitement de toute permutation séparable est équivalent à l'existence d'un jeu homogène infini dans les modèles standards, tandis que cette propriété échoue pour tout autre motif. Pour établir ce résultat, ils développent une nouvelle argumentation pour la non-computation diagonale relativisée. Le papier examine également le rôle de l'aléa dans le calcul de séquences ascendants ou descendants infinis pour les ordres linéaires calculables et enquête sur la partie première des théorèmes de type Ramsey pour les permutations séparables. Les auteurs concluent en présentant des questions ouvertes liées à la structure des assertions de type Ramsey et à la complexité computationnelle des problèmes associés, mettant en avant la recherche en cours dans ce domaine. En résumé, ce papier apporte une contribution significative à l'étude des théorèmes de type Ramsey, offrant de nouvelles perspectives sur leurs propriétés computationnelles et le rôle des permutations séparables dans ces théorèmes.