{"id":179,"date":"2023-10-04T17:27:54","date_gmt":"2023-10-04T15:27:54","guid":{"rendered":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/?page_id=179"},"modified":"2025-01-17T20:30:06","modified_gmt":"2025-01-17T19:30:06","slug":"cours-mpri-2-10-aspects-algorithmiques-de-la-combinatoire","status":"publish","type":"page","link":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/cours-mpri-2-10-aspects-algorithmiques-de-la-combinatoire\/","title":{"rendered":"Cours MPRI 2.10 Aspects algorithmiques de la combinatoire"},"content":{"rendered":"\n<p>Cette page correspond \u00e0 la partie du cours <em><a href=\"https:\/\/wikimpri.dptinfo.ens-cachan.fr\/doku.php?id=cours:c-2-10\" data-type=\"link\" data-id=\"https:\/\/wikimpri.dptinfo.ens-cachan.fr\/doku.php?id=cours:c-2-10\">Aspects algorithmiques de la combinatoire<\/a><\/em> donn\u00e9e par <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/\" data-type=\"page\" data-id=\"8\">J\u00e9r\u00e9mie Bouttier<\/a>, dans le cadre de la deuxi\u00e8me ann\u00e9e du <a href=\"https:\/\/wikimpri.dptinfo.ens-cachan.fr\/\" data-type=\"link\" data-id=\"https:\/\/wikimpri.dptinfo.ens-cachan.fr\/\">Master Parisien de Recherche en Informatique<\/a> (MPRI).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Dimers and related combinatorial models of statistical mechanics (2024-2025)<\/h2>\n\n\n\n<p>This year, the course was taught in English. It was more or less based on Chapter 2 of these <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2025\/01\/MPRI_20251010_notes.pdf\" data-type=\"attachment\" data-id=\"343\">lectures notes<\/a>, which are in French and in an unfinished state, to be supplemented with the more recent lecture-specific material available below :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>8 November : introduction, notions from graph theory, the dimer model and some of its avatars, dimers on rectangular grids and the Temperley bijection. <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2024\/11\/slides_MPRI_20241108.pdf\" data-type=\"attachment\" data-id=\"290\">Slides<\/a><\/li>\n\n\n\n<li>15 November : the LGV lemma and application to the enumeration of lozenge tilings of an hexagon, the pfaffian of a skew-symmetric matrix. <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2024\/11\/slides_MPRI_20241115.pdf\" data-type=\"attachment\" data-id=\"292\">Slides<\/a><\/li>\n\n\n\n<li>22 November : exercise session supervised by Guillaume Chapuy<\/li>\n\n\n\n<li>29 November : <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2024\/12\/MPRI_20241129_partiel.pdf\" data-type=\"attachment\" data-id=\"306\">partial exam<\/a>, <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2024\/12\/MPRI_20241129_partiel_corrige.pdf\" data-type=\"attachment\" data-id=\"305\">correction<\/a> (both written jointly with Guillaume Chapuy)<\/li>\n\n\n\n<li>13 December : Kasteleyn&rsquo;s method for enumerating dimer configurations via pfaffian orientations of graphs. <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2024\/12\/slides_MPRI_20241213.pdf\" data-type=\"attachment\" data-id=\"330\">Slides<\/a><\/li>\n\n\n\n<li>10 January : around the Ising and Potts models. After a short introduction, we worked on some <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2025\/01\/MPRI_20250110_exos.pdf\" data-type=\"attachment\" data-id=\"334\">exercises<\/a> (in French).<\/li>\n\n\n\n<li>17 January : lozenge tilings, plane partitions, and the RSK algorithm. Here are my <a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2025\/01\/MPRI_20250117_notes.pdf\" data-type=\"attachment\" data-id=\"342\">handwritten notes<\/a> (this material is not given in the above lecture notes, but may be found in classical textbooks such as <a href=\"https:\/\/math.mit.edu\/~rstan\/ec\/\" data-type=\"link\" data-id=\"https:\/\/math.mit.edu\/~rstan\/ec\/\">Enumerative Combinatorics, volume 2<\/a> by Stanley).<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Autour de quelques mod\u00e8les bidimensionnels de physique statistique \u00e0 l&rsquo;\u00e9quilibre (2023-2024)<\/h2>\n\n\n\n<p><strong>S\u00e9ances :<\/strong> 4 octobre, 25 octobre, 8 novembre, 11 novembre 2023<br><strong>Attention :<\/strong> pas de s\u00e9ance le 1er novembre ! (Toussaint)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>s\u00e9ance du 4 octobre :\n<ul class=\"wp-block-list\">\n<li>notions de physique statistique : distribution de Boltzmann, exemple du mod\u00e8le d&rsquo;Ising<br>(pour des simulations du mod\u00e8le d&rsquo;Ising 2D, voir par exemple la page 10 des <a href=\"https:\/\/www.unige.ch\/math\/folks\/velenik\/papers\/LN-Ising.pdf\" data-type=\"link\" data-id=\"https:\/\/www.unige.ch\/math\/folks\/velenik\/papers\/LN-Ising.pdf\">notes de cours<\/a> d&rsquo;Yvan Velenik)<\/li>\n\n\n\n<li>les mod\u00e8les de dim\u00e8res et leurs diff\u00e9rents avatars (pavages par dominos\/losanges)<\/li>\n\n\n\n<li>bijection de Temperley entre dim\u00e8res et arbres couvrants sur le r\u00e9seau carr\u00e9<br><a href=\"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-content\/uploads\/sites\/82\/2023\/10\/slides_MPRI_20230410.pdf\" data-type=\"attachment\" data-id=\"190\">Images montr\u00e9es pendant le cours<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>s\u00e9ance du 25 octobre :\n<ul class=\"wp-block-list\">\n<li>bijection de Temperley (suite), formule de Fisher-Kasteleyn-Temperley pour le nombre de pavages par dominos d&rsquo;un rectangle<\/li>\n\n\n\n<li>la formule de MacMahon pour le nombre de pavages par losanges d&rsquo;un hexagone : preuve par le lemme de Lindstr\u00f6m\u2013Gessel\u2013Viennot et calcul de d\u00e9terminant<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>s\u00e9ance du 8 novembre :\n<ul class=\"wp-block-list\">\n<li>m\u00e9thode de Kasteleyn pour l&rsquo;\u00e9num\u00e9ration des configurations de dim\u00e8res sur les graphes plans : le cas biparti (voir aussi le chapitre 2 des <a href=\"https:\/\/www.ceremade.dauphine.fr\/~detiliere\/Cours\/polycop_Dimeres.pdf\" data-type=\"link\" data-id=\"https:\/\/www.ceremade.dauphine.fr\/~detiliere\/Cours\/polycop_Dimeres.pdf\">notes de cours<\/a> de B\u00e9atrice de Tili\u00e8re) et le cas non n\u00e9cessairement biparti (pfaffien, orientations pfaffiennes)<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>s\u00e9ance du 15 novembre :\n<ul class=\"wp-block-list\">\n<li>m\u00e9thode de Kasteleyn : compl\u00e9ments, exemples, application au calcul de la fonction de partition du mod\u00e8le d&rsquo;Ising sur r\u00e9seau carr\u00e9<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>L&rsquo;<strong>examen<\/strong>, portant \u00e9galement sur la partie du cours donn\u00e9e par Guillaume Chapuy, aura lieu le mercredi 29 novembre 2023 de 13h \u00e0 15h30.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Cette page correspond \u00e0 la partie du cours Aspects algorithmiques de la combinatoire donn\u00e9e par J\u00e9r\u00e9mie Bouttier, dans le cadre de la deuxi\u00e8me ann\u00e9e du Master Parisien de Recherche en Informatique (MPRI). Dimers and related combinatorial models of statistical mechanics (2024-2025) This year, the course was taught in English. It was more or less based [&hellip;]<\/p>\n","protected":false},"author":105,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-179","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/pages\/179","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/users\/105"}],"replies":[{"embeddable":true,"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/comments?post=179"}],"version-history":[{"count":33,"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/pages\/179\/revisions"}],"predecessor-version":[{"id":347,"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/pages\/179\/revisions\/347"}],"wp:attachment":[{"href":"https:\/\/perso.imj-prg.fr\/jeremie-bouttier\/wp-json\/wp\/v2\/media?parent=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}