COMBINATOIRE ANALYSE

Théorèmes d'existence

Le théorème de Ramsey et celui de Hall-König, dont nous donnons les énoncés maintenant, jouent un rôle spécial en combinatoire. Ils assurent l'existence de certaines configurations dans des conditions très générales et ont ainsi trouvé de nombreuses applications.

Supposons que l'on ait un graphe de six sommets, dans lequel deux sommets distincts sont joints par une arête « coloriée » en bleu ou en rouge. Démontrons la propriété (P) suivante : Il existe un triangle dont les trois arêtes ont la même couleur. Considérons en effet les cinq arêtes issues d'un sommet donné S₁ du graphe. Nécessairement trois de ces arêtes ont la même couleur, disons bleue ; appelons-les S₁S₂, S₁S₃ et S₁S₄. Si l'une des arêtes S₂S₃, S₂S₄, S₃S₄ est bleue, disons S₂S₃, le triangle S₁S₂S₃ est bleu. Sinon les arêtes S₂S₃, S₂S₄, S₃S₄ sont rouges, mais alors le triangle S₂S₃S₄ est rouge. La propriété (P) est ainsi vérifiée. L'argument essentiel qui a été utilisé est le principe des tiroirs : si l'on met n objets dans p tiroirs (p ≤ n), alors le nombre des objets dans au moins un tiroir est supérieur ou égal à n/p. Le théorème de Ramsey peut être considéré comme une généralisation de ce principe.

Théorème de Ramsey. Soit X un ensemble de n éléments et supposons donnés d'abord trois entiers p, q, r satisfaisant à p ≥ r, q ≥ r et r ≥ 1, ensuite une partition de l'ensemble de toutes les parties de X de cardinal r, en deux classes P et Q. Alors il existe un entier N(p, q, r) ne dépendant que des entiers p, q, r et non pas de l'ensemble X tel que la propriété (P′) suivante soit vérifiée : Si n ≥ N(p, q, r), il existe ou bien une partie A de X de p éléments qui a tous ses sous-ensembles de cardinal r dans P, ou bien une partie B de q éléments qui a tous ses sous-ensembles de cardinal r dans Q.

Dans l'exemple précédent, on avait n = 6, p = q = 3 et r = 2. Les ensembles de deux éléments sont alors les arêtes, qui sont divisées en deux classes, les bleues (classe P) et les rouges (classe Q). La propriété (P) équivaut à dire que l'on a N(3, 3, 2) ≥ 6. En fait, on a l'égalité.

Le théorème de Hall- König peut être énoncé de deux façons différentes, soit en termes de systèmes de représentants distincts, soit en termes de matrices à coefficients 0 ou 1. Nous ne donnerons pas ici l'énoncé sous cette dernière forme. Soit X = {1, 2, 3, 4, 5} l'ensemble des cinq premiers entiers et considérons les sous-ensembles X₁ = {1, 4}, X₂ = {1, 2, 4}, X₃ = {1, 2, 4} et X₄ = {2, 4, 5} de X. On peut choisir des entiers x₁, x₂, x₃, x₄ de sorte que l'on ait x_i∈ X_i pour 1 ≤ i ≤ 4 et que tous les x_i soient distincts. Il suffit de prendre en effet les nombres x₁ = 1, x₂ = 2, x₃ = 4, x₄ = 5. Si on remplace dans cet exemple X₄ par X₄′ = {2, 4}, un tel choix n'est plus possible puisque la réunion des quatre ensembles X₁, X₂, X₃, X₄′ ne contient que trois éléments distincts 1, 2, 4. On est ainsi amené à donner la définition suivante : Étant donné une suite (X₁, X₂, ..., X_n) de parties d'un ensemble non vide X, on dit que cette suite possède un système de représentants distincts, s'il existe une suite (x₁, x₂, ..., x_n) de n éléments distincts de X satisfaisant à x_i∈ X_i pour tout i tel que 1 ≤ i ≤ n.

Théorème de Hall-König. La condition nécessaire et suffisante pour qu'une suite (X₁, X₂, ..., X_n) de parties d'un ensemble non vide X possède un système de représentants distincts est que, pour tout k (1 ≤ k ≤ n) et tout sous-ensemble {i₁, i₂, ..., i_k} de k indices extrait de {1, 2, ..., n} on ait |X_i1 ∪ X_i2 ∪ X_ik| ≥ k.

La condition[...]