|
Édition du: 08/04/2024 |
|
INDEX |
Nombres et théorème de RAMSEY |
|||
|
|
||||
Faites un double-clic pour un retour en haut de page
|
Nombres de RAMSEY Bornes et historique Les pages
précédentes nous apprennent que les nombres de Ramsey sont difficilement
connus et les mathématiciens cherchent à cerner leurs valeurs.
|
||
|
|
Sommaire de cette page >>> Approche >>> Nombres de Ramsey >>> Historique général >>> Historique récent |
Débutants Glossaire |
|
S'applique à tout ce qui se compte Supposons que vous essayez de répartir tous les
nombres entiers dans un certain nombre de boites et que vous souhaitiez
éviter de placer des séquences de nombres régulièrement espacés dans l'une
des boites. La théorie de Ramsey montre que vous échouerez
(sauf si vous avez une infinité de boites). La théorie peut être appliquée à presque tout ce
que vous pouvez compter. Principale conclusion: on ne peut pas créer un
système complètement chaotique. |
Calcul des nombres de Ramsey Un nombre de Ramsey renseigne sur la taille à
atteindre pour qu'un type d'organisation soit inévitable dans un ensemble. Un nombre de Ramsey est difficile à calculer. On
ne connait que les plus petits. Il faut se contenter d'établir des limites. Erdős et un collaborateur ont proposé une
limite supérieure il y a près d'un siècle. Aujourd'hui, elle n'a pratiquement
pas évolué. Un progrès est annoncé en 2023. |
|
|
Les premiers nombres de Ramsey sont relativement simples à calculer. |
Les grands nombres de Ramsey ne sont connus que
par encadrement |
|
|
R(k, k) Plus généralement, le nombre de Ramsey R(k, k),
est le nombre minimum de sommets au-delà duquel un graphe ne peut éviter de
contenir une clique de taille k. R(2, 2) = 2 Vous voulez connaître la taille du plus petit
graphe qui doit inévitablement contenir une clique
de taille deux, ou R(2, 2) pour les mathématiciens. Puisqu'un
graphe complet avec deux sommets n'est que deux sommets reliés par une arête,
et que cette arête doit être rouge ou bleue, R(2, 2) vaut 2. R(3, 3) = 6 Il n'est pas très difficile de montrer que le
nombre de Ramsey pour une clique de taille 3, ou R(3, 3), est 6 R(4, 4) = 18 Mais ce n'est qu'en 1955 que R(4, 4) a été fixé à
18. R(4, 5) = 25 Résultat publié en 1993 sur les pages de
Rochester Democrat and Chronicle. R(5, 5) Le cas R(5, 5) reste inconnu; c'est au moins 43
et pas plus grand que 48. |
Examen un par un impossible Même pour des nombres relativement petits, il est
impossible de passer au crible toutes les colorations possibles. Avec un graphe complet à 10 sommets, il y a (10 × 9 / 2 =) 45
arêtes. Chacune de celles-ci peut être colorée de deux
manières. Ce qui produit 245 cas, ce qui est astronomiquement
grand (245 = 35 184 372 088 832). Plus la taille de la clique augmente, plus il est
difficile de calculer le nombre de Ramsey. Fourchette ou encadrement La plage d'incertitude augmente rapidement: selon
les estimations compilées par Stanisław Radziszowski, R(10, 10) pourrait
être aussi petit que 798 et aussi grand que 23 556. Mais les objectifs des mathématiciens vont bien
au-delà de R(10, 10). Ils veulent une formule qui donne une bonne estimation
de R(k, k), même — ou surtout — lorsque k est extrêmement grand. |
|
|
L'histoire des
nombres de Ramsey remonte au début du XXe siècle. Le concept a été introduit
par le mathématicien britannique Frank P. Ramsey dans un article intitulé
"Sur un problème de logique formelle" publié en 1930. Le travail de
Ramsey était principalement motivé par son intérêt pour la logique formelle
et les questions philosophiques liées à la vérité mathématique. L'enquête
initiale de Ramsey s'est concentrée sur un problème spécifique connu sous le
nom de "problème des amis". Le problème
consistait à déterminer le nombre minimum d'invités requis lors d'une fête
pour assurer la présence d'une structure sociale spécifique. Ramsey a formulé
le problème en termes de segments colorées entre des paires d'invités, dans
le but de trouver un sous-graphe complet (une
clique) d'une taille donnée ou un ensemble indépendant (un ensemble de
sommets sans arêtes entre eux) d'une taille donnée. Ramsey a
introduit le concept de "nombre d'ordre" (order number, devenu
nombre de Ramsey) pour décrire le nombre minimum d'invités nécessaires pour
garantir la présence de la structure souhaitée. Il a noté ce nombre R (m, n),
avec m représentant la taille de la clique souhaitée et n représentant la taille
de l'ensemble indépendant souhaité. |
Initialement, Ramsey s'intéressait principalement
à la détermination des limites inférieure et supérieure des valeurs de R(m,
n). Il a établi quelques premières limites et a fourni une limite supérieure
pour R (3, 3), qui est maintenant connue sous le nom de R (3, 3) ≤ 6.
Cependant, il n'a pas été en mesure de déterminer les valeurs exactes de la
plupart des nombres de Ramsey. L'étude des nombres de Ramsey a gagné en
attention et en progrès au cours des décennies suivantes. Dans les années
1940 et 1950, Erdős, Szekeres et d'autres ont apporté des contributions
significatives à la théorie de Ramsey, établissant des limites inférieures et
supérieures pour divers nombres de Ramsey. Ils ont introduit des techniques
combinatoires et prouvé des résultats fondamentaux, tels que le théorème
d'Erdős-Szekeres, qui fournit des limites pour les sous-séquences
monotones dans des séquences de nombres. |
|
|
Ramsey Quelques semaines avant la mort de Ramsey, les
Actes de la London Mathematical Society ont publié l'article dans lequel il a
introduit les nombres de Ramsey. Ce travail ne portait même pas sur les graphes,
mais sur un problème de logique mathématique. Ramsey a prouvé qu'une déclaration qui satisfait
à certaines conditions doit être vraie au moins une partie du temps. L'une de ces conditions était qu'il y ait un
grand "univers" de scénarios pour tester l'énoncé. Comme tremplin
vers ce résultat, Ramsey a montré que le nombre de Ramsey est fini. Erdős et Szekeres Cinq ans plus tard, Erdős et
Szekeres ont montré que R(k,
k) est inférieur à 4k. Et 12 ans plus tard, Erdős a montré qu'il est
plus grand qu'environ Pour ce faire, il a calculé la probabilité qu'un
graphe avec des arêtes colorées au hasard contienne une clique
monochromatique. Cette technique probabiliste est devenue particulièrement
intéressante dans la théorie des graphes. |
Au fil des décennies, de nombreux mathématiciens
ont tenté de réduire l'écart entre les valeurs possibles du nombre de Ramsey.
Borne inférieure Certains ont réussi : En 1975, Joel Spencer a
doublé la limite inférieure. Borne supérieure Et une série d'articles de Conlon, Andrew
Thomason et Ashwin Sah ont abaissé la limite supérieure d'un facteur
d'environ Mais par rapport à la taille des limites du
nombre de Ramsey, ces ajustements étaient faibles. En revanche, toute réduction au 4 dans la formule
d'Erdős et Szekeres R(k, k) < 4k serait une amélioration
exponentielle, augmentant rapidement à mesure que k augmente. Progrès de 2023 Campos, Griffiths, Sahasrabudhe et Morris
affirment avoir montré que R(k,
k) < 3,993k. Ce qui selon les mathématiciens travaillant sur
ce sujet est un résultat spectaculaire. Certains prétendent que la méthode utilisée
pourrait permettre de descendre plus bas: 3,9 voire jusqu'à 3. |
|
Voir Actualités
2023
|
En mars 2024, Sam
Mattheus et Jacques Verstraete viennet de montrer que:
Ce qui prouve la
conjecture de Erdös. Sources: The
asymptotic of r(4,t) |
Voir Actualités
2024
Haut de page (ou
double-clic)
|
Retour |
|
|
|
Suite |
|
|
|
Voir |
|
|
|
Cette page |
http://villemin.gerard.free.fr/aMaths/Topologi/aaaRamse/Bornes.htm
|
|