Victor Bapst

A partir du formalisme non rigoureux de la « méthode de la cavité », les physiciens ont fait depuis 15 ans des prédictions remarquables sur les transitions de phases dans les problèmes d’optimisation aléatoires. Une de ces prédictions les plus notables est que dans dans problèmes comme k-SAT aléatoire ou le k-coloriage de graphes aléatoires il y aurait, juste avant la transition de satisfiabilité, une seconde transition de phase : la condensation. L’existence de cette transition semble intimement reliée à la difficulté d’obtenir des résultats précis sur le seuil de satisfiabilité ainsi qu'à l’échec d'algorithmes de type «  message passing » . Dans le cas du k-coloriage de graphe, il existe une conjecture précise sur la localisation de la condensation qui est donnée en terme d’un problème de point fixe distributionnel. Dans cet exposé, je présenterai les grandes lignes d’une preuve rigoureuse de cette conjecture pour k grand.