Nombre de Ramsey: R53

Édition du: 03/06/2023

INDEX Graphe Topologie Géométrie Logique Dénombrement Jeux	Nombres et théorème de RAMSEY
	Petits Nombres (Intro.)	Valeurs – Table	EN BREF
	Principe des tiroirs	Propriétés et calculs	R(3, 3) = 6	R(3, 3, 3)
	Assemblée	Bornes – Historique	R(3, 4) = 9	R(3, 5) = 14
	Graphe	Ramsey – Biographie	R(4, 4) = 18

Faites un double-clic pour un retour en haut de page

Nombre de RAMSEY R(3,5)

Sommaire de cette page

>>> R(3, 5) – Borne inférieure

>>> R(3, 5) – Borne supérieure

>>> Assemblée

Débutants

Dénombrement

Glossaire

Combinatoire

R(3,5) – Borne inférieure

haut

Borne inférieure

Avec 13 sommets, il est possible de colorier le graphe complet avec deux couleurs sans jamais créer un triangle ou un hexagone complet (cinq sommets et toutes les arêtes possibles).

Sur ces deux figures complémentaires:

en bleu, aucun triangle s'appuyant sur les sommets de polygone à 13 côtés;

en rouge, aucun hexagone avec toutes ses diagonales (exemple de tracé d'hexagone en bas; pas de diagonales)

Le nombre R(3, 5) est plus grand que 13.

R(3,5) – Borne supérieure			haut
Borne supérieure On se réfère à l'inégalité des nombres de Ramsey. Voir Table des valeurs	R(3, 5) ≤ R(2, 5) + R(3, 4) = 5 + 9 = 14 On a donc: 13< R(3, 5) ≤ 14 => R(3, 5) = 14
Exemple de tracé Avec 14 sommets, il est possible de créer plusieurs pentagones complets. Il est même impossible de ne pas en créer un. Tracé inévitable Illustrer l'apparition inévitable d'un pentagone complet n'est pas simple.		Exemple de tracé de triangle et pentagones complets Quatre quadrilatères complets.
En terme de complémentaire Pour tout graphe d'au moins 14 sommets (R₁₄), soit G contient un triangle, soit son complémentaire G^c, contient un hexagone complet (R₅).		En résumé, on dit que: R_k est le graphe complet à k sommets

Assemblée

haut

Deux à deux

Dans une assemblée de 14 personnes,

soit chacun connait, au moins, 7 personnes

soit chacun ne connait pas, au moins, 7personnes.

Cas 3, 5

Dans une assemblée de 14 personnes, il est toujours possible de trouver, au moins:

soit cinq personnes qui se connaissent mutuellement (chacun connait les trois autres),

soit trois personnes qui ne se connaissent ni les uns ni les autres.

Ou l'inverse.

Haut de page (ou double-clic)

Retour	Ramsey: R(3, 3, 3)
Suite	Ramsey: EN BREF
Voir	Énigmes et paradoxes Graphe de Delaunay Intelligence artificielle Jeux – Index Logique formelle Percolation Relier les points d'un seul coup de crayon Topologie – Glossaire Tour de Brahmâ	Énigmes et paradoxes Graphe de Delaunay Intelligence artificielle Jeux – Index Logique formelle Percolation Relier les points d'un seul coup de crayon Topologie – Glossaire Tour de Brahmâ
Sites	*Voir Références en page d'introduction*
Cette page	http://villemin.gerard.free.fr/aMaths/Topologi/aaaRamse/R53.htm