Théorème de Tverberg

Le théorème de Tverberg (en anglais : Tverberg’s theorem ) est un théorème qui fait partie à la fois du domaine mathématique de la géométrie convexe et de la combinatoire topologique ; il remonte à un article publié par le mathématicien norvégien Helge Tverberg en 1966. Il représente une généralisation du théorème de Radon et est le point de départ d'un grand nombre d'investigations plus approfondies. Le théorème de Bárány est lui est étroitement lié, et le théorème de Tverberg peut en être dérivé[1],[2],[3].

Formulation du théorème

Illustration pour n =2 et r =3, N+1 = 7 points permettent une décomposition du type indiqué.

La théorème s'énonce comme suit[4],[5],[6] :

Théorème — Soient n ≥ 1 {\displaystyle n\geq 1} et r ≥ 2 {\displaystyle r\geq 2} deux entiers et N = ( r − 1 ) ⋅ ( n + 1 ) {\displaystyle N=(r-1)\cdot (n+1)} . Pour tout ensemble A ⊆ R n {\displaystyle A\subseteq \mathbb {R} ^{n}} de l'espace euclidien contenant au moins N + 1 {\displaystyle N+1} points, il existe une décomposition

A = A 1 ∪ ˙ A 2 ∪ ˙ ⋯ ∪ ˙ A r {\displaystyle A=A_{1}{\dot {\cup }}A_{2}{\dot {\cup }}\,\dots {\dot {\cup }}A_{r}}

en r {\displaystyle r} sous-ensembles disjoints deux-à-deux telle que l'intersection de leurs enveloppes convexes

conv ⁡ ( A 1 ) ∩ conv ⁡ ( A 2 ) ∩ ⋯ ∩ conv ⁡ ( A r ) {\displaystyle \operatorname {conv} \left(A_{1}\right)\cap \operatorname {conv} \left(A_{2}\right)\cap \,\dots \cap \operatorname {conv} \left(A_{r}\right)}

est non vide.

Exemples

Pour n = 1 {\displaystyle n=1} , un ensemble de N + 1 = 2 r − 1 {\displaystyle N+1=2r-1} points de la droite réelle peut être réparti en r {\displaystyle r} sous-ensembles dont les enveloppes convexes se croisent. En effet, si les points sont x 1 < x 2 < ⋯ < x 2 r − 1 {\displaystyle x_{1}<x_{2}<\cdots <x_{2r-1}} , alors la partition en A i = { x i , x 2 r − i } {\displaystyle A_{i}=\{x_{i},x_{2r-i}\}} pour i = 1 , . . . , r {\displaystyle i=1,...,r} satisfait cette condition (et d'ailleurs elle est unique).

Pour r = 2 {\displaystyle r=2} , le théorème de Tverberg stipule que tout ensemble de n + 2 {\displaystyle n+2} points peut être partitionné en deux sous-ensembles dont les enveloppes convexes se croisent. Ce théorème est connu sous le nom de théorème de Radon. Dans ce cas aussi, pour des points en position générale, la partition est unique.

Dans le cas r = 3 et n = 2, le théorème stipule que sept points quelconques du plan peuvent être divisés en trois sous-ensembles dont les enveloppes convexes se coupent. L'illustration montre un exemple dans lequel les sept points sont les sommets d'un heptagone régulier. Comme le montre l'exemple, il peut y avoir de nombreuses partitions de Tverberg différentes du même ensemble de points ; ces sept points peuvent être partitionnés de sept façons différentes qui diffèrent par des rotations les unes des autres.

Commentaires

  • Le théorème de Tverberg et été conjecturé auparavant par Bryan John Birch dans un article publié en 1959[5].
  • Le théorème est optimal en ce sens que l'énoncé du théorème pour les sous-ensembles avec au plus N {\displaystyle N} points n'est plus valable[7].
  • Comme déjà mentionné plus haut, pour r = 2 {\displaystyle r=2} , on obtient le théorème de Radon.

Théorème de Tverberg topologique

Une formulation équivalente du théorème de Tverberg est la suivante :

Un énoncé équivalent — Soient n {\displaystyle n} et r {\displaystyle r} des entiers positifs et N = ( r − 1 ) ( n + 1 ) {\displaystyle N=(r-1)(n+1)} . Soit f {\displaystyle f} une fonction affine d'un simplexe Δ N → R n {\displaystyle \Delta ^{N}\to \mathbb {R} ^{n}}  ; il existe des faces F 1 , … , F r {\displaystyle F_{1},\ldots ,F_{r}} disjointes deux-à-deux de Δ N {\displaystyle \Delta ^{N}} dont les images par f {\displaystyle f} s'intersectent, en d'autres termes telles que F i ∩ F j = ∅ {\displaystyle F_{i}\cap F_{j}=\emptyset } pour tout 1 ≤ i ≠ j ≤ r {\displaystyle 1\leq i\neq j\leq r} et f ( F 1 ) ∩ ⋯ ∩ f ( F r ) ≠ ∅ {\displaystyle f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset } .

Les énoncés sont équivalentes car toute fonction affine sur un simplexe est uniquement déterminée par les images de ses sommets.

Le théorème topologique de Tverberg généralise cette formulation : on prend pour f {\displaystyle f} une fonction continue et pas nécessairement affine. Mais l'énoncé n'est prouvé que dans le cas où r {\displaystyle r} est une puissance d'un nombre premier. L'énoncé est le suivant :

Théorème topologique — Soit n {\displaystyle n} un entier positif, soit r {\displaystyle r} une puissance d'un nombre premier et soit N = ( n + 1 ) ( r − 1 ) {\displaystyle N=(n+1)(r-1)} . Si f : Δ N → R n {\displaystyle f:\Delta ^{N}\to \mathbb {R} ^{n}} est une fonction continue du simplexe Δ N {\displaystyle \Delta ^{N}} de dimension N {\displaystyle N} , alors il existe r {\displaystyle r} faces deux à deux disjointes de Δ N {\displaystyle \Delta ^{N}} dont les images sous f {\displaystyle f} se coupent. En d'autres termes, il existe des faces F 1 , . . . , F r {\displaystyle F_{1},...,F_{r}} de Δ N {\displaystyle \Delta ^{N}} telles que F i ∩ F j = ∅ {\displaystyle F_{i}\cap F_{j}=\emptyset } pour 1 ≤ i ≠ j ≤ r {\displaystyle 1\leq i\neq j\leq r} et f ( F 1 ) ∩ ⋯ ∩ f ( F r ) ≠ ∅ {\displaystyle f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset } .

Le théorème topologique de Tverberg a été prouvé pour un nombre premier r {\displaystyle r} par Imre Bárány, Senya B. Shlosman et András Szűcs[8]. Matousek, dans la deuxième édition de son livre, présente en 2008 une autre preuve utilisant des « deleted joins ».

Le théorème a été prouvé pour r {\displaystyle r} une puissance d'un nombre premier par Ozaydin[9] et ultérieurement par Volovikov[10] et par Sarkaria[11]

Bibliographie

  • « The Tverberg Partition Theorem », Theorem of the day, no 107,‎ 2005–2022 (lire en ligne, consulté le ).
  • Imre Bárány et Pablo Soberón, « Tverberg's theorem is 50 years old: A survey. », Bull. Amer. Math. Soc. (N.S.), vol. 55,‎ , p. 459–492.
  • Bryan J. Birch, « On 3N points in a plane », Proceedings of the Cambridge Philosophical Society, vol. 55,‎ , p. 289–293.
  • W. A. Coppel, Foundations of Convex Geometry, Cambridge University Press, coll. « Australian Mathematical Society Lecture Series » (no 12), (ISBN 0-521-63970-0).
  • Mark Longueville, A Course in Topological Combinatorics, Springer-Verlag, coll. « Universitext », (ISBN 978-1-4419-7909-4, MR 2976494).
  • Jiří Matoušek, Lectures on Discrete Geometry, Springer-Verlag, coll. « Graduate Texts in Mathematics » (no 212), (ISBN 0-387-95373-6, MR 1899299).
  • Jiří Matoušek, Anders Björner et Günter M. Ziegler, Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler, Springer-Verlag, coll. « Universitext », , 2e éd., xii+214 (ISBN 978-3-540-00362-5, zbMATH 1234.05002).
  • Helge Tverberg, « A generalization of Radon's theorem », The Journal of the London Mathematical Society, vol. 41,‎ , p. 123-128 (MR 0187147).
  • Stephan Hell, Tverberg-type theorems and the Fractional Helly property (Thèse de doctorat), Technische Universität Berlin, (DOI 10.14279/DEPOSITONCE-1464, lire en ligne)

Notes et références

  • (en)/(de) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Tverberg's theorem » (voir la liste des auteurs) et en allemand « Satz von Tverberg » (voir la liste des auteurs).
  1. ↑ Coppel 1998, p. 68 et suiv..
  2. ↑ Longueville 2013, p. 106 et suiv..
  3. ↑ Matoušek 2002, p. 200 et suiv..
  4. ↑ Coppel 1998, p. 69.
  5. ↑ a et b Longueville 2013, p. 106.
  6. ↑ Matoušek 2002, p. 200.
  7. ↑ Coppel 1998, p. 70.
  8. ↑ (en) I. Bárány, S. B. Shlosman et A. Szücs, « On a Topological Generalization of a Theorem of Tverberg », Journal of the London Mathematical Society, vol. s2-23, no 1,‎ , p. 158-164 (DOI 10. 1112/jlms/s2-23.1.158, lire en ligne)
  9. ↑ Murad Ozaydin, « Equivariant Maps for the Symmetric Group », Préprint resté non publié,‎ (lire en ligne)
  10. ↑ (en) A. Yu. Volovikov, « On a topological generalization of the Tverberg theorem », Mathematical Notes, vol. 59, no 3,‎ , p. 324–326 (ISSN 1573-8876, DOI 10.1007/BF02308547, lire en ligne)
  11. ↑ K. S. Sarkaria, « Tverberg partitions and Borsuk-Ulam theorems », Pacific Journal of Mathematics, vol. 196, no 1,‎ , p. 231-241 (ISSN 0030-8730, lire en ligne).
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique