UNE ETUDE SUR LES NOMBRES DE RAMSEY CLASSIQUES ET MULTIPLES BINAIRES ET TERNAIRES

Jihad M. JAAM

Dans ce travail, nous donnons une formulation et une démonstration claires du théorème Général de Ramsey en termes de bonne colorations des arêtes d’un hypergraphe . Cette présentation nous a permis de découvrir que, non seulement les graphes admettent des structures régulières, mais également les hypergraphes . Ainsi, nous pouvons associer à chaque hyper graphe un coloriage cyclique . Elle nous a permis également de formuler quelques théorèmes et conjectures sur l’inexistence de bons coloriages cycliques d’hypergraphes binaires et ternaires .

Nous démontrons les propriétés des nombres de Ramsey en termes de bonnes colorations ainsi que les liens étroits entre les nombres de Ramsey classiques de rang h-1 et ceux de rang h . De même, nous montrons que les nombres chromatiques d’un hypergraphe, les nombres de Schur et les nombres de Turán correspondent à des cas particuliers des nombres de Ramsey .

Nous nous sommes également interessé aux problèmes de lévaluation des nombres de Ramsey classique R(k₁, k₂, …,k_m;h) et multiples r(k₁, k₂, …, k_m;h), binaires (h = 2) et ternaires (h = 3) . L’evaluation de chacun de ces nombres est un problème combinatoire NP-difficile . Afin de les déterminer (ou les approximer), nous leur associons des hypergraphes binaires et ternaires . Nous construisons les bonnes colorations des arêtes de ces hypergraphes par des algorithmes d’optimisation stochastique dans lesquels le critère à minimiser est le nombre de cliques monochromes .

Une procédure d’énumération des colorations des arêtes impliquées dans des cliques monochromes est également élaborée, ainsi qu’une méthode de recuit simulé de façon à sortir des optima locaux . Nous retrouvons tous les nombres de Ramsey classiques et multiples et nous associons aux nombres de la forme R(k₁k₂, k₃; h) et r(k₁, k₂, k₃; h) des minorants et des majorants originaux, en se servant particulièrement, des propriétés des coloriages cycliques .