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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Excuse.