Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
160 personne(s) sur le site en ce moment
E. Cartan

Les maths pour l'agreg

A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Triangulations d'un simplexe - Lemme de Sperner - conséquences next up previous index
suivant: Index monter: Zoologie de la topologie précédent: Inégalité isodiamétrique   Index

Triangulations d'un simplexe - Lemme de Sperner - conséquences

On s'inspire ici du livre [4], en tâchant de donner une preuve plus détaillée.

Définition On appelle simplexe de dimension $ n$ l'enveloppe convexe de $ n+1$ points formant un repère affine.

On appelle face d'un simplexe l'enveloppe convexe d'un nombre fini (quelconque) de ses points. Sa dimension est par définition le nombre de points de cette face moins $ 1$. On appelle $ g$-face une face de dimension $ g$.

Lemme Tout élément $ P$ appartenant à un simplexe $ \Delta$ est décrit de manière unique par ses coordonnées barycentriques dans le repère des sommets de ce simplexe, si l'on impose que la somme des dites coordonnées est $ 1$. Chaque coordonnée est $ \geq 0$.

Démonstration: Voir la proposition-définition [*].$ \sqcap$$ \sqcup$

On se donne pour la suite un simplexe $ \Delta$ de $ \mathbb{R}^n$ de sommets $ x_0$, $ x_1$, ... , $ x_n$.

Tout point $ x$ de $ \Delta$ est donc repéré par ses coordonées barycentriques $ c_0(x)$, ... , $ c_n(x)$, avec $ \sum_{i=0}^n c_i(x)=1$, et $ \sum_{i=0}^n c_i(x).\overrightarrow {xx_i}=\overrightarrow 0$.

Définition Soit $ \sigma \in \sigma _{n+1}$ une permutation de $ [0,n]$.

On note $ \Delta _\sigma $ l'ensemble des points $ x$ de $ \Delta$ tels que

$\displaystyle c_{\sigma (0)}(x) \geq c_{\sigma (1)}(x) \geq ... \geq c_{\sigma (n)}(x)$


Proposition

$ \bullet $$ \Delta$ est l'union des $ \Delta _\sigma $.

$ \bullet $Pour tout $ \sigma \in \sigma _{n+1}$, $ \Delta _\sigma $ est un simplexe.

$ \bullet $Les intérieurs des $ \Delta _\sigma $ sont disjoints.

Démonstration: Le premier $ \bullet $ne mérite pas notre attention.

Pour le second $ \bullet $, c'est plus difficile, et nous allons donc détailler:

Un point $ x$ est dans $ \Delta _I$ avec $ I$ la permutation identité, si ses coordonnées $ c_0$, $ c_1$,...,$ c_n$ vérifient $ c_0 \geq c_1 \geq ... \geq c_n$. En écrivant

$\displaystyle t_0=c_0$

$\displaystyle t_1=c_1-c_0$

$\displaystyle t_2=c_2-c_1-c_0$

$\displaystyle t_i=c_i-c_{i-1}-c_{i-2}-...-c_0$

$\displaystyle t_n=c_n-c_{n-1}-c_{n-2}-...-c_0$

on voit que $ x$ est dans $ \Delta _I$ si et seulement si il est dans l'enveloppe convexe des points de coordonnées barycentriques

$\displaystyle (1,0,0,0,...,0)$

$\displaystyle (1,1,0,0,...,0)$

$\displaystyle (1,1,1,0,...,0)$

$\displaystyle ...$

$\displaystyle (1,1,1,1,...,1)$

Je n'ai pas normalisé pour ne pas alourdir la notation, sinon on obtient

$\displaystyle (1,0,0,0,...,0)$

$\displaystyle (\frac12,\frac12,0,0,...,0)$

$\displaystyle (\frac13,\frac13,\frac13,0,...,0)$

$\displaystyle ...$

$\displaystyle (\frac1n,\frac1n,\frac1n,\frac1n,...,\frac1n)$

Donc il s'agit bien d'un simplexe. Il est non vide car les sommets définis ci-dessus forment bien un repère affine et donc l'intérieur est un voisinage de leur isobarycentre.

Il en va de même pour autre chose que l'identité; $ \Delta _\sigma $ est l'enveloppe convexe de $ n$ points comportant respectivement un $ 1$ et seulement des 0 ailleurs, deux $ 1$ et seulement des 0 ailleurs, trois $ 1$ et seulement des 0 ailleurs, et ainsi de suite, chaque fois les $ 1$ étant conservés, et un nouveau $ 1$ étant ajouté.

Le troisième $ \bullet $est démontré dans le lemme qui suit.$ \sqcap$$ \sqcup$

Définition On appelle triangulation d'un simplexe $ \Delta$ un ensemble fini de simplexes $ \Delta _i$ tels que:

$ \bullet $ $ \cup_i \Delta _i=\Delta $

$ \bullet $Si $ i\neq j$, $ Int(\Delta _j) \cap Int(\Delta _i)=\emptyset$

$ \bullet $L'intersection d'une face de $ \Delta _i$ et d'une face de $ \Delta _j$ (pour $ i=j$ ou $ i\neq j$) est soit vide soit une face de $ \Delta _i$ et une face de $ \Delta _j$.

Lemme L'ensemble des $ \Delta _\sigma $ pour $ \sigma \in \sigma _{n+1}$ est une triangulation de $ \Delta$.

Démonstration: $ \bullet $Il est bien clair que la réunion des $ \Delta _\sigma $ est bien égale à $ \Delta$.

$ \bullet $L'intersection des intérieurs de $ \Delta _\sigma $ et $ \Delta _\tau $ avec $ (\sigma ,\tau )\in\sigma _{n+1}^2$ est incluse dans l'intérieur des intersections, et donc incluse dans un hyperplan; donc elle est vide.

$ \bullet $Regardons ce qu'est une face de simplexe, par exemple le simplexe $ \Delta _I$, avec $ I$ la permutation identité.

Il s'agit du barycentre d'un nombre fini de sommets, de la forme

$\displaystyle (1/p,1/p,...,1/p,1/p,0,0,...,0,0).$

C'est à dire d'une somme pondérés de

$\displaystyle (1,0,0,...,0)$

$\displaystyle (\frac{1}i,...,\frac1i,0,...,0)$

$\displaystyle (\frac{1}i,...,\frac1j,0,...,0)$

On constate donc qu'une face est entièrement décrite par des équations du type $ c_0(x) r_0 c_1(x) r_1 c_2(x) r_2 ... r_{n-1} c_n(x) r_n 0$, avec $ r_i$ opérateur $ =$ ou $ \geq$.

Une intersection de faces va encore être du même type, car au plus elle va remplacer des $ \geq$ par des $ =$. D'où le résultat.$ \sqcap$$ \sqcup$

Lemme Dans la triangulation de $ \Delta$ en les $ \Delta _\sigma $$ \sigma $ appartient à $ \sigma _{n+1}$, les $ \Delta _\sigma $ ont un diamètre inférieur à $ \frac{n}{n+1}$ fois le diamètre de $ \Delta$.

Démonstration:

$ \bullet $le centre de gravité $ x$ (ou isobarycentre) de $ \Delta$ appartient à tout simplexe $ \Delta _\sigma $ (car tous les $ c_i(x)$ sont égaux, égaux à $ \frac1{n+1}$).

$ \bullet $la distance de $ x$ à un point de $ \Delta$ est inférieur ou égale aux distances aux sommets de $ \Delta$, donc la distance d'un point de $ \Delta _\sigma $ à $ x$ est toujours inférieure ou égale à $ \frac{n}{n+1}$ fois la longueur de la médiane.

$ \bullet $le diamètre de $ \Delta _\sigma $, qui est la longueur maximal d'un de ses côtés, est donc majoré par la longueur max des côtés sur la face opposée à $ x$, et par la longueur max des arêtes débouchant sur $ x$... Dans tous les cas, cette longueur est majorée par celle d'une médiane de $ \Delta$ ou d'une face du simplexe (une face de dimension quelconque, éventuellement une arête).$ \sqcap$$ \sqcup$

Lemme Pour tout $ \epsilon $ on peut obtenir des triangulations de $ \Delta$ en simplexes de diamètre inférieurs à $ \epsilon $.

Démonstration:

On va utiliser par récurrence le lemme précédent. Les deux premiers $ \bullet $de la définition d'une triangulation sont faciles à obtenir, le problème est de montrer qu'une partition de chaque élément d'une partition donne encore une partition vérifiant le troisième point, c'est à dire le fait que l'intersection de deux faces de deux éléments distincts de la partition est soit vide soit égale à une face de chacun des deux éléments. Intuitivement, le problème est de voir que les faces se "recollent" bien.

Pour cela il suffit de voir que la triangulation faite selon le lemme précédent induit une triangulation de chacune des faces du dit simplexe - triangulation égale à celle qu'aurait donné le même lemme sur cette face. Cela se voit facilement en voyant qu'une face est une partie du simplexe où l'on annule une des composantes.$ \sqcap$$ \sqcup$

Définition [Numérotation standard d'un simplexe] Etant donnée une triangulation $ \Delta _i$ d'un simplexe $ \Delta$, on note $ S$ l'ensemble des sommets des éléments de cette triangulation. On appelle numérotation standard d'une triangulation d'un simplexe de sommets $ x_0,...,x_n$ une application $ f$ de $ S$ dans $ \{0,n\}$ telle que $ f(x_i)=i$ et si pour tout $ s$ dans $ S$ $ f(s)=i$ pour un certain $ i$ tel que $ x_i$ est un sommet de la face de $ \Delta$ de dimension minimale contenant $ x$.

NB: la caractérisation "pour tout $ s$ dans $ S$ $ f(s)=i$ pour un certain $ x_i$ tel que $ x_i$ est un sommet de la face de $ \Delta$ de dimension minimale contenant $ x$" inclue la condition $ f(x_i)=i$, car une face peut très bien avoir une dimension 0.

On constate donc que dans une triangulation comme celles que l'on a construites plus haut, l'isobarycentre est autorisé à prendre n'importe quelle valeur puisque la seule face qui le contienne est $ \Delta$ lui-même.

Proposition Une numérotation standard $ f$ d'une triangulation du simplexe $ \Delta$ enveloppe convexe de $ (x_0,...,x_n)$ induit une numérotation standard de la triangulation induite sur le simplexe $ \Delta '$ enveloppe convexe de $ (x_0,...,x_{n-1})$.

Démonstration:

$ \bullet $Il est clair que tout sommet de la triangulation de $ \Delta '$ a bien un numéro $ <n$.

$ \bullet $Soit $ x$ sommet de la triangulation de $ \Delta '$ appartenant à une face $ F$ minimale de $ \Delta$.

$ \bullet $$ F$ est forcément incluse dans $ \Delta '$.

$ \bullet $$ F$ est donc la même face que la face minimale de $ x$ dans $ \Delta '$.

$ \bullet $Donc la numérotation induite est bien standard.$ \sqcap$$ \sqcup$

Lemme [Lemme de Sperner] Toute triangulation d'un simplexe de dimension $ n$ munie d'une numérotation standard possède un élément numéroté $ (0,...,n)$.

Démonstration:

$ \bullet $Soit $ \Delta$ notre simplexe, supposé muni d'une numérotation standard $ f$ sur une triangulation $ T$ de $ \Delta$.

$ \bullet $On note $ P(U)$ la propriété pour un simplexe $ U$ de dimension $ r$ d'avoir un sommet numéroté $ i$ et un seul pour tout $ i$ dans $ [1,r]$.

$ \bullet $Soit $ E$ l'ensemble des simplexes de $ T$ ayant la propriété $ P$.

$ \bullet $Soit $ F$ l'ensemble des simplexes de $ T$ qui ne sont pas dans $ E$ mais dont un numéro et un seul est numéroté $ i$ pour tout $ i$ dans $ [0,n-1]$ (attention ils ne vérifient donc pas la propriété $ P$).

$ \bullet $Soit $ G$ l'ensemble des $ n-1$-faces de simplexes de $ T$ inclus dans $ \Delta '$ et vérifiant la propriété $ P$ (rappelons qu'une face de simplexe est un simplexe).

$ \bullet $Soit $ H$ l'ensemble des $ n-1$-faces de simplexes de $ T$ qui ne sont pas contenues dans $ \Delta '$ et qui vérifient la propriété $ P$.

$ \bullet $Chaque élément de $ E$ contient une et une seule $ n-1$-face ayant la propriété $ P$.

$ \bullet $Chaque élément de $ F$ contient exactement deux faces ayant la propriété $ P$ (facile, il y a exactement deux éléments numérotés pareil, donc on bâtit deux simplexes ayant la numérotation requise).

$ \bullet $Un élément de $ G$ est face d'un et d'un seul simplexe (car il est inclus dans $ \Delta '$).

$ \bullet $Un élément de $ H$ est face d'exactement deux simplexes, car il n'est pas inclus dans $ \Delta '$, et car il n'est pas non plus sur une autre face puisqu'il ne contient pas de sommet numéroté $ n$.

(par simplicité dans la suite et pour alléger les notations je note $ I$ le cardinal $ \vert I\vert$ d'un ensemble $ I$)

$ \bullet $On en déduit $ E+2F=G+2.H$ en comptant le nombre de $ n-1$-faces ayant la propriété $ P$, avec leurs multiplicités (c'est à dire en comptant deux fois les faces communes à deux simplexes).$ \sqcap$$ \sqcup$

$ \bullet $En comptant modulo $ 2$, on en déduit que $ E$ et $ G$ on la même parité.

$ \bullet $Il est clair que $ G$ est "le" $ E$ correspondant à $ \Delta '$.

$ \bullet $Par récurrence sur la dimension, on en déduit donc que $ G$ a toujours la même parité. Or dans le cas de la dimension $ 1$, on constate facilement que ce nombre est impair; on a une alternance de 0 et $ 1$, 0 en premier, $ 1$ à la fin, donc on a changé un nombre impair de fois de 0 à $ 1$ ou de $ 1$ à 0.

$ \bullet $On en déduit donc le résultat tant attendu; $ E$ ne peut être nul puisqu'impair...$ \sqcap$$ \sqcup$

Théorème [Théorème de Brouwer] Soit $ f$ une application continue d'un simplexe $ \Delta$ dans $ \Delta$. Alors $ f$ admet au moins un point fixe.
Démonstration: $ \bullet $On suppose que $ f$ n'a pas de point fixe.

$ \bullet $Soit $ \Delta _i$, pour $ i\in[0,n]$, l'ensemble des $ x \in \Delta$ tels que $ c_i(x)>c_i(f(x))$ (intuitivement $ f$ "éloigne" $ x$ du sommet $ i$ - attention, pas au sens de la distance, mais au sens du poids barycentrique du sommet $ i$; les points les plus "loin" étant les points de la face opposée, le point le plus proche étant le sommet lui-même).

$ \bullet $ $ \Delta = \cup_i \Delta _i$. En effet, soit $ x \in \Delta$.

- Supposons $ c_i(x)\leq c_i(f(x))$ pour tout $ i$.

- $ \sum c_i(x)=\sum c_i(f(x))=1$

- donc $ c_i(x)=c_i(f(x))$ pour tout $ i$

- alors on a $ f$ admettant un point fixe en $ x$.

- c'est une contradiction, donc il existe $ i$ tel que $ c_i(x)>c_i(f(x))$.

$ \bullet $$ x_i$ appartient à $ \Delta _i$ (évident; $ f$ ne peut qu'"éloigner" un point de lui-même, puisque $ f$ n'a pas de point fixe)

$ \bullet $$ x_i$ n'appartient pas à $ \Delta _j$ si $ j\neq i$ (non moins évident; $ x$ est déjà "loin" autant que possible de $ x_j$, puisqu'il appartient à la face opposée)

$ \bullet $Si $ x$ appartient à la face de $ \Delta$ engendrée par les $ x_i$ pour $ i\in I$ pour un certain sous-ensemble $ I$ de $ [0,n]$, alors $ x$ n'appartient pas aux $ \Delta _i$ si $ i\not\in I$ (toujours évident - si $ x$ appartient à la face engendrée par les $ x_i$ pour $ i\in I$, il appartient à la face opposée à $ x_j$ pour tout $ j\not \in I$, et ne peut donc en être éloigné).

$ \bullet $Soit $ T$ une triangulation de $ \Delta$, ayant pour ensemble de sommets l'ensemble $ S$. Soit $ g$ l'application qui à $ s \in S$ associe $ g(s)$ avec $ s \in \Delta _{g(s)}$; on cherche à montrer qu'il s'agit d'une numérotation standard.

$ \bullet $$ g$ est bien définie, puisque l'on a montré que les $ \Delta _i$ recouvraient $ \Delta$.

$ \bullet $le fait que $ g(x_i)=i$ a déjà été prouvé ( $ x_i \in \Delta_i$, $ x_i\not\in \Delta_j$ quand $ j\neq i$).

$ \bullet $soit $ s \in S$, et $ F$ une face minimale de $ \Delta$ contenant $ s$. Il faut montrer que $ g(s)$ est le numéro d'un sommet de $ F$.

$ \bullet $si $ F=\Delta $, le résultat est clair.

$ \bullet $si $ s$ appartient à une face stricte de $ \Delta$, alors $ s$ n'appartient pas aux $ \Delta _j$ pour $ j$ ne désignant pas un numéro de sommet de $ F$ (prouvé un peu plus haut); donc $ g(s)$ est forcément le numéro d'un sommet de $ F$.

$ \bullet $$ g$ est donc bien une numérotation.

$ \bullet $On a montré qu'on pouvait construire des triangulations aussi fines que l'on voulait, au sens où chaque simplexe de la triangulation pouvait être imposé de diamètre inférieur à $ 1/n$. On se donne $ T_n$ une telle triangulation, avec $ g_n$ la numérotation correspondante, donnée par les questions précédentes.

$ \bullet $D'après le lemme de Sperner, il existe un élément de la triangulation $ T$ qui a la propriété $ P$ évoquée plus tôt, c'est à dire qu'il comporte un sommet numéroté $ i$ pour tout $ i$ dans $ [0,n]$.

$ \bullet $On peut considérer alors la suite de sommets numérotés 0 dans des simplexes ayant la propriété $ P$ de la triangulation $ T_n$.

$ \bullet $Puisque l'on est dans un compact métrique, on peut en extraire une sous-suite convergente, par le théorème de Bolzano-Weierstrass (voir théorème [*]). Soit $ x$ la limite.

$ \bullet $$ x$ est aussi la limite des suites de sommets numérotés $ i$ dans des simplexes ayant la propriété $ P$, pour $ i\in[1,n]$, car le diamètre des simplexes tend vers 0.

$ \bullet $Par continuité de $ f$, $ c_i(f(x)) \geq c_i(x)$ pour tout $ i$.

$ \bullet $Or $ \sum_i c_i(x)=\sum_i c_i(f(x))=1$, donc $ c_i(f(x))=c_i(x)$ pour tout $ i$.

$ \bullet $On en déduit alors que $ x=f(x)$. D'où la contradiction...$ \sqcap$$ \sqcup$

Corollaire [Brouwer] Toute application continue d'une boule unité fermée de $ \mathbb{R}^n$ dans elle-même comporte un point fixe.

Démonstration:

En fait il suffit de montrer que la boule unité fermée est homéomorphe à un simplexe. Cela est fait dans la proposition [*].$ \sqcap$$ \sqcup$

Corollaire [Champ rentrant dans la sphère] Soit $ V$ un champ de vecteur continu de la boule unité fermée de $ \mathbb{R}^n$ dans $ \mathbb{R}^n$. Si pour tout $ x$, $ \tilde V(x)= <V(x),x>$ est négatif strictement 1.5, alors $ V$ s'annule au moins en un point de la boule unité.

Démonstration:

$ \bullet $On note $ S$ la sphère unité fermée, et $ C_r$ la couronne constituée par la boule unité fermée privée de la boule ouverte de rayon $ 1-r$.

$ \bullet $On considère pour tout $ \epsilon $ l'application $ f_\epsilon $ de $ \overline B$ (la boule unité fermée) dans $ \mathbb{R}^n$ qui à $ x$ associe $ x+\epsilon .\overrightarrow V(x)$.

$ \bullet $ $ f_\epsilon $ est continu.

$ \bullet $$ \tilde V$ étant continue sur un compact $ \overline B$, on peut lui trouver un majorant à $ {\parallel}V {\parallel}$. Notons $ M$ ce maximum.

$ \bullet $$ V$ étant continue sur un compact $ S$, elle y atteint son maximum, qui est négatif. Notons $ m$ ce maximum; on a $ m<0$.

$ \bullet $En tout point $ x$ de $ S$, on peut centrer une boule ouverte de rayon $ r_x$ sur laquelle $ <x,V(x)>$ est inférieur à $ m/2$. La sphère $ S$ est recouverte par les boules centrées en $ x$ de rayon $ r_x/2$; on peut donc extraire de ce recouvrement un recouvrement fini. Les boules de rayon $ r_x$ recouvrent elle aussi $ S$, et elles recouvrent aussi une couronne $ C_r$ pour un $ r$ assez petit.

$ \bullet $Sur $ C_r$, on a donc $ <x,V(x)>$ inférieur à $ m/2$.

$ \bullet $ $ {\parallel}f_\epsilon (x){\parallel}^2={\parallel}x {\parallel}^2 + \epsilon ^2 {\parallel}V(x) {\parallel}^2 + 2 \epsilon <V(x),x>$.

$ \bullet $Donc $ {\parallel}f_\epsilon (x){\parallel}^2 \leq {\parallel}x {\parallel}^2+\epsilon ^2.M^2 + 2 \epsilon <V(x),x>$

$ \bullet $Sur $ C_r$, on a alors $ {\parallel}f_\epsilon (x){\parallel}^2 \leq {\parallel}x {\parallel}^2+\epsilon ^2.M^2+\epsilon .m$

$ \bullet $Pour $ \epsilon $ suffisamment petit, on a donc $ {\parallel}f_\epsilon (x){\parallel}^2 < {\parallel}x {\parallel}^2$

$ \bullet $Pour $ \epsilon $ suffisamment petit et $ {\parallel}x {\parallel}< 1-r $ on a aussi $ {\parallel}f(x) {\parallel}\leq 1$ (puisque $ V$ est borné).

$ \bullet $On déduit de tout cela que $ f_\epsilon $ pour $ \epsilon $ assez petit est une application de la boule unité fermée dans la boule unité fermée. Par le résultat [*], on en déduit donc que $ f_\epsilon $ admet un point fixe, et que donc $ \tilde V$ s'annule quelque part.$ \sqcap$$ \sqcup$



Notes

... strictement1.5
On dit que le champ est rentrant.

next up previous index
suivant: Index monter: Zoologie de la topologie précédent: Inégalité isodiamétrique   Index
C.Antonini_JF.Quint_P.Borgnat_J.Bérard_E.Lebeau_E.Souche_A.Chateau_O.Teytaud
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page