Couplages dans les graphes

• Main Author: Viennot, Xavier Gérard
• Other Authors: Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
• Format: Conference Object
• Language: French
• Published: HAL CCSD 2014
• Subjects: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; Arctique*
• Online Access: https://hal.archives-ouvertes.fr/hal-00998357

video: https://mediakiosque.univ-pau.fr/avc/courseaccess?id=2289 transparents: http://vulgarisation.xavierviennot.org/Colleges_et_Lycees_files/Pau14.pdf National audience De combien de façons peut-on couvrir un échiquier avec des dominos ? Voici un problème typique de dénombrement de pavages, qui sont en fait des couplages parfaits dans un graphe. D'une manière générale, un couplage d'un graphe est la donnée d'un ensemble d'arêtes dont les extrémités sont disjointes deux à deux. Lorsque tous les sommets du graphe sont couverts, le couplage est dit parfait. Je montrerai des "formules" remarquables donnant le nombre de couplages parfaits de certains graphes, en particulier le graphe associé à un "échiquier" ayant m lignes et n colonnes. Curieusement, ce genre de formule résoud un modèle introduit en physique pour étudier le ferromagnétisme. Si l'on change le graphe "échiquier" en d'autres réseaux, comme le diagramme dit "Aztèque", des formules très simples et stupéfiantes apparaîssent. Certains dénombrements de couplages partiels permettent de retrouver des formules "scolaires" de trigonométrie sur les sinus et cosinus. C'est la "philosophie" de la combinatoire actuelle: des preuves "visuelles" évitant des calculs compliqués. Enfin, avec le "théorème du cercle arctique", je donnerai un aperçu de recherches récentes en combinatoire sur des couplages aléatoires du diagramme Aztèque, associant combinatoire, algorithmes, probabilités, physique statistique et mathématiques visuelles.