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^[1],[2].

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

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^[3], 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 ${\displaystyle n=d+2}$. Les hypothèses du théorème assurent l'existence d'un point ${\displaystyle a_{1}}$ qui se trouve dans l'intersection des ${\displaystyle X_{2},X_{3},\dots ,X_{d+2}}$.

${\displaystyle a_{1}\in \bigcap _{i=2}^{d+2}X_{i}}$

De la même manière on peut définir pour tout ${\displaystyle j\in \{1,2,\dots ,{d+2}\}}$ un élément ${\displaystyle a_{j}}$ dans l'intersection des ${\displaystyle X_{i},i\neq j}$

${\displaystyle a_{j}\in \bigcap _{i=1,i\neq j}^{d+2}X_{i}.}$

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

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

Dans cette nouvelle collection, chaque intersection de ${\displaystyle 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.

S'il y a une répétition dans la liste de points ${\displaystyle (a_{1},\ldots ,a_{d+2})}$, disons ${\displaystyle a_{j}=a_{k}}$, avec ${\displaystyle j\neq k}$, alors ${\displaystyle a_{j}}$ est clairement dans l'intersection ${\displaystyle \bigcap _{i=1}^{d+2}\Delta _{i}}$, et la propriété est prouvée. Sinon, on applique le théorème de Radon à l'ensemble ${\displaystyle A=\{a_{1},a_{2},\dots ,a_{d+2}\}}$.

Ce théorème assure l'existence de deux sous-ensembles disjoints ${\displaystyle A_{1},A_{2}\subset A}$ tels que l'enveloppe convexe de ${\displaystyle A_{1}}$ intersecte celle de ${\displaystyle A_{2}}$. Il existe donc un point ${\displaystyle x}$ appartenant à l'intersection des deux enveloppes convexes de ${\displaystyle A_{1}}$ et ${\displaystyle A_{2}}$. On va montrer que l'intersection des ${\displaystyle \Delta _{i}}$ contient ce point ${\displaystyle x}$, ce qui démontrera l'énoncé intermédiaire.

Prenons ${\displaystyle j\in \{1,2,\dots ,{d+2}\}}$. Si ${\displaystyle a_{j}\in A_{1}}$, alors ${\displaystyle a_{j}\notin A_{2}}$, et par conséquent tous les points de ${\displaystyle A_{2}}$ sont des ${\displaystyle a_{k}}$ avec ${\displaystyle k\not =j}$. Or de tels points sont dans ${\displaystyle \Delta _{j}}$ par définition, et donc ${\displaystyle A_{2}\subset \Delta _{j}}$. Comme ${\displaystyle \Delta _{j}}$ est convexe, il contient alors l'enveloppe convexe de ${\displaystyle A_{2}}$ et par conséquent on a : ${\displaystyle x\in \Delta _{j}}$. De la même manière, si ${\displaystyle a_{j}\notin A_{1}}$, alors ${\displaystyle A_{1}\subset \Delta _{j}}$, et le même raisonnement donne ${\displaystyle x\in \Delta _{j}}$. Le point x fourni par Radon est donc bien commun à tous les ${\displaystyle \Delta _{i}}$.

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

Sur le polytope compact enveloppe convexe des points de ${\displaystyle A=(a_{1},\ldots ,a_{d+2})}$, on considère la fonction continue ${\displaystyle f}$ définie par :

${\displaystyle f(x)=\mathrm {Max} _{1\leq i\leq d+2}\left(d(x,\Delta _{i})\right)}$

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

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

Pour ${\displaystyle \theta \in [0,1]}$, on va noter ${\displaystyle x_{\theta }=(1-\theta )x+\theta a_{1}}$ le point courant du segment ${\displaystyle [x,a_{1}]}$.

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

On va montrer le théorème par l'absurde. Supposons donc l'intersection des ${\displaystyle \Delta _{i}}$ vide.

Chacun des simplexes ${\displaystyle \Delta _{i}}$ est une intersection d'un nombre fini de demi-espaces. Énumérons la liste complète de ces demi-espaces ${\displaystyle R_{1},R_{2},\ldots ,R_{k}}$ de ${\displaystyle \mathbb {R} ^{d}}$. On remarque tout de suite que l'intersection des ${\displaystyle \Delta _{i}}$ est égale à l'intersection des ${\displaystyle R_{j}}$ qui est donc elle aussi vide.

Pour chacun de ces demi-espaces, prenons une forme affine ${\displaystyle f_{j}}$ pour laquelle ${\displaystyle R_{j}=\{x\in E\,\mid \,f_{j}(x)\geq 0\}}$.

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 ${\displaystyle f_{j}}$ égale à la forme constante ${\displaystyle -1}$. Dit autrement, il existe un ${\displaystyle \lambda >0}$ tel que ${\displaystyle -\lambda }$ soit dans l'enveloppe convexe des ${\displaystyle f_{j}}$.

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

Pour chacun d'entre eux, prenons un simplexe qu'il contient parmi la liste des ${\displaystyle \Delta _{i}}$ : ces simplexes sont au plus ${\displaystyle d+1}$ donc se rencontrent par hypothèse. C'est contradictoire.

Dans le plan, soient S₁, …, S_q des segments portés par q droites parallèles. Si les segments S_i 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 S_i sont parallèles à l'axe Oy, les X_i = { (a,b) | la droite d'équation y = ax+b rencontre S_i } sont des convexes de R² auxquels on peut appliquer le théorème de Helly.

• H. G. Eggleston, Convexity, Cambridge University Press, coll. « Cambridge Tracts in Mathematics » (n^o 47), 1958, viii + 136 (ISBN 9780511566172, DOI 10.1017/CBO9780511566172).
• Steven R. Lay, Convex sets and their applications, John Wiley & Sons, coll. « Pure and Applied Mathematics », 1982, xvi + 244 (zbMATH 0492.52001).

• Théorème de Kirchberger, par exemple dans (en) Alexander Barvinok, A Course in Convexity, AMS, coll. « GSM » (n^o 54), 2002, 366 p. (ISBN 978-0-8218-2968-4, lire en ligne), 21
• Théorème de Tverberg

• Portail de la géométrie