Théorème de Helly - Définition

Introduction

Le théorème de Helly est un résultat combinatoire sur les convexes.

Ce résultat a été prouvé en 1913 par Eduard Helly, et il a été publié par Johann Radon en 1921.

Énoncé

Il est facile d'étendre le théorème à des familles infinies d'ensembles convexes, en rajoutant une hypothèse de compacité

Preuves

On donne la preuve dans le cas fini (le cas infini se ramène au cas fini par un argument de compacité).

Il y a plusieurs preuves du théorème de Helly, mais toutes se prêtent bien à être aiguillées par l'énoncé intermédiaire suivant :

Dans tous les modes de démonstration, il y a un travail géométrique un peu subtil à faire pour parvenir à cet énoncé intermédiaire ; en revanche terminer la preuve ne demande pas d'idée bien compliquée.

Commençons donc par le plus facile, en montrant que l'énoncé intermédiaire entraîne le théorème de Helly sous la forme donnée plus haut.

Supposons d'abord que n = d + 2. Les hypothèses du théorème assurent l'existence d'un point a₁ qui se trouve dans l'intersection des .

De la même manière on peut définir pour tout un élément a_j dans l'intersection des

Appliquons l'énoncé intermédiaire à ces points : il fournit un point x qui est à la fois dans tous les simplexes Δ_i. Mais, par définition de Δ_i, tous les sommets de ce simplexe sont dans X_i. Donc x est un point de X_i pour tout i.

À présent, raisonnons par récurrence : supposons que n > d + 2 et que le résultat soit vrai au rang n − 1. Le raisonnement précédent montre que toute intersection de d + 2 ensembles convexes est non vide. On considère la nouvelle collection obtenue en remplaçant X_{n − 1} et X_n par l'ensemble

Dans cette nouvelle collection, chaque intersection de d + 1 ensembles est non vide. L'hypothèse de récurrence implique donc que l'intersection de cette nouvelle collection est non vide ; mais cette intersection est la même que celle de la collection initiale.

On va maintenant donner plusieurs preuves de l'énoncé intermédiaire.

Première preuve : via le théorème de Radon

S'il y a une répétition dans la liste de points , disons a_j = a_k, avec , alors a_j est clairement dans l'intersection , et la propriété est prouvée. Sinon, on applique le théorème de Radon à l'ensemble .

Ce théorème assure l'existence de deux sous-ensembles disjoints tels que l'enveloppe convexe de A₁ intersecte celle de A₂. Il existe donc un point x appartenant à l'intersection des deux enveloppes convexes de A₁ et A₂. On va montrer que l'intersection des Δ_i contient ce point x, ce qui démontrera l'énoncé intermédiaire.

Prenons . Si , alors , et par conséquent tous les points de A₂ sont des a_k avec . Or de tels points sont dans Δ_j par définition, et donc . Comme Δ_j est convexe, il contient alors l'enveloppe convexe de A₂ et par conséquent on a : . De la même manière, si , alors , et le même raisonnement donne . Le point x fourni par Radon est donc bien commun à tous les Δ_i.

Deuxième preuve : via le théorème de Carathéodory

On munit l'espace affine d'une structure euclidienne.

Sur le polytope compact enveloppe convexe des points de , on considère la fonction continue f définie par :

puis on prend un point x de ce polytope en lequel elle admet son minimum. Montrer que les simplexes se rencontrent revient donc à montrer que f(x) = 0.

Le théorème de Carathéodory assure qu'on peut extraire de A une sous-famille avec seulement d + 1 points dont x est barycentre à coefficients positifs, autrement dit qu'il existe un indice i tel que x appartient à Δ_i. Quitte à renuméroter les points de A, on supposera que x appartient à Δ₁.

Pour , on va noter x_θ = (1 − θ)x + θa₁ le point courant du segment [x,a₁].

L'idée de la fin de la preuve est alors la suivante : puisque a₁ est dans , quand on fait glisser x_θ le long du segment [x,a₁] en direction de a₁, ce point se rapproche de tous les simplexes . Par ailleurs, il s'éloigne peut-être de Δ₁, mais au départ il en était à distance nulle et pour θ petit il en est encore à distance très petite et donc sans influence sur la valeur f(x_θ) (puisque c'est un Max) —du moins si . Le résultat de ces observations, c'est que f(x_θ) commence par diminuer quand θ augmente en restant suffisamment petit, et diminue même strictement si . Ceci contredit la minimalité de f(x).

Troisième preuve : par le théorème de Carathéodory et le lemme de Farkas

On va montrer le théorème par l'absurde. Supposons donc l'intersection des Δ_i vide.

Chacun des simplexes Δ_i est une intersection d'un nombre fini de demi-espaces. Énumérons la liste complète de ces demi-espaces de . On remarque tout de suite que l'intersection des Δ_i est égale à l'intersection des R_j qui est donc elle aussi vide.

Pour chacun de ces demi-espaces, prenons une forme affine f_j pour laquelle .

Par le lemme de Farkas sous sa forme de critère de consistance pour un système d'inéquations affines, il existe donc une combinaison linéaire à coefficients positifs des f_j égale à la forme constante − 1. Dit autrement, il existe un λ > 0 tel que − λ soit dans l'enveloppe convexe des f_j.

Par le théorème de Carathéodory, il existe une sous-collection d'au plus d + 1 de ces f_j qui contienne encore − λ dans son enveloppe convexe. En réappliquant le lemme de Farkas (dans ce sens c'est une évidence), l'intersection des R_j correspondants est alors vide.

Pour chacun d'entre eux, prenons un simplexe qu'il contient parmi la liste des Δ_i : ces simplexes sont au plus d + 1 donc se rencontrent par hypothèse. C'est contradictoire.