À propos du nombre d’Erdös

Le « nombre d’Erdös » est une sorte de distraction ¹Si vous n’êtes pas vous-même mathématicien, ou si vous n’avez jamais vraiment fréquenté ces personnes, vous serez peut-être surpris, au moins dans un premier temps, de la nature des jeux (ou des blagues d’ailleurs) qui les amusent. de la communauté mathématique. Le principe est d’attribuer à chaque mathématicien un nombre entier selon les règles suivantes :

• on commence par attribuer à Paul Erdös ²Page Wikipédia sur Paul Erdös (qui est bien sûr celui qui a donné son nom au concept) le nombre d’Erdös 0 ;
• on attribue le nombre d’Erdös 1 à tout mathématicien ayant cosigné un article avec Paul Erdös ;
• on attribue le nombre d’Erdös 2 à tout mathématicien (n’ayant pas encore de nombre d’Erdös et) ayant cosigné un article avec un mathématicien ayant 1 pour nombre d’Erdös ;
• on attribue le nombre d’Erdös 3 à tout mathématicien (n’ayant pas encore de nombre d’Erdös et) ayant cosigné un article avec un mathématicien ayant 2 pour nombre d’Erdös ;
• et ainsi de suite.

Remarquez qu’il est possible que certains mathématiciens ne soient pas atteints par le procédé que l’on vient de décrire. C’est par exemple évidemment le cas de quelqu’un qui n’a jamais publié d’article en collaboration. On convient qu’une telle personne a un nombre d’Erdös infini.

Une autre façon de comprendre le nombre d’Erdös est de faire intervenir un graphe. Précisément, on dessine sur une feuille de papier un point représentant chaque mathématicien, et on relie deux points dès lors que les mathématiciens correspondant ont publié un article en commun. Le nombre d’Erdös d’un mathématicien est alors la longueur du plus court chemin le reliant à Paul Erdös. S’il n’existe aucun tel chemin, le nombre d’Erdös est infini. Il faut comprendre que calculer précisément son nombre d’Erdös est souvent une tâche difficile : autant il n’est pas forcément très dur d’en trouver un majorant (il suffit pour cela de trouver une suite de mathématiciens nous reliant à Paul Erdös), autant il est beaucoup plus délicat d’être certain qu’il n’existe aucun chemin plus court !

Je me suis amusé récemment à estimer mon nombre d’Erdös. Je suis sûr que vous serez ravis d’apprendre ³Par exemple, si vous avez publié un article avec moi (je m’adresse donc ici à un nombre très réduit de personnes), votre nombre d’Erdös est au plus 5. qu’il est plus petit que 4 : j’ai publié un article avec David Savitt, qui a lui-même publié avec Jérémy Martin, qui a lui-même publié avec John Conway, qui a lui-même publié avec Paul Erdös. En fait, je pense même qu’il est exactement égal à 4, mais je n’en ai pas la preuve ! Enfin, peu importe.

Tout cela ne pourrait sembler être qu’un jeu idiot qui ne mérite pas vraiment que l’on s’y attarde, mais j’ai choisi d’en parler car il illustre un phénomène qui peut paraître un peu surprenant lorsqu’on l’entend pour la première fois. Le fait est que les nombres d’Erdös des mathématiciens sont en général très petits (si l’on excepte l’infini, s’entend) : le plus grand connu en 1998 était 7 selon Wikipédia. Autrement dit, le tissu des collaborations permet de relier très rapidement deux mathématiciens d’origine très différente et travaillant sur des sujets qui n’ont a priori rien à voir.

Ce même phénomène se manifeste dans bien d’autres situations de la vie de tous les jours (pour des gens n’ayant aucun rapport avec les mathématiques, je veux dire). Par exemple, je peux définir le nombre de Caruso comme suit :

• je m’octroie 0 comme nombre de Caruso ;
• j’octroie 1 comme nombre de Caruso à toutes les personnes qui me connaissent directement ⁴La relation de connaissance n’est peut-être pas très bien définie. Si cela vous trouble, vous pouvez remplacer « connaître » par « avoir déjà discuté avec » ;
• j’octroie 2 comme nombre de Caruso à toutes les personnes (qui n’en ont pas encore et) qui connaissent une personne de nombre de Caruso égal à 1 ;
• et ainsi de suite.

Déjà, il ne semble pas très difficile de se convaincre que toute personne ayant un contact quelconque avec notre civilisation ⁵Je veux dire que j’exclus par là certaines éventuelles tribus vivant (par exemple) dans la jungle amazonienne, dont on ne connaîtrait pas l’existence. a un nombre de Caruso fini. En réalité, il existe un certain adage (je ne sais pas à quel point il a été vérifié scrupuleusement) qui affirme que le nombre de Caruso de tous ces gens est au plus 6 (si vous trouvez que c’est vraiment petit, remplacez-le par 15, et là il est certain que l’adage est vrai !). Par exemple, je devrais connaître en moins de six intermédiaires n’importe quel paysan chinois. Et, en réalité, en y réfléchissant un peu, ce n’est pas du tout absurde. Par exemple, étant donné que je m’implique un peu dans certaines activités mathématiques, je connais des personnes proches du ministère de l’éducation nationale ; il y a ensuite fort à parier que ces gens connaissent notre actuel président de la République (peut-être via un intermédiaire supplémentaire, mais sans doute directement) ; celui-ci connaît à son tour son homologue chinois ; ensuite, je dois avouer que cela est plus flou dans mon esprit, car je ne suis pas très au courant de la vie des paysans chinois, cela dit, on peut penser qu’ils fréquentent les marchés et donc connaissent des notables de la ville la plus proche ; certains de ces derniers ont probablement des intérêts politiques qui les relient à leur président en peu d’étapes. En fait, je voulais présenter un trajet relativement classique (consistant à passer par des personnes dont le rayonnement géographique est vaste), mais il y en aurait sans doute des plus efficaces puisque je connais déjà personnellement des personnes d’origine chinoise ! Dans tous les cas, on se rend donc compte sur cet exemple que la borne de 6 n’est pas déraisonnable (et qu’en tout cas, celle de 15 est très large).

Un autre exemple est celui d’Internet. En réalité, il est assez similaire à celui que je viens de détailler, la différence essentielle est que les êtres humains sont remplacés par des ordinateurs. En effet, Internet n’est rien d’autre que la possibilité offerte aux ordinateurs de communiquer entre eux. Bien entendu, de la même façon que personne ne connaît directement tous les habitants de la planète, aucun ordinateur n’est en mesure de discuter directement avec tous les autres. Par contre, chacun a un petit cercle d’« amis » avec qui il a la possibilité d’échanger des informations. Comment cela fonctionne-t-il en pratique ? Prenons un exemple simple : supposons que je veuille consulter, depuis mon ordinateur personnel (qui répond au doux nom de boumbo.toonywood.org, ou boumbo pour les intimes), le site d’« Images des Mathématiques ». En pratique, je lance mon navigateur préféré, je tape l’URL du site (à savoir http://images-archive.math.cnrs.fr/) dans la barre de navigation, et j’attends le téléchargement. En fait, pour avoir accès à l’information, boumbo va devoir la demander à l’un de ses confrères, que l’on appelle généralement l’hébergeur du site. Cet hébergeur a lui aussi un nom qui est en fait précisé dans l’adresse que j’ai tapée : exactement, il s’agit de la partie qu’il y entre http:// et le / suivant : dans notre cas, le nom de l’ordinateur que boumbo doit contacter est donc images-archive.math.cnrs.fr. Mais bien sûr boumbo n’a pas un cercle d’amis très développé (essentiellement, il ne sait discuter qu’avec son fournisseur d’accès), et en particulier, il ne connaît pas (ou du moins ne sait pas communiquer directement avec) images-archive.math.cnrs.fr. Malgré tout, il s’en sort de la façon suivante : il commence par faire la liste de tous ses interlocuteurs et en choisit un parmi eux qu’il juge plus à même de joindre le destinataire (selon des critères, en général, très rudimentaires). Il contacte ensuite l’ordinateur selectionné et lui demande de relayer la conversation. Si ce premier intermédiaire a la possibilité de discuter directement avec images-archive.math.cnrs.fr, il peut établir la communication, sinon il adopte à son tour la même stratégie en contactant un autre de ses amis qu’il juge plus à même d’atteindre l’objectif. En pratique, il y a souvent plusieurs intermédiaires, mais ce qui est remarquable, c’est que leur nombre n’est jamais très grand (souvent de l’ordre d’une dizaine). C’est cette dernière constatation qui d’une part fait qu’Internet marche bien, et d’autre part est une nouvelle illustration du phénomène que l’on souhaite décrire (en particulier, c’est l’exact analogue de ce qui a été expliqué dans l’alinéa précédent au sujet des réseaux de connaissance d’êtres humains). Pour conclure ce paragraphe, j’aimerais dire qu’il existe la commande traceroute sous Linux qui permet d’afficher la liste des intermédiaires nécessaires à contacter un hôte distant. Dans le cas de images-archive.math.cnrs.fr, on s’aperçoit que l’on a du faire appel à onze intermédiaires ⁶Dans l’ordre : rbx-7-m2.routers.ovh.net, rbx-2-6k.routers.ovh.net,
160g.th2-1-6k.routers.ovh.net,
Renater.sfinx.tm.fr, te4-2-rouen-rtr-021.cssi.renater.fr,
te4-2-rouen-rtr-021.cssi.renater.fr,
193.51.189.53, te1-2-nantes-rtr-021.cssi.renater.fr,
or-angers-nantes.cssi.renater.fr,
ua-alp.net.univ-angers.fr et finalement bonnezeaux.math.univ-angers.fr..

Il y aurait bien d’autres manifestations du phénomène décrit (par exemple basée sur le réseau du métro parisien, ou plus généralement le réseau ferroviaire), mais je pense qu’il est raisonnable de s’arrêter là au niveau des illustrations. J’aimerais malgré tout conclure par une analyse très minimaliste de la situation. En fait, en étudiant les exemples précédents, on se rend compte que ce qui fait marcher l’affaire est l’existence de nœuds au rayonnement très vaste et/ou très diversifié : pour les connaissances entre êtres humains, il s’agit typiquement des chefs d’états ou des stars internationales ; pour les ordinateurs, il s’agit des fournisseurs d’accès ; pour le métro parisien, il s’agit des grandes stations comme Châtelet les Halles ; pour le réseau ferroviaire finalement, ce sont les grandes gares parisiennes. Souvent, donc, pour relier deux points quelconques, le plus simple est de passer par ces grands pôles. Cela fournit en réalité même une méthode si l’on n’a pas une connaissance « a priori » du réseau complet : il suffit en fait de connaître le réseau autour du point où l’on se situe et les grands pôles ! Par exemple, en ce qui concerne le réseau ferroviaire, on peut se dire que si la ville que l’on cherche à atteindre fait partie du réseau TER local, on y va directement, et si ce n’est pas le cas, on passe par Paris et on demandera conseil là-bas. Bien entendu, si l’on veut rejoindre un patelin perdu, il serait peut-être bon de savoir en outre dans quelle région, voire dans quel département, il se situe. Mais on n’a en tout cas pas besoin d’avoir une connaissance globale de toutes les voies ferrées de France ! La même remarque s’applique lorsqu’il s’agissait de me relier par une suite de connaissances à un quelconque paysan chinois : même si je ne connais strictement rien à la structure du tissu social chinois, et simplement en sachant que je dois aboutir en Chine, je commence par me diriger vers ces grands pôles, incarnés ici par des personnes qui sont susceptibles d’avoir des contacts avec le pays (par exemple les chefs d’état, ou des amis mathématiciens d’origine chinoise), charge ensuite à eux de se débrouiller pour atteindre la personne qui m’intéresse. Pour Internet, comme je l’ai déjà expliqué, c’est exactement la méthode appliquée, et le fait est qu’un ordinateur personnel a simplement besoin de connaître le nom de son fournisseur d’accès pour pouvoir accéder à l’information mise à disposition sur toute la planète.

Une dernière chose que l’on peut souligner est l’importance de l’existence des pôles précédents à diverses échelles. En effet, si l’on reprend l’exemple des connaissances entre êtres humains, il est bien beau de vouloir systématiquement passer par les chefs d’État, mais il est clair que notre président actuel ne connaît pas personnellement toute la population française ! On a donc également besoin de pôles intermédiaires au niveau régional, départemental, communal, et même familial. Le même motif apparaît lorsque l’on regarde un plan de chemin de fer : il y a certes les grandes gares parisiennes auxquelles concourent les lignes TGV, mais il y a aussi les capitales de région et les chefs-lieux qui sont les centres des réseaux locaux (du type TER) certes plus modestes mais nécessaires si l’on veut atteindre les plus petits villages. La même observation vaut pour le réseau Internet : les pôles sont alors ce que l’on appelle des routeurs, et il en existe aussi bien au niveau familial (si vous avez plusieurs ordinateurs avec Internet chez vous, vous possédez probablement un routeur), au niveau d’une université ou d’une entreprise, qu’au niveau national (par exemple Renater) et international. On observe donc au final une sorte de structure fractale dans laquelle les mêmes motifs se répètent à toutes les échelles. Pour en revenir au nombre d’Erdös, je ne sais pas à quel point cette structure fractale se manifeste dans la communauté mathématique, mais il est probable qu’elle soit encore très présente. En effet, il y a d’abord les grands mathématiciens (comme Paul Erdös) qui sont connus de tous leurs confrères tant leur contribution est (ou a été) volumineuse et variée. Il y a ensuite les mathématiciens dont la renommée est importante mais n’a pas réussi à dépasser les frontières de leur sous-domaine (par exemple l’arithmétique pour citer le mien). Si l’on s’intéresse à une localité plus géographique, on peut également citer certains chefs de laboratoire qui sont certainement bien connus sur leur campus, mais pas nécessairement au-delà. Et enfin, il y a les autres, et notamment les jeunes mathématiciens (typiquement les thésards), qui n’ont pas encore eu le temps de rencontrer beaucoup de confrères, ni de se faire connaître.