Carnet de Route du Séminaire de la Détente Mathématique

Une preuve combinatoire du théorème du point fixe de Brouwer

Le 14 mars 2022  - Ecrit par  Léo Dort Voir les commentaires (2)

Voici quelques notes illustrées et colorées prises lors de l’exposé de Caroline Brosse le 14 avril 2021 pour le Séminaire de la Détente Mathématique.

Ne laissons aucune place au suspens, voici le théorème du point fixe de Brouwer.

Théorème de Brouwer (1912) Toute application continue $f$ de la boule unité de $\mathbb{R}^n$ dans elle-même admet un point fixe, i.e. qu’il existe $x$ tel que $f(x)=x$.

Brouwer aurait eu l’idée de ce résultat alors qu’il buvait son café. En mélangeant son sucre, il semble qu’il y ait toujours un point immobile, ou autrement dit lorsque vous mélangez votre café, il y a un point à la surface qui n’aura pas bougé.

Commençons par le cas de la dimension 1. Dans ce cas $f$ est une fonction continue de l’intervalle $[0,1]$ dans lui-même.

Considérons alors la fonction $g:x\in[0,1]\longmapsto f(x)-x$. On a alors $g(0)\geq0$ et $g(1)\leq0$. Ainsi d’après le théorème des valeurs intermédiaires, on en déduit qu’il existe $x$ tel que $g(x)=0$, c’est-à-dire tel que $f(x)=x$. Ce qui termine la démonstration en dimension 1.

Dans le reste de ces notes, nous démontrons le théorème de Brouwer grâce à un bel argument combinatoire : le lemme de Sperner.

Entrons dans le monde fabuleux de la combinatoire

On s’intéresse à un objet très important en combinatoire : un graphe.

Un graphe est la donnée :

  • d’un ensemble de sommets représentant par exemple des individus, et
  • d’un ensemble d’arêtes représentant par exemple les liens d’amitiés entre ces individus.

Pour chaque sommet du graphe, on peut définir son degré, c’est-à-dire son nombre de voisins (ou son nombre d’amis).

Commençons par énoncer une propriété, vraie pour n’importe quel graphe, et qu’on utilisera plus tard.

Propriété : Le nombre de sommets de degré impair est pair.

Exercice : Démontrer la propriété.

Le lemme de Sperner en dimension 1 et 2

Lemme de Sperner (dimension 1) Dans une ligne bicolore, il y a au moins un changement de couleur. Et même, il y en a un nombre impair.

Il s’agit d’une version discrète du théorème des valeurs intermédiaires.
Comme nous avons déjà démontrer le théorème de Brouwer en dimension 1, ajoutons une dimension, et intéressons-nous au cas de la dimension 2.

Une triangulation (dans le plan) est une partition d’un objet en un ensemble de triangles.
Dans la suite nous allons trianguler des triangles.

On va maintenant colorier une triangulation avec 3 couleurs de la manière suivante :

  • chaque sommet externe possède une couleur différente,
  • chaque côté du triangle externe est une ligne bicolore, et
  • les sommets à l’intérieur du triangle externe sont colorés par l’une des 3 couleurs au choix.

Une telle coloration est appelée coloration de Sperner.

On peut maintenant énoncer le lemme de Sperner en dimension 2.

Lemme de Sperner (dimension 2) Soit $T$ un grand triangle, subdivisé, dont la triangulation est munie d’un coloriage de Sperner. Alors il existe un petit triangle dont les trois sommes sont de couleurs différentes.

Démontrons ce joli résultat.

Commençons par ouvrir les arêtes .

Puis construisons un nouveau graphe. Plaçons un sommet dans chaque petit triangle, et un à l’extérieur du grand. Puis on place une arête si on peut relier ces nouveaux sommets grâce à l’une des ouvertures :

Quel peut-être le degré d’un sommet  ?

Toutes les configurations possibles (à permutation des sommets près) sont :

  • sommet est de degré 0
  • sommet est de degré 2
  • sommet est de degré 1

Ainsi les sommets de degré 1 sont exactement les sommets placés à l’intérieur des triangles tricolores . Il suffit donc de trouver un sommet de degré 1 dans notre nouveau graphe pour en déduire le lemme de Sperner.

Mais alors comment faire ?

Partons du sommet extérieur.

Et suivons un chemin dans le graphe.

Plusieurs choses peuvent arriver :

  1. si on arrive dans une impasse, c’est-à-dire que le chemin se termine par un sommet de degré 1, alors c’est gagné !
  2. ou alors on revient au sommet de départ, autrement dit on réalise une boucle.

    Dans ce cas, on essaie un autre chemin jusqu’à en trouver un bon.

    Pourquoi pouvons-nous trouver un tel chemin ?

    Rappelons que les sommets à l’intérieur des petits triangles ont pour degré 0, 1, ou 2.
    Donc tous les sommets d’une boucle (sauf le sommet extérieur) sont de degré 2.

    Puis on a vu que le nombre de changements de couleur dans une ligne bicolore est impair. Donc le degré du sommet extérieur est impair.

    Or on sait que dans un graphe le nombre de sommets de degré impair est pair. Ainsi le sommet extérieur est nécessairement relié à un autre sommet de degré impair, c’est-à-dire un sommet de degré 1.

Ce qui achève la démonstration du lemme de Sperner en dimension 2.

De Sperner à Brouwer en dimension 2

Nous allons maintenant démontrer le théorème de Brouwer en dimension 2. On considère une fonction $f$ du disque unité de $\mathbb{R}^2$ dans lui-même et continue.

Raisonnons par l’absurde, et supposons que $f$ n’a pas de point fixe. En plaçant 3 sommets sur le cercle, on peut voir le cercle comme un triangle.

L’application $f$ est donc maintenant une fonction continue du triangle (plein) $T$ dans lui-même. L’astuce maintenant est de ne pas voir le triangle dans le plan, mais dans l’espace !

En plongeant le triangle dans $\mathbb{R}^3$, $f$ définie sur $T$ et à valeurs dans $T$, est maintenant une fonction de $\mathbb{R}^3$ à valeurs dans $\mathbb{R}^3$.

Puisque nous voulons appliquer le lemme de Sperner, il nous faut donc introduire des triangulations. On construit par itération des triangulations de plus en plus petites grâce au procédé suivant : « un triangle à l’étape $k$ de la construction est raffiné en à l’étape $k+1$ ».

Les premières triangulations sont les suivantes :

Soit $T_k$ la triangulation donnée par la $k$-ième étape de la construction précédente.

On définit alors un coloriage $\lambda$ sur la triangulation $T_k$. Pour $x=(x_1,x_2,x_3)\in T_k$, on pose
\[ \lambda(x) \, = \, \min\left\{ i \in \{1,2,3\} :\, f(x)_i < x_i \right\}. \]
Pour les dessins, on adopte les conventions suivantes :

  • si $\lambda(x)=1$, alors le sommet est coloré en bleu ,
  • si $\lambda(x)=2$, alors le sommet est coloré en vert , et
  • si $\lambda(x)=3$, alors le sommet est coloré en orange .

On affirme alors que $\lambda$ définit une coloration de Sperner pour la triangulation $T_k$.

Exercice : Montrer l’affirmation précédente.

  • Tout d’abord, $\lambda$ est bien définie. En effet, par hypothèse $f(x)\neq x$ pour tout $x\in T_k$, et puisque
    \[ \sum_{i=1}^3 x_i=1 \quad \textrm{ et } \quad \sum_{i=1}^3 f(x)_i =1, \]
    on en déduit qu’il existe un indice $i \in \{ 1,2,3 \}$ tel que $f(x)_i < x_i$.
  • Puis on a $\lambda(e_i)=i$ pour tout $i=1,2,3$. En effet, puisque $f(e_i)\neq e_i$, on a
    \[ f(e_i)_i < 1=(e_i)_i \quad \textrm{ et } \quad (e_i)_j=0\leq f(e_i)_j \textrm{ si } i\neq j. \]
  • Enfin, $\lambda(x)\neq i$ si $x$ est sur le segment opposé à $e_i$. En effet, si $x$ est sur le segment opposé à $e_i$, alors $x_i=0$, et ainsi $x_i\leq f(x)_i$ c’est-à-dire $\lambda(x)\neq i$.

Ce qui montre bien que $\lambda$ est une coloration de Sperner.

On peut donc appliquer le lemme de Sperner. Dans chaque triangulation $T_k$, il existe un petit triangle multicolore, de sommets $v_1^k$ (coloré 1), $v_2^k$ (coloré 2) et $v_3^k$ (coloré 3).

On construit ainsi 3 suites $(v_1^k)_{k\geq0}$, $(v_2^k)_{k\geq0}$ et $(v_3^k)_{k\geq0}$.

Puisque le triangle $T$ est un compact de $\mathbb{R}^3$, on peut extraire 3 sous-suites de $(v_1^k)_{k\geq0}$, $(v_2^k)_{k\geq0}$ et $(v_3^k)_{k\geq0}$ qui convergent simultanément.

Remarquons que ces extractions ont la même limite, notée $v$. En effet, par construction les sommets $v_1^{\varphi(k)}$, $v_2^{\varphi(k)}$ et $v_3^{\varphi(k)}$ sont les sommets d’une suite de triangles de la triangulation $T_{\varphi(k)}$ de plus en plus petits. Ils sont donc de plus en plus proches. Donc si les suites convergent, alors les limites coïncident.

Dans la suite, par abus de notations on ne différencie pas les suites $(v_i^k)_{k\geq0}$ de leur sous-suite $(v_i^{\varphi(k)})_{k\geq0}$.

Mais alors, comment conclure ?

Pour ce faire, essayons de comparer $v$ et $f(v)$. Puisque $f$ est continue sur $T$, et
\[ v = \lim_{k\rightarrow+\infty} v_1^k = \lim_{k\rightarrow+\infty} v_2^k = \lim_{k\rightarrow+\infty} v_3^k, \]
on a
\[ f(v) = \lim_{k\rightarrow+\infty} f(v_1^k) = \lim_{k\rightarrow+\infty} f(v_2^k) = \lim_{k\rightarrow+\infty} f(v_3^k). \]
Mais on a, d’après la définition de la coloration $\lambda$ :
\[ f(v_1^k) < (v_1^k)_1 \quad \textrm{ et } \quad f(v_2^k)_1 \geq (v_2^k)_1. \]
Donc en passant à la limite dans les inégalités précédentes, on obtient :
\[ f(v)_1 \leq v_1 \quad \textrm{ et } \quad f(v)_1 \geq v_1, \]
c’est-à-dire
\[ f(v)_1 = v_1. \]
On montre de la même manière que :
\[ f(v)_2 = v_2 \quad \textrm{ et } \quad f(v)_3 = v_3. \]
On a donc démontré que $f(v)=v$, autrement dit $f$ admet un point fixe. Ce qui est une contradiction avec notre hypothèse de départ, et achève la démonstration.

Et en dimension supérieure ?

En dimension 3, on considère des triangulations sur des tétraèdres,

et des colorations avec des conditions sur les arêtes et les faces.

En dimension $n$ quelconque, on considère des simplexes à $n+1$ sommets, c’est-à-dire l’analogue du triangle à $n$ dimensions.

On définit de la même manière les triangulations d’un simplexe comme une partition en simplexes plus petits de même dimension, et les colorations de Sperner sur ces simplexes.
Puis grâce à un raisonnement par récurrence sur la dimension, on obtient l’énoncé général du lemme de Sperner suivant :

Lemme de Sperner Soit $S$ un simplexe de dimension $n$, subdivisé, dont la triangulation est munie d’un coloriage de Sperner. Alors il existe un petit simplexe de dimension $n$ multicolore.

Et de la même manière qu’en dimension 2, on déduit le théorème de Brouwer du lemme de Sperner.

Quelques applications

Un résultat équivalent au lemme de Sperner et au théorème de Brouwer est le lemme de Knaster-Kuratowski-Mazurkiewicz ou lemme KKM. Il s’écrit en termes de fermés de $\mathbb{R}^n$, mais énonçons-le en dimension 2.

Soit $T=x_1 x_2 x_3$ un triangle. Soient $F_1,F_2,F_3$ trois fermés tels que :

  1. $T\subset F_1\cup F_2\cup F_3$,
  2. $x_i\in F_i$, et
  3. si on note $c_{ij}$ le côté du triangle $x_i x_j$, alors $c_{ij}\subset F_i\cup F_j$.

Alors il existe $x\in F_1\cap F_2 \cap F_3$.

Le théorème du point fixe de Brouwer peut aussi se reformuler en un énoncé de la théorie des jeux !

Connaissez-vous le jeu de Hex ?

Il s’agit d’un jeu ou deux joueurs s’affrontent sur un plateau fait d’hexagones. Le but pour chacun des joueurs bleu et rouge est de relier les bords du plateau (correspondant à sa couleur) en coloriant tour à tour les hexagones.

À la fin des années 1940, John Nash démontra qu’il y a toujours un vainqueur à ce jeu. Ce n’est que bien plus tard qu’un mathématicien du nom de David Gale montra que le théorème du point fixe de Brouwer se déduit du résultat de Nash.

Vous pouvez trouver ici les notes manuscrites de cet exposé au format pdf, et cliquez pour en savoir plus sur le séminaire et la MMI.

Partager cet article

Pour citer cet article :

Léo Dort — «Une preuve combinatoire du théorème du point fixe de Brouwer» — Images des Mathématiques, CNRS, 2022

Commentaire sur l'article

  • Erreur dans la démonstration du théorème de Brouwer

    le 19 mai à 15:43, par Timothée Dantec

    Bonjour, je crois qu’il y a une erreur dans votre démonstration. Pour conclure que la fonction f admet un point fixe on doit montrer que f(v)=v notamment en sa troisième coordonnée.
    On ne peut cependant pas le faire comme pour la première et seconde coordonnée. Pour la première coordonnée, comme détaillé dans le document, on peut faire un théorème des gendarmes entre les suites (v1) et (v2).
    Pour la seconde, on peut faire de même entre les suites (v2) et (v3).
    Cependant pour la troisième coordonnée nous n’avons qu’une seule information sur la suite ce qui nous empêche de faire un encadrement :
    Par construction de (v3) on sait que son image en la troisième coordonnée est inférieur à sa troisième coordonnée, mais c’est tout, car la fonction de coloriage étant définie comme un minimum, la construction des suites (v1) et (v2) par rapport à cette fonction ne nous apprends rien sur les deuxième et troisième coordonnée pour (v1) et sur la troisième coordonnée pour (v2).

    Pour résumer le construction des suites en fonctions d’une fonction de coloriage basée sur un « min » fait que l’on a trois informations sur la première coordonnée de v, deux sur la seconde, mais une seule sur la troisième, empêchant de conclure de la même façon.

    Cordialement.

    Répondre à ce message
    • Erreur dans la démonstration du théorème de Brouwer

      le 19 mai à 15:58, par Timothée Dantec

      En fait il n’y a pas de problème pour conclure, on peut trouver la troisième coordonnée grâce à l’équation du triangle, ce n’est juste pas exactement de la même manière :)

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Carnets de route de la MMI» voir le dossier