100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Louis Funar

Dieter Mitsche

Sur le saut du nombre chromatique par cliques de G(n,p)
Tuesday, 18 January, 2022 - 14:00 to 15:00
Résumé : 

Le nombre chromatique par cliques d'un graphe est le nombre minimal de couleurs d'un coloriage des sommets du graphe tel qu'aucune clique (sous-graphes complet) maximale ne soit monochromatique. En 2016, avec C. McDiarmid et P. Pralat, nous avons remarqué qu'autour de $p=n^{-1/2}$ le nombre chromatique par cliques du graphe d'Erdos-Renyi $G(n,p)$ diminue de $n^{\Omega(1)}$ en augmentant la valeur de $p$ de $n^{o(1)}$, sans résoudre les détails de ce phénomène surprenant. Dans ce travail récent on résout ce 'saut' autour de $p =n^{-1/2}$. Notre preuve utilise des arguments d'approximation et de concentration, nous permettant

(i) d'obtenir des résultats plus puissants qu'avec une application typique de l'inégalité de Janson et

(ii) de déterminer le nombre chromatique par cliques de $G(n,p)$ pour toute valeur de $p$ à facteurs logarithmiques près.

Travail en collaboration avec Lyuben Lichev et Lutz Warnke.

Institution de l'orateur : 
ICJ (Université de Saint-Étienne)
Thème de recherche : 
Probabilités
Salle : 
projection en salle 4 (en ligne)
logo uga logo cnrs