{"id":4655,"date":"2024-12-08T10:59:24","date_gmt":"2024-12-08T09:59:24","guid":{"rendered":"https:\/\/eva.louis-le-grand.net\/maths\/?p=4655"},"modified":"2024-12-08T11:00:06","modified_gmt":"2024-12-08T10:00:06","slug":"nombre-de-ramsey","status":"publish","type":"post","link":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/2024\/12\/08\/nombre-de-ramsey\/","title":{"rendered":"Nombre de Ramsey"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"CO8 Small Ramsey Numbers: r(3, 4)=9, r(3, 5)= 14, r(4,4) =18\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/SRCWgViSgWs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Timothy Gowers at GYSS 2021 - Ramsey Theory\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/uxRvfEOC3uQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Rappel : qu\u2019est-ce qu\u2019une clique dans un graphe ?<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Un <strong>graphe<\/strong> est constitu\u00e9 de <strong>sommets<\/strong> reli\u00e9s par des <strong>ar\u00eates<\/strong>.<br>Une <strong>clique<\/strong> dans un graphe est un sous-ensemble de sommets o\u00f9 chaque sommet est reli\u00e9 \u00e0 tous les autres sommets du sous-ensemble. Autrement dit, tous les sommets de la clique sont connect\u00e9s entre eux.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Exemple : dans un graphe, si les sommets A,B,CA, B, CA,B,C sont connect\u00e9s entre eux par des ar\u00eates, alors {A,B,C}\\{A, B, C\\}{A,B,C} forme une clique.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Coloration des ar\u00eates<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Imaginons un graphe complet KnK_nKn\u200b avec nnn sommets. Cela signifie qu&rsquo;il y a une ar\u00eate entre chaque paire de sommets.<br>On colore chaque ar\u00eate du graphe avec <strong>2 couleurs<\/strong> (par exemple, rouge et bleu). L\u2019objectif est d\u2019\u00e9tudier les sous-graphes color\u00e9s ainsi.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Nombres de Ramsey : que cherche-t-on ?<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Un <strong>nombre de Ramsey<\/strong> R(k,l)R(k, l)R(k,l) est le plus petit nombre de sommets nnn n\u00e9cessaire pour garantir qu\u2019apr\u00e8s avoir color\u00e9 les ar\u00eates d\u2019un graphe complet KnK_nKn\u200b avec deux couleurs :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>soit<\/strong> il existe une <strong>clique rouge<\/strong> de taille kkk,<\/li>\n\n\n\n<li><strong>soit<\/strong> il existe une <strong>clique bleue<\/strong> de taille lll.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">En d\u2019autres termes, R(k,l)R(k, l)R(k,l) est le seuil o\u00f9 l\u2019on ne peut <strong>pas \u00e9viter<\/strong> de cr\u00e9er une grande clique monochrome, peu importe comment on choisit de colorer les ar\u00eates.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Exemple concret : R(3, 3)<\/strong><\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Prenons R(3,3)R(3, 3)R(3,3). Cela signifie que nous cherchons le plus petit nnn tel que, dans un graphe complet KnK_nKn\u200b, chaque coloration en rouge et bleu contient forc\u00e9ment :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>une clique rouge de taille 3<\/strong>, ou<\/li>\n\n\n\n<li><strong>une clique bleue de taille 3<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Pour n=5n = 5n=5, il est possible de colorer les ar\u00eates de K5K_5K5\u200b de fa\u00e7on \u00e0 \u00e9viter une clique monochrome de taille 3. Mais pour n=6n = 6n=6, c\u2019est impossible ! Ainsi, R(3,3)=6R(3, 3) = 6R(3,3)=6.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"1010\" src=\"https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-1024x1010.jpg\" alt=\"\" class=\"wp-image-4658\" srcset=\"https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-1024x1010.jpg 1024w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-300x296.jpg 300w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-768x758.jpg 768w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-1536x1516.jpg 1536w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5307-ramsey-plateau-2048x2021.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"472\" src=\"https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-1024x472.jpg\" alt=\"\" class=\"wp-image-4659\" srcset=\"https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-1024x472.jpg 1024w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-300x138.jpg 300w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-768x354.jpg 768w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-1536x708.jpg 1536w, https:\/\/eva.louis-le-grand.net\/maths\/wp-content\/uploads\/2024\/11\/IMG_5302-ramsey-2048x944.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Encadrement des nombres de Ramsey<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Les nombres de Ramsey sont <strong>difficiles \u00e0 calculer<\/strong>. On conna\u00eet quelques valeurs pr\u00e9cises, mais souvent on ne dispose que d&rsquo;encadrements.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>R(3,3)=6R(3, 3) = 6R(3,3)=6 est une des rares valeurs connues pr\u00e9cis\u00e9ment.<\/li>\n\n\n\n<li>R(4,4)R(4, 4)R(4,4) est compris entre 18 et 25 (valeur exacte inconnue).<\/li>\n\n\n\n<li>R(5,5)R(5, 5)R(5,5) est compris entre 43 et 49.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">\u00c0 quoi \u00e7a sert ?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Les nombres de Ramsey sont importants en math\u00e9matiques, en informatique et en th\u00e9orie des graphes car ils permettent d&rsquo;\u00e9tudier :<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>La structure in\u00e9vitable :<\/strong> ils montrent qu\u2019au-del\u00e0 d\u2019un certain seuil, des configurations \u00ab\u00a0ordonn\u00e9es\u00a0\u00bb (comme des cliques monochromes) sont garanties.<\/li>\n\n\n\n<li><strong>Applications pratiques :<\/strong> ils interviennent en r\u00e9seaux (t\u00e9l\u00e9communications, planification), en th\u00e9orie des jeux et en bioinformatique.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Exemple pour exp\u00e9rimenter<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Prenons un graphe K6K_6K6\u200b avec 6 sommets nomm\u00e9s A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F. Colorons les ar\u00eates au hasard en rouge et bleu. Montrez qu&rsquo;il y aura toujours une clique monochrome de 3 sommets.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Essayez de choisir une coloration. Puis, examinez les sous-ensembles de 3 sommets et v\u00e9rifiez ! C&rsquo;est un bon exercice pour visualiser ce concept.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Timothy Gowers (M\u00e9daille Fields 1998)<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Timothy Gowers a re\u00e7u la M\u00e9daille Fields en 1998 pour ses travaux en <strong>analyse fonctionnelle<\/strong> et en <strong>combinatoire additive<\/strong>. Une partie de ses recherches est li\u00e9e aux id\u00e9es de la <strong>th\u00e9orie de Ramsey<\/strong>, en particulier dans le cadre de la combinatoire et des structures dans des ensembles infinis.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Endre Szemer\u00e9di (Prix Abel 2012, pas M\u00e9daille Fields)<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Endre Szemer\u00e9di, bien que n&rsquo;ayant pas re\u00e7u la M\u00e9daille Fields, a \u00e9t\u00e9 r\u00e9compens\u00e9 par le <strong>Prix Abel<\/strong> en 2012 pour ses contributions fondamentales \u00e0 la combinatoire et \u00e0 la th\u00e9orie des graphes.<br>Le <strong>th\u00e9or\u00e8me de Szemer\u00e9di<\/strong>, qui dit que tout ensemble suffisamment grand de nombres entiers contient des progressions arithm\u00e9tiques de longueur arbitraire, peut \u00eatre vu comme une extension des id\u00e9es de la th\u00e9orie de Ramsey dans un contexte arithm\u00e9tique.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Paul Erd\u0151s <\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Paul Erd\u0151s n\u2019ait pas re\u00e7u la M\u00e9daille Fields, il a \u00e9t\u00e9 un pionnier des <strong>nombres de Ramsey<\/strong> et de la combinatoire. Il a contribu\u00e9 \u00e0 poser les bases de la recherche moderne dans ce domaine, notamment avec ses conjectures sur les bornes asymptotiques des nombres de Ramsey.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Analyse des r\u00e9seaux biologiques<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Les r\u00e9seaux biologiques, comme les <strong>r\u00e9seaux de prot\u00e9ines<\/strong> (PPI : Protein-Protein Interaction Networks) ou les <strong>r\u00e9seaux de g\u00e8nes<\/strong> (Gene Regulatory Networks), sont souvent mod\u00e9lis\u00e9s sous forme de graphes o\u00f9 :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Les <strong>n\u0153uds<\/strong> repr\u00e9sentent des mol\u00e9cules (prot\u00e9ines, g\u00e8nes, m\u00e9tabolites, etc.).<\/li>\n\n\n\n<li>Les <strong>ar\u00eates<\/strong> repr\u00e9sentent des interactions biologiques.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Application des concepts de Ramsey :<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>On peut \u00e9tudier si un r\u00e9seau contient des <strong>motifs structuraux in\u00e9vitables<\/strong> comme des sous-graphes sp\u00e9cifiques (cliques ou structures monochromes) qui pourraient correspondre \u00e0 des <strong>modules fonctionnels<\/strong> ou des complexes de prot\u00e9ines.<\/li>\n\n\n\n<li>Par exemple, dans un r\u00e9seau d\u2019interactions prot\u00e9iques, une clique de taille kkk peut repr\u00e9senter un <strong>complexe prot\u00e9ique<\/strong> o\u00f9 chaque prot\u00e9ine interagit directement avec toutes les autres.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Coloration des interactions<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Dans certains contextes, on peut \u00ab\u00a0colorer\u00a0\u00bb les interactions biologiques pour repr\u00e9senter des propri\u00e9t\u00e9s diff\u00e9rentes, par exemple :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Une interaction rouge pourrait indiquer une interaction <strong>activatrice<\/strong> (stimulation entre deux g\u00e8nes\/prot\u00e9ines).<\/li>\n\n\n\n<li>Une interaction bleue pourrait repr\u00e9senter une interaction <strong>inhibitrice<\/strong>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Probl\u00e8me de Ramsey en bioinformatique :<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Si on examine un graphe color\u00e9 de ce type, les concepts de Ramsey permettent de r\u00e9pondre \u00e0 des questions comme :\n<ul class=\"wp-block-list\">\n<li><strong>Existe-t-il une sous-r\u00e9gion monochrome ?<\/strong> Cela peut correspondre \u00e0 un module activ\u00e9 ou inhib\u00e9 dans son ensemble.<\/li>\n\n\n\n<li><strong>Quelle est la taille minimale d\u2019un r\u00e9seau dans lequel ces propri\u00e9t\u00e9s sont in\u00e9vitables ?<\/strong> Cela peut guider les chercheurs \u00e0 d\u00e9tecter des motifs critiques dans des r\u00e9seaux complexes.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Analyse des co-expressions g\u00e9niques<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Les <strong>profils d\u2019expression g\u00e9nique<\/strong> mesur\u00e9s dans des exp\u00e9riences comme la RNA-seq produisent de vastes ensembles de donn\u00e9es o\u00f9 les g\u00e8nes co-exprim\u00e9s peuvent \u00eatre mod\u00e9lis\u00e9s comme des graphes.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Les <strong>cliques<\/strong> monochromes dans ces graphes indiquent souvent des <strong>modules de co-expression<\/strong>, c&rsquo;est-\u00e0-dire des ensembles de g\u00e8nes qui sont activ\u00e9s ou r\u00e9prim\u00e9s ensemble sous certaines conditions biologiques.<\/li>\n\n\n\n<li>Les concepts de Ramsey aident \u00e0 formaliser ces analyses en garantissant qu\u2019un certain type de r\u00e9gularit\u00e9 (comme une clique monochrome) est in\u00e9vitable dans des ensembles suffisamment grands.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Mod\u00e9lisation de l\u2019\u00e9volution<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">En biologie \u00e9volutive, les concepts de Ramsey peuvent \u00eatre appliqu\u00e9s pour mod\u00e9liser des ph\u00e9nom\u00e8nes li\u00e9s \u00e0 l&rsquo;\u00e9volution :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Convergence \u00e9volutive :<\/strong> Des motifs similaires apparaissent in\u00e9vitablement dans diff\u00e9rentes branches de l\u2019arbre \u00e9volutif (analogie aux structures monochromes dans un graphe color\u00e9).<\/li>\n\n\n\n<li><strong>R\u00e9sistance aux mutations :<\/strong> On peut utiliser des graphes color\u00e9s pour mod\u00e9liser les relations entre diff\u00e9rents g\u00e9notypes et ph\u00e9notypes. Une clique monochrome pourrait indiquer un ensemble de g\u00e9notypes robustes qui produisent des ph\u00e9notypes similaires.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Pour aller plus loin, conf\u00e9rence de Timothy au coll\u00e8ge de France et \u00e0 l&rsquo;IHP<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Rappel : qu\u2019est-ce qu\u2019une clique dans un graphe ? Un graphe est constitu\u00e9 de sommets reli\u00e9s par des ar\u00eates.Une clique dans un graphe est un sous-ensemble de sommets o\u00f9 chaque sommet est reli\u00e9 \u00e0 tous les autres sommets du sous-ensemble. Autrement dit, tous les sommets de la clique sont connect\u00e9s entre eux. Coloration des ar\u00eates [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4655","post","type-post","status-publish","format-standard","hentry","category-non-classe"],"_links":{"self":[{"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/posts\/4655","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/comments?post=4655"}],"version-history":[{"count":4,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/posts\/4655\/revisions"}],"predecessor-version":[{"id":4752,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/posts\/4655\/revisions\/4752"}],"wp:attachment":[{"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/media?parent=4655"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/categories?post=4655"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eva.louis-le-grand.net\/maths\/index.php\/wp-json\/wp\/v2\/tags?post=4655"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}