À propos du nombre d’Erdös

Le 16 juillet 2009  - Ecrit par  Xavier Caruso Voir les commentaires (5)

Le « nombre d’Erdös » est une sorte de distraction [1] 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 [2] (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 [3] 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 [4] ;
  • 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 [5] 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.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.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.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.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.math.cnrs.fr, on s’aperçoit que l’on a du faire appel à onze
intermédiaires [6].

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.

Notes

[1Si 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.

[2Page Wikipédia sur Paul Erdös

[3Par 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.

[4La 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 »

[5Je 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.

[6Dans 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.

Partager cet article

Pour citer cet article :

Xavier Caruso — «À propos du nombre d’Erdös» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • À propos du nombre d’Erdös

    le 20 décembre 2008 à 16:03, par Peter Haissinsky

    Je voudrais signaler la vidéo suivante, qui illustre
    la conjecture selon laquelle deux personnes seraient
    toujours liées par six intermédiaires :

    WWW.SIX.LEMONDEESTPETIT.CA, de Vali FUGULIN ;
    Québec, 2000, 26mn, vidéo, documentaire ;
    Production : Office National du Film du Canada.
    La réalisatrice se lance à l’assaut de la théorie des six degrés de séparation, qui prétend qu’il y aurait au plus six personnes entre chaque habitant de la planète.

    On peut en voir un petit extrait sur le site de l’Office Nationale du Film du Canada :

    http://www3.onf.ca/collection/films/fiche/index.php?id=33910

    Répondre à ce message
  • À propos du nombre d’Erdös

    le 16 juillet 2009 à 18:54, par Cécile Musy

    Bravo pour vos articles, très bien faits !

    Ce phénomène se rapproche du fait de passer d’un thème défini à un autre, pour dévier complètement du point de départ, par exemple dans les discussions ou dans le « surf » sur internet ; anecdote personnelle : je viens de découvrir votre site en cherchant une recette de soupe au pistou...

    Avec deux intermédiaires seulement !

    Répondre à ce message
  • À propos du nombre d’Erdös

    le 17 juillet 2009 à 09:21, par Ludmila

    Je note à la fois :

    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.

    ce qui est un peu effrayant et pourrait laisser croire que les mathématiciens sont d’une espèce différente, et :

    je viens de découvrir votre site en cherchant une recette de soupe au pistou...

    ce qui est rassurant en prouvant qu’il n’en est rien.

    Respectueusement

    Ludmila

    P.S. Quant à la recette elle-même, les 25 cl d’huile me semblent exagérés. De même que certains articles scientifiques, certaines recettes peuvent (doivent ?) être allégées.

    Répondre à ce message
  • À propos du nombre d’Erdös

    le 17 juillet 2009 à 10:42, par Sonia G.

    Merci pour cet article clair.
    On peut lire aussi La théorie des six de Jacques Expert qui est un polar dans lequel le tueur adopte comme mode opératoire la théorie des 6 degrés reliant deux individus quelconques.

    Répondre à ce message
  • À propos du nombre d’Erdös

    le 16 décembre 2012 à 23:37, par Alain Valette

    L’humoriste belge François Pirette a fait un sketch, que je trouve assez réussi, sur le théorie des 6 degrés de séparation :

    http://www.pirette.com/lgdb3_6poignees1.html

    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é ?

Suivre IDM