• Accueil
  • À propos
  • Accrom\(\alpha\)th en PDF
  • Commanditaires
  • Contact
  • Contributions des lecteurs
  • Sites amis

Logo

Point fixe et coloriage

Par Frédéric Gourdeau
Volume 12.1 - hiver-printemps 2017

Imaginez que vous avez deux cartes du Québec, l’une par-dessus l’autre. Vous prenez celle du dessus que vous déformez en la froissant, tournant, retournant et pliant comme vous voulez, et vous la déposez à nouveau sur l’autre carte, sans qu’elle dépasse. Alors, il y a toujours au moins un point de la carte déformée qui est exactement au-dessus du même point sur la carte du dessous. Surprenant?

Transformation topologique

Lorsque l’on déforme une carte sans la déchirer, la fonction qui décrit la transformation est continue. Intuitivement, on voit que si deux points sont près l’un de l’autre sur la carte initiale, alors ils sont toujours près l’un de l’autre après la déformation de la carte. Si la carte est imprimée sur une surface malléable que l’on peut étirer (comme un tissu élastique) ou même contracter (comme une mince couche de pâte à modeler), et que l’on permet en plus d’étirer ou de contracter certaines parties de la carte, la transformation est toujours continue: il s’agit d’une transformation topologique.

Lorsque l’on dépose la carte déformée sur la carte initiale, sans qu’elle dépasse, alors il y a toujours au moins un point de la carte déformée qui est exactement au-dessus du même point sur la carte du dessous. Ce résultat est un exemple d’application du Théorème du point fixe de Brouwer, lequel a de nombreuses applications. (Voir l’encadré Un résultat aux multiples ramifications.)

Point fixe d’une fonction

Point fixe d’une fonction
Pour une fonction f d’un ensemble E vers lui-même, un point P est fixe si f(P) = P.

Dans l’exemple de la carte du Québec, où chaque point de la carte déformée se trouve au-dessus d’un point P’ de la carte du dessous,la fonction f est définie par f(P)=P’. Le fait que les déformations permises de la carte donnent une fonction f continue est essentiel. Si on déchire la carte, le résultat ne tient plus.

Fig.PointFixe13Si le domaine n’est pas borné, une fonction, même continue, n’a pas nécessairement de point fixe. Par exemple, la fonction \(f (x) = x^2 + 1/4\) définie sur les nombres réels possède un point fixe \((x = 1/2,\) car \(f (1/2) = 1/2)\) alors que la fonction \(f (x) = x^2 + 1\) n’en a pas (toujours sur les nombres réels).

Pour garantir l’existence d’un point fixe, le théorème de Brouwer demande que la fonction continue soit définie sur un domaine borné et qui inclut sa frontière. Mais il doit aussi être sans trou. Par exemple, la rotation d’un quart de tour d’un anneau est une transformation continue qui n’a pas de point fixe.

Fig.PointFixe14

Théorème du point fixe de Brouwer (dans le plan)
Soit E une région bornée du plan, délimitée par une courbe comme un cercle où un polygone, qui inclut sa frontière et n’ayant pas de trou. Alors toute fonction continue \(f: E \to E\) possède au moins un point fixe P.

Un résultat aux multiples ramifications

Le Théorème de Brouwer a de nombreuses applications, dans des domaines variés. On peut l’utiliser pour démontrer un résultat sur les matrices (le théorème de Perron-Frobenius) qui est au cœur de l’algorithme Pagerank utilisé par Google. Il est aussi utile pour démontrer le Théorème de Jordan, un résultat topologique fondamental, dont l’énoncé semble à ce point évident que l’on peut se demander ce qu’il y a à prouver. Dans sa formulation naïve, le Théorème de Jordan dit qu’une courbe fermée simple dans le plan le divise en deux parties dont cette courbe est la frontière, et que l’une de ces parties est bornée et l’autre pas. Pour être précis, il faut définir correctement ce qu’est une courbe fermée simple: la continuité joue ici un rôle, et l’intuition initiale qui rendait le résultat évident ne permet pas de démontrer le théorème facilement.

En généralisant le résultat de Brouwer, Kakutani a obtenu le théorème de point fixe qui porte son nom, et dont John Forbes Nash Jr a fait usage pour ses travaux portant sur ce que l’on appelle maintenant l’équilibre de Nash. Rappelons que Nash, qui a obtenu le Prix Nobel d’économie en 1994, est le mathématicien dont la biographie a été adaptée pour produire le film Un homme d’exception.

Démontrer un tel résultat n’est pas évident car on connaît très peu de choses sur la transformation de la carte: froisser, plier, retourner, ce n’est pas très bien défini mathématiquement, enfin, pas dans le sens habituel. Où sont les coordonnées? Où est la formule? L’important ici n’est pas que la fonction nous soit donnée sous une forme particulière mais bien qu’elle soit continue: par exemple, on ne peut permettre de déchirer la carte, car à ce moment le résultat n’est plus vrai.

Tout cela est bien beau, mais comment alors prouver le Théorème du point fixe de Brouwer?

Triangle et point fixe

Pour prouver le Théorème du point fixe dans le plan, il suffit de le démontrer dans le cas où E est la région formée par un triangle et son intérieur. On peut en effet transformer de manière continue en un triangle une région qui respecte les conditions énoncées dans le Théorème de Brouwer, et ainsi se ramener à une fonction continue f du triangle ABC vers lui-même. (Voir l’encadré Un triangle suffit.) On veut donc montrer qu’une fonction continue f d’un triangle dans lui-même possède un point fixe, c’est-à-dire un point P tel que f(P) = P.

Un triangle suffit

Fig.PointFixe09

Si on a une région plane E dont la frontière est une courbe qui est suffisamment régulière, alors on peut la déformer de manière continue pour obtenir un triangle T. Plus précisément, il existe une fonction continue \(g: T \to E\) dont l’inverse \(g^{-1}: E \to T\) est aussi une fonction continue, tel que montré sur le diagramme ci-contre.

Pour montrer que \(f: E \to E\) possède un point fixe, il suffit alors de considérer la fonction \(F = g^{-1}\circ f\circ g,\) qui va de T vers T. Si on trouve un point P tel que \(F(P) = P\), alors on a que \(Q = g(P)\) est un point fixe de f. En effet comme \(F = g^{-1}\circ f\circ g\) alors \(g\circ F = f\circ g\) et donc:

\[g(P) = (g\circ F)(P) = (f\circ g)(P) = f(g(P)).\]

Fig.PointFixe10

 

Coloriage et point fixe

En mathématiques, on s’intéresse depuis longtemps aux problèmes de coloriage. Cela peut paraître surprenant, et ce qui peut l’être encore plus, c’est que c’est utile! Le Lemme de Sperner en est un magnifique exemple. Il décrit des conditions qui garantissent l’existence d’un triangle ayant ses trois sommets de couleurs différentes, et nous allons voir comment l’utiliser pour prouver l’existence d’un point fixe pour toute fonction continue d’un triangle vers lui-même. Mais avant de l’utiliser, encore faut-il l’énoncer correctement.

Le Lemme de Sperner

Fig.PointFixe01On divise un triangle ABC en plusieurs petits triangles tel que sur le dessin ci-contre. (On a ce qu’on appelle une triangulation du triangle.) On colore A en rouge, B en bleu et C en jaune, et chacun des autres sommets en jaune, bleu ou rouge, avec la seule condition que les sommets sur le côté AC sont jaunes ou rouges, ceux sur le côté BC sont jaunes ou bleus, et ceux sur le côté AB sont rouges ou bleus. Les sommets intérieurs sont jaunes, bleus ou rouges, sans autre condition.

Le Lemme de Sperner affirme qu’il existe au moins un petit triangle qui a ses trois sommets de couleurs différentes: on le dira tricoloré. Sur la figure, le petit triangle bleu est tricoloré.

Trouver un triangle tricoloré

Fig.PointFixe02Lorsqu’il y a peu de triangles, on pourrait espérer trouver un argument qui permette de traiter tous les cas pour montrer qu’il existe au moins un triangle tricoloré. Mais que faire si on a plusieurs triangles? Pourriez-vous traiter tous les cas de coloriage de ce triangle? Et que dire si on a des millions de petits triangles?

La preuve du Lemme de Sperner utilise un joli argument de parité (voir l’encadré).

Balade dans la maison triangulaire

Pour montrer qu’il existe toujours au moins un triangle tricoloré, on considère que le triangle ABC est une maison, que chacun des petits triangles est une pièce dont les côtés sont les murs, et que tout segment reliant un sommet rouge et un sommet jaune est un mur ayant une porte.

Fig.PointFixe03On considère alors les pièces que l’on peut visiter en entrant dans la maison, sans revenir sur ses pas et sans passer deux fois par la même porte.

Chaque chemin possible débutant à l’extérieur doit passer par une porte pour rentrer dans la maison: on peut continuer le chemin et sortir de la pièce par une autre porte lorsque le triangle est coloré rouge – jaune – rouge; sinon, le chemin se termine et on est alors dans un triangle qui est tricoloré. Donc chaque chemin qui se termine à l’intérieur de la maison doit se terminer dans un triangle tricoloré.

Mais attention!, un chemin qui débute à l’extérieur peut ressortir de la maison en empruntant ainsi deux portes extérieures.

Comment alors montrer qu’il y a au moins un chemin qui se termine à l’intérieur de la maison?

Pair ou impair

Fig.PointFixe04On peut voir qu’il y a toujours un nombre impair de portes extérieures. En effet, comme le mur AC débute avec un sommet rouge A et termine avec un sommet jaune C, il y a un nombre impair de changements de couleurs entre des sommets consécutifs: s’il y en avait un nombre pair, les sommets A et C seraient de la même couleur.

Un chemin qui débute et se termine à l’extérieur emprunte deux portes extérieures. Puisque aucune pièce n’a trois portes, on ne peut avoir deux chemins différents qui passent par une même pièce: il n’y a jamais de choix. Comme il y a un nombre impair de portes extérieures, au moins un des chemins qui débute à l’extérieur doit se terminer dans une pièce intérieure – et on a gagné, car cette pièce doit être un triangle tricoloré!

Un coloriage à la Sperner

Pour prouver l’existence d’un point fixe pour toute fonction continue d’un triangle vers lui-même en utilisant le Lemme de Sperner, on veut un coloriage des points du triangle qui respecte les conditions du lemme tout en étant relié au comportement de la fonction f. Il y a plusieurs choix possibles, dont celui donné par l’algorithme suivant. (Voir les coordonnées barycentriques pour une définition plus rigoureuse.)

  • Fig.PointFixe05On colore les sommets: A en rouge, B en bleu et C en jaune.
  • Si f(X) se retrouve dans la région en rouge, on dit que f(X) s’éloigne A de A et on colore X en rouge (comme A). (La région ne contient pas le côté contenant X.)
  • Si f(X) ne s’éloigne pas de A et qu’il s’éloigne de B (i.e. f(X) est strictement à gauche de la parallèle à AC par le point X), alors on colore X en bleu (comme B): f(X) sera en fait dans la région en bleu sur la figure.
  • Si f(X) ne s’éloigne ni de A, ni de B, et qu’il s’éloigne de C, alors on le colore en jaune: il sera dans la région en jaune.

Si il y a un point X qui ne peut être coloré, c’est qu’il est fixe car il ne s’éloigne ni de A, ni de B, ni de C. Dans la suite, on supposera que les sommets des petits triangles considérés sont colorés: si un sommet ne peut être coloré, alors on a déjà un point fixe.

Notons que pour un point X sur le côté AB, il n’y a pas de région jaune et X est donc rouge ou bleu; de même, un point sur le côté AC est rouge ou jaune, et un point du côté BC est bleu ou jaune. Le coloriage respecte donc bien les conditions du Lemme de Sperner.

Coordonnées barycentriques

Pour un point X dans un triangle, on considère que les trois régions colorées représentent les points qui sont plus loin de A, plus loin de B et plus loin de C.

Fig.PointFixe06

Fig.PointFixe07

Fig.PointFixe08

On peut définir précisément ces régions en utilisant les coordonnées barycentriques. Si on place le triangle dans un plan cartésien, on peut vérifier que tout point X du triangle peut être exprimé sous la forme

\[X = \alpha_1 A + \alpha_2 B + \alpha_3 C,\]

où les \(\alpha_i, = 1, 2, 3,\) sont positifs et de somme 1, ce que l’on note \(X(\alpha_1, \alpha_2, \alpha_3).\) Alors, un point \(Y(\beta_1, \beta_2, \beta_3)\) du triangle est dans la première région si \(\beta_1 < \alpha_1,\) dans la deuxième si \(\beta_2 < \alpha_2\) et dans la troisième si \(\beta_3 < \alpha_3\).

Pour définir le coloriage des points, on considère les coordonnées barycentriques de \(f(X) = X’ \alpha’_1, \alpha’_2, \alpha’_3)\). On colore \(X\) en rouge si \(\alpha’_1 < \alpha_1\). Si ce n’est pas le cas, (ce qui revient à dire que \(\alpha’_1 ≥ \alpha_1)\), alors on colore \(X\) en bleu si \(\alpha’_2 < \alpha_2.\) Si \(X\) n’est ni rouge ni bleu (ce qui revient à dire que \(\alpha’_1 ≥ \alpha_1\) et \(\alpha’_2 ≥ \alpha_2),\) alors on colore \(X\) en jaune si \(\alpha’_3 < \alpha_3.\) Autrement, on doit avoir \(\alpha’_i = \alpha_i \) pour \(i=1,2,3,\) ce qui implique que \(X=f(X)\) est un point fixe.

spernerEmanuel Sperner 1905-1980

Emanuel Sperner était un mathématicien allemand, né à Waltdorf près de Neisse. Cette ville fait maintenant partie de la Pologne et porte le nom polonais de Nysa. Sperner a étudié au Carolinum Gymnasium de Neisse et est entré à l’Université de Fribourg en 1925. À l’époque, les étudiants avaient l’habitude de fréquenter plusieurs universités et, après deux semestres, Sperner s’est inscrit à l’Université de Hambourg.

Il y a reçu son doctorat en 1928. C’est dans sa thèse qu’il a présenté l’important résultat appelé maintenant Lemme de Sperner.

Un triangle multicolore

Chacun des points du triangle a ainsi été coloré en jaune, bleu ou rouge, tout en respectant les conditions du Lemme de Sperner. Alors, pour toute triangulation du triangle en petits triangles, il existe un petit triangle qui est tricoloré: si le triangle est très petit, ses sommets jaune, bleu et rouge sont très près les uns des autres.

Une infinité de triangles tricolorés, de plus en plus petits

On considère des triangulations avec des triangles de plus en plus petits (disons que l’on diminue la longueur des côtés des petits triangles par 2 à chaque étape), et pour chaque triangulation, on considère un des petits triangles tricolorés dont l’existence est garantie par le Lemme de Sperner. On a donc une infinité de triangles tricolorés, de plus en plus petits.

Une infinité de sommets rouges
point-fixe-1Considérons la suite des sommets rouges de ces petits triangles tricolorés, et divisons le triangle initial en 10 régions: il y a forcément au moins une de ces régions qui contient une infinité de points rouges. Divisons cette région en 10 régions plus petites: il y en a encore forcément une qui contient une infinité de points rouges. Et ainsi de suite. En subdivisant toujours ainsi, on peut voir qu’il y a une infinité de points rouges dans une région aussi petite que l’on veut. À la limite, les régions ainsi obtenues tendent vers un point: ce point est donc la limite de points rouges.

Un point que l’on ne peut colorer

Le point est la limite de points rouges. Mais comme ces points rouges sont les sommets de triangles tricolorés de plus en plus petits, les autres sommets de ces triangles se rapprochent aussi de P qui est donc la limite de points rouges, de points bleus et de points jaunes.

Peut-on le colorer? En fait, selon la définition de coloriage donnée plus tôt, le point ne pourra être coloré (voir encadré), et il est donc fixe, ce qui démontre le Théorème du point fixe de Brouwer.

Un point fixe dans \(\mathbb{R}^n\)

Le résultat de point fixe que nous avons montré a des formulations plus générales. Il demeure vrai si on a une fonction \(f: E \to E\) où \(E\) est une région bornée et suffisamment régulière dans l’espace, sans trou et incluant sa frontière, telle une sphère ou un polyèdre, et aussi pour des régions aux propriétés analogues dans \(\mathbb{R}^n\) pour \(n ≥ 4.\)

Le Lemme de Sperner est aussi vrai pour l’analogue des triangles dans \(\mathbb{R}^n\), soit les tétraèdres dans \(\mathbb{R}^3\) et les simplexes en général dans \(\mathbb{R}^n\).

L’utilité du Lemme de Sperner montre bien que le coloriage a sa place en mathématiques, et illustre que les mathématiques discrètes peuvent être utiles dans d’autres domaines.

Le point fixe: un point limite

Fig.PointFixe11Si on a une suite de points rouges Rk qui tend vers un point P du triangle, que peut-on dire de P? Comme la fonction est continue et que f(Rk) s’éloigne de A, alors f(P) ne peut pas se rapprocher de A.

Si une suite de points bleus Bk tend vers ce même point P, alors f(P) ne peut pas se rapprocher de B. Et si en plus une suite de points jaunes Jk tend vers P, alors f(P) ne peut pas s’approcher de C.

Donc, si trois suites Jk, Bk et Rk tendent vers un même point P, alors P est fixe, car f(P) n’est plus près ni de A, ni de B, ni de C.

On peut formuler cet argument de manière plus rigoureuse, en utilisant les coordonnées barycentriques.

Un résultat évident en 1D

fixe-grapheSi au lieu de considérer une carte comme représentant une surface en 2D, on considère une ficelle comme représentant un segment, alors il est simple de montrer que l’on a un point fixe. Sur la figure, en allant d’une extrémité à l’autre de la ficelle et de la même ficelle repliée, on passe par toutes les couleurs. Deux points de même couleur seront forcément superposés car à l’extrême gauche, le point de la ficelle du dessous est à gauche du même point sur la ficelle repliée, et à l’extrême droite, le point de la ficelle du dessous est à droite du même point sur la ficelle repliée.

Une représentation graphique le montre aussi. En effet, le graphe d’une fonction continue \(f: [0, 1] \to [0, 1]\) doit couper la droite \(y = x\) en au moins un point dont les coordonnées sont alors égales: soit ce point de coordonnées \((a, a).\) Alors \(f(a) = a\) et \(a\) est donc un point fixe de \(f.\)

Credit : http://mathforum.org/mathimages/index.php/Image:Strings1.jpg

Credit : http://mathforum.org/mathimages/index.php/Image:Strings1.jpg

PDF« >PDF

  • ● Version PDF
Partagez
  • tweet

Tags: Construction des mathématiques

Articles récents

  • Statistique et santé publique

    André Ross
  • Modéliser le réchauffement climatique

    France Caron
  • Partage équitable bis

    Christiane Rousseau

Sur le même sujet

  • Une somme qui sème la controverse

    Frédéric Gourdeau
  • Les coniques, une grande famille

    Christiane Rousseau
  • Élargir pour simplifier

    Christiane Rousseau

Volumes

  • Journée internationale des mathématiques: Accromath multilingue
  • Volume 16.1 – hiver-printemps 2021
  • Volume 15.2 – été-automne 2020
  • Thème spécial: Les mathématiques sont partout
  • Volume 15.1 – hiver-printemps 2020
  • Volume 14.2 – été-automne 2019
  • Volume 14.1 – hiver-printemps 2019
  • Volume 13.2 – été-automne 2018
  • Volume 13.1 – hiver-printemps 2018
  • Volume 12.2 – été-automne 2017
  • Volume 12.1 – hiver-printemps 2017
  • Volume 11.2 – été-automne 2016
  • Volume 11.1 – hiver-printemps 2016
  • Volume 10.2 – été-automne 2015
  • Volume 10.1 – hiver-printemps 2015
  • Volume 9.2 – été-automne 2014
  • Volume 9.1 – hiver-printemps 2014
  • Volume 8.2 – été-automne 2013
  • Volume 8.1 – hiver-printemps 2013
  • Volume 7.2 – été-automne 2012
  • Volume 7.1 – hiver-printemps 2012
  • Volume 6.2 – été-automne 2011
  • Volume 6.1 – hiver-printemps 2011
  • Volume 5.2 – été-automne 2010
  • Volume 5.1 – hiver-printemps 2010
  • Volume 4.2 – été-automne 2009
  • Volume 4.1 – hiver-printemps 2009
  • Volume 3.2 – été-automne 2008
  • Volume 3.1 – hiver-printemps 2008
  • Volume 2.2 – été-automne 2007
  • Volume 2.1 – hiver-printemps 2007
  • Volume 1 – été-automne 2006
  • Article vedette

    Auteurs

    • Michel Adès
    • Antoine Allard
    • Jean Aubin
    • Marie Beaulieu
    • Rosalie Bélanger-Rioux
    • Claude Bélisle
    • Marc Bergeron
    • Pierre Bernier
    • André Boileau
    • Véronique Boutet
    • Pietro-Luciano Buono
    • Massimo Caccia
    • Jérôme Camiré-Bernier
    • France Caron
    • Philippe Carphin
    • Kévin Cazelles
    • Laurent Charlin
    • Pierre Chastenay
    • Jocelyn Dagenais
    • Marie-France Dallaire
    • Jean-Lou de Carufel
    • Jean-Marie De Koninck
    • Lambert De Monte
    • Jean-Paul Delahaye
    • Marc-André Desautels
    • Florin Diacu
    • Jimmy Dillies
    • Nicolas Doyon
    • Philippe Drobinski
    • Hugo Drouin-Vaillancourt
    • Louis J. Dubé
    • Thierry Duchesne
    • Stéphane Durand
    • Thomas Erneux
    • Philippe Etchécopar
    • Charles Fleurent
    • Jérôme Fortier
    • Marlène Frigon
    • Jean-François Gagnon
    • André Garon
    • Christian Genest
    • Denis Gilbert
    • Jonathan Godin
    • Frédéric Gourdeau
    • Samuel Goyette
    • Jean Guérin
    • Hervé Guillard
    • Abba B. Gumel
    • James A. Hanley
    • Alain Hertz
    • Bernard R. Hodgson
    • Isabelle Jalliffier-Verne
    • Guillaume Jouvet
    • Tomasz Kaczynski
    • Patrick Labelle
    • Marc Laforest
    • Josiane Lajoie
    • Alexis Langlois-Rémillard
    • René Laprise
    • Steffen Lauritzen
    • Denis Lavigne
    • Adrien Lessard
    • Jean Meunier
    • Normand Mousseau
    • Johanna G. Nešlehová
    • Pierre-André Noël
    • Dmitry Novikov
    • Ostap Okhrin
    • Laurent Pelletier
    • Jean-François Plante
    • Annie Claude Prud'Homme
    • Benoît Rittaud
    • Louis-Paul Rivest
    • Serge Robert
    • André Ross
    • Christiane Rousseau
    • Guillaume Roy-Fortin
    • Yvan Saint-Aubin
    • Maria Vittoria Salvetti
    • Vasilisa Shramchenko
    • Robert Smith?
    • William Verreault
    • Redouane Zazoun

Sujets

Algèbre Applications Applications des mathématiques Changements climatiques Chaos Construction des mathématiques COVID-19 Cristallographie cryptographie Dimension 4 Fractales GPS Gravité Géométrie Histoire des mathématiques Imagerie Infini Informatique Informatique théorique Jeux mathématiques Logique mathématique Lumière Mathématiques de la planète Terre Mathématiques et architecture Mathématiques et arts Mathématiques et astronomie Mathématiques et biologie Mathématiques et développement durable Mathématiques et littérature Mathématiques et médecine Mathématiques et physique Mathématiques et transport Miroirs Nombres Pavages Portrait d'un mathématicien Portrait d'un physicien Probabilités Probabilités et statistique Racines Rubrique des Paradoxes Section problèmes Théorie des noeuds Éditorial Épidémiologie

© 2021 Accromath