Nombres de Ramsey — Les-mathematiques.net The most powerful custom community solution in the world

Nombres de Ramsey

Salut

Je pense qu'on peut poster ce sujet ici et non en arithmétique, sinon...
J'ai un petit problème avec les nombres de Ramsey et les notes que je lis sur Wikipedia. Je cherche à trouver $R(5, 5)$ qui est supposé (c'est démontrer) être entre $43$ et $48$ compris, mais j'ai fait une excursion ailleurs.
D'après le tableau des nombres de Ramsey de Wikipedia $R(6, 5)$ est compris entre $58$ et $87$. Ce qui me fait penser que en général $R(r, s)\neq R(s, r)$.
Mais avec le graphe suivant à $48$ sommets, qui donne que les ''arètes bleues'', que j'ai obtenu, je ne comprends plus vraiment le tableau de Wikipédia, particulièrement la valeur de $R(6, 5)$.

Le graphe :

V := Graph(undirected, {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 9}, {1, 18}, {1, 19}, {1, 20}, {1, 22}, {1, 23}, {1, 24}, {1, 25}, {1, 30}, {1, 31}, {1, 32}, {1, 34}, {1, 35}, {1, 36}, {1, 37}, {1, 42}, {1, 43}, {1, 44}, {1, 46}, {1, 47}, {1, 48}, {2, 3}, {2, 4}, {2, 6}, {2, 10}, {2, 17}, {2, 19}, {2, 20}, {2, 21}, {2, 23}, {2, 24}, {2, 26}, {2, 29}, {2, 31}, {2, 32}, {2, 33}, {2, 35}, {2, 36}, {2, 38}, {2, 41}, {2, 43}, {2, 44}, {2, 45}, {2, 47}, {2, 48}, {3, 4}, {3, 7}, {3, 11}, {3, 17}, {3, 18}, {3, 20}, {3, 21}, {3, 22}, {3, 24}, {3, 27}, {3, 29}, {3, 30}, {3, 32}, {3, 33}, {3, 34}, {3, 36}, {3, 39}, {3, 41}, {3, 42}, {3, 44}, {3, 45}, {3, 46}, {3, 48}, {4, 8}, {4, 12}, {4, 17}, {4, 18}, {4, 19}, {4, 21}, {4, 22}, {4, 23}, {4, 28}, {4, 29}, {4, 30}, {4, 31}, {4, 33}, {4, 34}, {4, 35}, {4, 40}, {4, 41}, {4, 42}, {4, 43}, {4, 45}, {4, 46}, {4, 47}, {5, 6}, {5, 7}, {5, 8}, {5, 9}, {5, 14}, {5, 15}, {5, 16}, {5, 22}, {5, 23}, {5, 24}, {5, 26}, {5, 27}, {5, 28}, {5, 29}, {5, 34}, {5, 35}, {5, 36}, {5, 38}, {5, 39}, {5, 40}, {5, 41}, {5, 46}, {5, 47}, {5, 48}, {6, 7}, {6, 8}, {6, 10}, {6, 13}, {6, 15}, {6, 16}, {6, 21}, {6, 23}, {6, 24}, {6, 25}, {6, 27}, {6, 28}, {6, 30}, {6, 33}, {6, 35}, {6, 36}, {6, 37}, {6, 39}, {6, 40}, {6, 42}, {6, 45}, {6, 47}, {6, 48}, {7, 8}, {7, 11}, {7, 13}, {7, 14}, {7, 16}, {7, 21}, {7, 22}, {7, 24}, {7, 25}, {7, 26}, {7, 28}, {7, 31}, {7, 33}, {7, 34}, {7, 36}, {7, 37}, {7, 38}, {7, 40}, {7, 43}, {7, 45}, {7, 46}, {7, 48}, {8, 12}, {8, 13}, {8, 14}, {8, 15}, {8, 21}, {8, 22}, {8, 23}, {8, 25}, {8, 26}, {8, 27}, {8, 32}, {8, 33}, {8, 34}, {8, 35}, {8, 37}, {8, 38}, {8, 39}, {8, 44}, {8, 45}, {8, 46}, {8, 47}, {9, 10}, {9, 11}, {9, 12}, {9, 14}, {9, 15}, {9, 16}, {9, 18}, {9, 19}, {9, 20}, {9, 26}, {9, 27}, {9, 28}, {9, 30}, {9, 31}, {9, 32}, {9, 33}, {9, 38}, {9, 39}, {9, 40}, {9, 42}, {9, 43}, {9, 44}, {9, 45}, {10, 11}, {10, 12}, {10, 13}, {10, 15}, {10, 16}, {10, 17}, {10, 19}, {10, 20}, {10, 25}, {10, 27}, {10, 28}, {10, 29}, {10, 31}, {10, 32}, {10, 34}, {10, 37}, {10, 39}, {10, 40}, {10, 41}, {10, 43}, {10, 44}, {10, 46}, {11, 12}, {11, 13}, {11, 14}, {11, 16}, {11, 17}, {11, 18}, {11, 20}, {11, 25}, {11, 26}, {11, 28}, {11, 29}, {11, 30}, {11, 32}, {11, 35}, {11, 37}, {11, 38}, {11, 40}, {11, 41}, {11, 42}, {11, 44}, {11, 47}, {12, 13}, {12, 14}, {12, 15}, {12, 17}, {12, 18}, {12, 19}, {12, 25}, {12, 26}, {12, 27}, {12, 29}, {12, 30}, {12, 31}, {12, 36}, {12, 37}, {12, 38}, {12, 39}, {12, 41}, {12, 42}, {12, 43}, {12, 48}, {13, 14}, {13, 15}, {13, 16}, {13, 17}, {13, 21}, {13, 25}, {13, 30}, {13, 31}, {13, 32}, {13, 34}, {13, 35}, {13, 36}, {13, 37}, {13, 42}, {13, 43}, {13, 44}, {13, 46}, {13, 47}, {13, 48}, {14, 15}, {14, 16}, {14, 18}, {14, 22}, {14, 26}, {14, 29}, {14, 31}, {14, 32}, {14, 33}, {14, 35}, {14, 36}, {14, 38}, {14, 41}, {14, 43}, {14, 44}, {14, 45}, {14, 47}, {14, 48}, {15, 16}, {15, 19}, {15, 23}, {15, 27}, {15, 29}, {15, 30}, {15, 32}, {15, 33}, {15, 34}, {15, 36}, {15, 39}, {15, 41}, {15, 42}, {15, 44}, {15, 45}, {15, 46}, {15, 48}, {16, 20}, {16, 24}, {16, 28}, {16, 29}, {16, 30}, {16, 31}, {16, 33}, {16, 34}, {16, 35}, {16, 40}, {16, 41}, {16, 42}, {16, 43}, {16, 45}, {16, 46}, {16, 47}, {17, 18}, {17, 19}, {17, 20}, {17, 21}, {17, 26}, {17, 27}, {17, 28}, {17, 29}, {17, 34}, {17, 35}, {17, 36}, {17, 38}, {17, 39}, {17, 40}, {17, 41}, {17, 46}, {17, 47}, {17, 48}, {18, 19}, {18, 20}, {18, 22}, {18, 25}, {18, 27}, {18, 28}, {18, 30}, {18, 33}, {18, 35}, {18, 36}, {18, 37}, {18, 39}, {18, 40}, {18, 42}, {18, 45}, {18, 47}, {18, 48}, {19, 20}, {19, 23}, {19, 25}, {19, 26}, {19, 28}, {19, 31}, {19, 33}, {19, 34}, {19, 36}, {19, 37}, {19, 38}, {19, 40}, {19, 43}, {19, 45}, {19, 46}, {19, 48}, {20, 24}, {20, 25}, {20, 26}, {20, 27}, {20, 32}, {20, 33}, {20, 34}, {20, 35}, {20, 37}, {20, 38}, {20, 39}, {20, 44}, {20, 45}, {20, 46}, {20, 47}, {21, 22}, {21, 23}, {21, 24}, {21, 26}, {21, 27}, {21, 28}, {21, 30}, {21, 31}, {21, 32}, {21, 33}, {21, 38}, {21, 39}, {21, 40}, {21, 42}, {21, 43}, {21, 44}, {21, 45}, {22, 23}, {22, 24}, {22, 25}, {22, 27}, {22, 28}, {22, 29}, {22, 31}, {22, 32}, {22, 34}, {22, 37}, {22, 39}, {22, 40}, {22, 41}, {22, 43}, {22, 44}, {22, 46}, {23, 24}, {23, 25}, {23, 26}, {23, 28}, {23, 29}, {23, 30}, {23, 32}, {23, 35}, {23, 37}, {23, 38}, {23, 40}, {23, 41}, {23, 42}, {23, 44}, {23, 47}, {24, 25}, {24, 26}, {24, 27}, {24, 29}, {24, 30}, {24, 31}, {24, 36}, {24, 37}, {24, 38}, {24, 39}, {24, 41}, {24, 42}, {24, 43}, {24, 48}, {25, 26}, {25, 27}, {25, 28}, {25, 29}, {25, 33}, {25, 42}, {25, 43}, {25, 44}, {25, 46}, {25, 47}, {25, 48}, {26, 27}, {26, 28}, {26, 30}, {26, 34}, {26, 41}, {26, 43}, {26, 44}, {26, 45}, {26, 47}, {26, 48}, {27, 28}, {27, 31}, {27, 35}, {27, 41}, {27, 42}, {27, 44}, {27, 45}, {27, 46}, {27, 48}, {28, 32}, {28, 36}, {28, 41}, {28, 42}, {28, 43}, {28, 45}, {28, 46}, {28, 47}, {29, 30}, {29, 31}, {29, 32}, {29, 33}, {29, 38}, {29, 39}, {29, 40}, {29, 46}, {29, 47}, {29, 48}, {30, 31}, {30, 32}, {30, 34}, {30, 37}, {30, 39}, {30, 40}, {30, 45}, {30, 47}, {30, 48}, {31, 32}, {31, 35}, {31, 37}, {31, 38}, {31, 40}, {31, 45}, {31, 46}, {31, 48}, {32, 36}, {32, 37}, {32, 38}, {32, 39}, {32, 45}, {32, 46}, {32, 47}, {33, 34}, {33, 35}, {33, 36}, {33, 38}, {33, 39}, {33, 40}, {33, 42}, {33, 43}, {33, 44}, {34, 35}, {34, 36}, {34, 37}, {34, 39}, {34, 40}, {34, 41}, {34, 43}, {34, 44}, {35, 36}, {35, 37}, {35, 38}, {35, 40}, {35, 41}, {35, 42}, {35, 44}, {36, 37}, {36, 38}, {36, 39}, {36, 41}, {36, 42}, {36, 43}, {37, 38}, {37, 39}, {37, 40}, {37, 41}, {37, 45}, {38, 39}, {38, 40}, {38, 42}, {38, 46}, {39, 40}, {39, 43}, {39, 47}, {40, 44}, {40, 48}, {41, 42}, {41, 43}, {41, 44}, {41, 45}, {42, 43}, {42, 44}, {42, 46}, {43, 44}, {43, 47}, {44, 48}, {45, 46}, {45, 47}, {45, 48}, {46, 47}, {46, 48}, {47, 48}}, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48])

Ce graphe ne contient pas de $K_6$ et son complémentaire ne contient pas de $K_5$ !

Quelqu'un peut-il lever mon incompréhension ? Merci.

Réponses

  • Ah, je vois. En fait j'avais écris ma réponse. C'est parce qu'en général $R(s, r)\neq R(r, s)$.....!

    Excuse.
  • J'ai encore besoin de quelques détails, parce que d'après Wikipedia $R(s, r) = R(r, s)$, et donc à mon avis, le théorème n'est pas très clair dans le cas où $r\neq s$.
  • C'est bon, j'ai vu la nuance. Excusez-moi d'avoir trop vite poste
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!