Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Helly
Résumé
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.
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 : .
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.