Théorème de Helly

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.