Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (2)

Le pouvoir de l’interdit

Publié le 21 décembre 2017
Bien illustré
> 30 minutes

Dans une première partie, nous avons vu qu’une certaine dose d’ordre est inévitable et qu’en particulier, tout graphe contient un grand ensemble stable ou une grande clique.
La taille minimale de cet ensemble stable ou clique inévitable est obtenue pour les graphes aléatoires. Que se passe-t-il si, à l’opposé, nous imposons une contrainte locale forte ? C’est le propos de la conjecture d’Erdős-Hajnal…

Au moment de continuer notre cheminement du théorème de Ramsey à la conjecture d’Erdős-Hajnal, et avant de nous plonger plus profondément encore dans les « technicalités » mathématiques, prenons le temps de contempler le paysage. Le point de vue, en ce moment charnière, est une invitation à la rêverie mathématique sur les notions d’ordre et de hasard, une invitation à nourrir notre intuition de ce monde toujours surprenant.

La faculté qui nous apprend à voir, c’est l’intuition. Sans elle, le géomètre serait comme un écrivain qui serait ferré sur la grammaire, mais qui n’aurait pas d’idée.

Henri Poincaré

Lire l’article en ligne

ÉCRIT PAR

Patrice Ossona de Mendez

Chercheur, Editeur en chef the European Journal of Combinatorics - Centre d'analyse et de mathématique sociales (CAMS)-École des Hautes Études en Sciences Sociales-CNRS

Partager