Théorème de Helly

Le théorème de Helly est un résultat combinatoire de géométrie 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é 

{{Théorème|Corollaire|Si  est une collection de sous-ensembles compacts convexes de  et que pour toute partie  finie de cardinal supérieur ou égal à ,  alors l'intersection de tous les  est non vide, c'est-à-dire : .}}

 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 . Les hypothèses du théorème assurent l'existence d'un point  qui se trouve dans l'intersection des .

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

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

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

Dans cette nouvelle collection, chaque intersection de  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 , avec , alors  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  intersecte celle de . Il existe donc un point  appartenant à l'intersection des deux enveloppes convexes de  et . On va montrer que l'intersection des  contient ce point , ce qui démontrera l'énoncé intermédiaire.

Prenons . Si , alors , et par conséquent tous les points de  sont des  avec . Or de tels points sont dans  par définition, et donc .
Comme  est convexe, il contient alors l'enveloppe convexe de  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 .

 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  définie par :

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

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

Pour , on va noter  le point courant du segment .

L'idée de la fin de la preuve est alors la suivante : puisque  est dans , quand on fait glisser  le long du segment  en direction de , 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  (puisque c'est un ) —du moins si . Le résultat de ces observations, c'est que  commence par diminuer quand  augmente en restant suffisamment petit, et diminue même strictement si . Ceci contredit la minimalité de .

 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  vide.

Chacun des simplexes  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  est égale à l'intersection des  qui est donc elle aussi vide.

Pour chacun de ces demi-espaces, prenons une forme affine  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  égale à la forme constante . Dit autrement, il existe un  tel que  soit dans l'enveloppe convexe des .

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

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

 Application 

Dans le plan, soient S1, …, Sq des segments portés par q droites parallèles. Si les segments Si admettent trois à trois une sécante commune alors il existe une droite qui les rencontre tous. En effet, en choisissant un repère pour lequel les Si sont parallèles à l'axe Oy, les Xi = { (a,b) | la droite d'équation y = ax+b rencontre Si'' } sont des convexes de R2 auxquels on peut appliquer le théorème de Helly.

Notes et références 

 .
 .

Voir aussi 
 Théorème de Kirchberger, par exemple dans 
 Théorème de Tverberg

Theoreme de Helly
Theoreme de Helly
Helly