Discussion:Taux d'expansion (théorie des graphes)

Réflexions après rédaction

Le problème auquel je me suis heurté en écrivant cet article est qu'il n'y a pas deux auteurs qui prennent exactement la même définition des mêmes objets. Par ailleurs, on peut présenter le même problème sous plusieurs biais (pas exemple, compter les sommets au lieu de compter les arêtes, normaliser les valeurs propres ou non, classer les valeurs propres en valeur absolue ou en valeur signée, ne considérer que les graphes réguliers ou tous les graphes, etc.).

Les auteurs vont jusqu'à se contredire eux-mêmes à l'intérieur de leurs articles. Par exemple, ils disent tous qu'un graphe expanseur est un graphe creux, mais très peu le mettent dans la définition. Ceux qui le précisent ajoutent une contrainte sur le degré maximal du graphe, ce qui est un peu dommage pour ce malheureux graphe en étoile qui n'est pas spécialement dense et se trouve pourtant éliminé d'office de la course .

Là où l'article anglais essaye de contenter un peu tout le monde, ce qui donne au final un beau fouillis, j'ai préféré prendre le point de vue majoritaire, et dire à chaque fois « il y a d'autres façons de faire » de façon quelque peu évasive. Je crois que le lecteur qui veut creuser pourra le faire, et le lecteur qui ne s'intéresse qu'aux grandes lignes ne sera pas noyé sous la multiplicité des points de vue.

J'ai aussi essayé de multiplier les exemples concrets, dans un but de vulgarisation. Les démonstrations avancées sont absentes pour le moment, seuls les raisonnements élémentaires sont mis en avant. --MathsPoetry (d) 25 mars 2012 à 03:02 (CEST)

Directions futures pour cet article

Un certain nombre de notions ne sont pas abordées :

• expander mixing lemma (traduction ?)
• marches aléatoires sur des graphes expanseurs
• interprétation géométrique
• etc.

On pourrait aussi donner la démonstration de l'inégalité de Cheeger, ou de la construction de Margulis, dans les très grandes lignes. --MathsPoetry (d) 24 mars 2012 à 15:15 (CET)

Une inégalité troublante quoique sourcée

Permets une remarque naïve d'une personne qui découvre le sujet. Tout est très clair dans la première partie, on suit très bien, illustration à l'appui et puis arrive une affirmation troublante : un graphe connexe à n sommets est 1/n - expanseur. Si j'ai bien compris les premières lignes, il me semble qu'il est au moins 2/n - expanseur : en effet $|\partial G(W)|\geq 1$ et $|W|\leq n/2$. Ai-je commis une erreur de raisonnement ?

Je sais... si j'ai raison, l'article n'aura pas tort pour autant : un graphe 2/n - expanseur est , a fortiori, 1/n-expanseur. Mais l'information sous cette forme me semble entretenir la confusion : pourquoi préférer cette minoration faible plutôt qu'un minoration forte plus naturelle ? HB (d) 29 mars 2012 à 15:28 (CEST)

C'est parfaitement exact. Il est 2/n-expanseur.

Je n'ai pas "osé" mettre 2/n car la source ne mentionne que 1/n. Oui, c'est crétin... Je suis trop consciencieux, je crois.

Vas-y, change en 2/n. Et merci pour cette lecture ! --MathsPoetry (d) 29 mars 2012 à 16:20 (CEST)

Bon j'ai vu que tu l'avais changé. J'ai supprimé la référence car elle ne correspond plus à l'affirmation de l'article. HB (d) 30 mars 2012 à 13:29 (CEST)

T'as bien fait (snif, ma belle source). --MathsPoetry (d) 30 mars 2012 à 14:08 (CEST)

Boucles et arêtes multiples

J'ai poursuivi ma lecture naïve et je rencontre un second problème. Dans l'encadrement du taux d'expansion, on a besoin de travailler sur la matrice d'incidence d'adjacence rhaaa. la définition de la matrice d'incidence comporte un flou assez surprenant dans le cas des boucles et cela a un impact très fort sur les valeurs propres de la matrice. A moins que dans un graphe k-régulier, il n'y ait pas de boucle? L'article sur WP graphe régulier ne le dit pas. J'ai cherché un peu sur le net. Seul Bibm@th précise qu'un graphe régulier est avant tout un graphe simple. Je trouve ailleurs des définitions lapidaires "un graphe k- régulier est un graphe dont tous les sommets sont de degré k" et des exemples toujours choisis dans les graphes simples. Dans l'article graphe régulier le théorème de Crispin Nash-Williams me semble faux si on accepte les boucles. Donc la question est "un graphe régulier est-til toujours simple ?" Si oui, il faut modifier l'article de WP correspondant. Sinon, il faut se poser la question : dans le cas de l'inégalité de Cheeger and co, faut il ajouter la condition simple ? Si la réponse est non, il faut alors préciser comment sont comptées les boucles. HB (d) 30 mars 2012 à 13:29 (CEST)

Bonne question.

Mon impression était que dans un graphe k-régulier (disons d-régulier, pour faire comme dans l'article), il peut y avoir des boucles.

Les boucles comptent chacune pour 2 dans le degré (puisqu'elles arrivent deux fois au même sommet), voir degré (théorie des graphes) où je le source.

Dans une construction connue de familles d'expanseurs dont je ne parle pas dans l'article, de degré 3, on dit que deux "sommets" de Z/pZ sont liés si ils se suivent ou se précèdent, ou sont inverse l'un de l'autre. Que je sache, plein de nombres en plus de 1 sont leur propre inverse, par exemple p - 1, mais pas seulement. Donc c'est un exemple où il y a plein de boucles. C'est d'ailleurs étonnant que ce soit une famille d'expanseurs avec autant de boucles, je me suis fait la réflexion.

T'es sûr qu'un graphe régulier est simple ? Ça me surprend beaucoup, et si c'est le cas, il faut corriger l'article graphe régulier ici !

Sur le principe, je ne vois pas trop de problème à travailler avec un multigraphe, avec même plusieurs arêtes entre deux sommets. Certaines opérations de manipulation des expanseurs créent d'ailleurs ces arêtes multiples.

Dans le cas de boucles, le graphe ne sera pas un très bon expanseur, puisque les boucles ne sortiront jamais du sous-ensemble S choisi. Pour les arêtes multiples, je ne sais pas quelle peut être l'incidence sur le taux d'expansion.

Il me semble qu'un des auteurs précise explicitement que les boucles sont autorisées, je te cherche ça. --MathsPoetry (d) 30 mars 2012 à 13:59 (CEST)

Ouaip, c'est dans Hoory et. al. p. 252, « 2.1 - Edge expansion and a combinatorial definition of expanders. Let us introduce some conventions now. Unless we say otherwise, a graph G = (V, E) is undirected and d-regular (all vertices have the same degree d; that is each vertex is incident to exactly d edges). Self loops and multiple edges are allowed. »

Pour bibmath qui dit qu'un graphe régulier est un graphe simple, je ne sais pas d'où ils ont tiré ça. Le leur signaler ?

L'article Matrice d'incidence dit explicitement comment ça se passe avec les boucles. Tu ne l'as pas vu ?

Crispin Nash-Williams me semble aussi faux si l'on admet les boucles ou les arêtes multiples. Le signaler d'urgence sur la page Graphe régulier.

Cordialement, --MathsPoetry (d) 30 mars 2012 à 14:19 (CEST)

rhaa j'ai corrigé ma confusion sur incidence et adjacence... Tu m'engages à aller faire des modifs dans les articles mais vu mon niveau dans ce domaine je préfère me contenter de poser des questions et de soulever les problèmes que de tenter des corrections sans connaissance suffisante. HB (d) 30 mars 2012 à 15:12 (CEST)

Ah oui, c'est pas pareil. Bah, on apprend tous. Bon, je signale le problème avec Crispin Nash-Williams sur la bonne PDD. Continue à poser les bonnes questions, et je continue à essayer d'y répondre . --MathsPoetry (d) 30 mars 2012 à 16:10 (CEST)

Autre point de vue et degré borné

Bonjour,

étant plutôt de la communauté "informatique théorique" je suis un peu géné par l'article : quand j'entends parler de graphes expanseurs c'est sous la forme de $(n,d,\lambda )$-expanseur, c'est à dire n sommets, degré maximum d, $\lambda$ le deuxième plus grand module de valeur propre. Et ici cet aspect (degré borné) n'est qu'anecdotique alors que pour les applications en informatique théorique c'est la notion centrale (par exemple pour cette source très valable (et très courte) [1], " In words, an expander is a highly connected sparse graph X"). J'ai lu les autres sujets de la discussion, donc je vois que c'est un choix, et il faut bien en faire un.

Comment pourrait-on changer cela ? Je vais essayer de voir le point de vue des sources de l'article.--Roll-Morton (discuter) 11 avril 2014 à 11:13 (CEST)

En me baladant dans les sources, j'avais trouvé des définitions assez fluctuantes, effectivement. Bon courage donc si tu veux y mettre un peu d'ordre. J'ai l'impression que l'article doit reprendre cette multiplicité des points de vue. Attention, l'informatique théorique c'est bien, mais il y a aussi des matheux purs qui bossent sur la théorie des graphes . --Catarella (discuter) 20 avril 2014 à 21:44 (CEST)

Hum, en fait ça va demander beaucoup de travail de biblio. Je le remets à plus tard...--Roll-Morton (discuter) 6 mai 2014 à 13:46 (CEST)

Je crois qu'on a en gros un siècle pour finir cette encyclopédie , rien ne presse. --Catarella (discuter) 7 mai 2014 à 22:57 (CEST)

Découper en deux ? / Renommage

Que pensez-vous de l'idée de découper l'article en deux : l'un serait expansion (théorie des graphes) et expliquerait l'expansion comme invariant/paramètre du graphe et l'autre serait Graphe expanseur ? Il me semble que cela simplifierait un peu la chose. C'est un choix qui n'a pas été fait en anglais, donc il y a peut-être des inconvénients, mais je n'en vois pas vraiment. --Roll-Morton (discuter) 17 février 2015 à 14:55 (CET)

En relisant les discussions du haut, je ne sais pas si c'est une très bonne idée de multiplier les articles, avec risque d'incohérence. Mais quand même...--Roll-Morton (discuter) 17 février 2015 à 15:03 (CET)

Pas trop chaud pour découper. On serait obligé de faire des rappels dans tous les sens, ça compliquerait la lecture, etc. On est une encyclopédie, pas un dictionnaire. --Catarella (discuter) 17 février 2015 à 16:07 (CET)

Ce qui m'embête c'est que dans un certains cas (certes rares), j'ai envie de faire un lien pour la notion d'expansion hors du cadre des expanseurs et je suis obligé de lier à cet article ce qui doit être déroutant pour le lecteur.--Roll-Morton (discuter) 17 février 2015 à 16:59 (CET)

Plus précisément, comme dit en introduction, la notion de graphe expanseur renvoie souvent à l'idée d'un graphe fortement connecté d'une certaine manière, alors que l'expansion est un paramètre, qui peut être faible (un peu comme le dit la dernière phrase du RI...).--Roll-Morton (discuter) 17 février 2015 à 17:03 (CET)

En passant : ok pour enlever le bandeau d'ébauche ? --Roll-Morton (discuter) 17 février 2015 à 17:29 (CET)

J'ai enlevé le bandeau.

Sur le fond, un "graphe expanseur" ça n'existe pas, la terminologie est foireuse. Tout graphe est plus ou moins expanseur. Tout dépend de combien.

Un problème si on découpe, c'est que la notion de "graphe expanseur" et de "taux d'expansion" sont très fortement liées et je sens le découpage comme artificiel.

Au passage "taux d'expansion" serait un meilleur titre que "expansion".

Enfin, "expanseur" et "fortement connecté", ce n'est pas tout à fait la même chose.

Depuis un autre article, tu peux toujours lier vers une certaine section de l'article avec la syntaxe [[Graphe expanseur#section|Mon titre]].

Il y aurait aussi la solution de renommer au lieu de découper ? --Catarella (discuter) 17 février 2015 à 18:14 (CET)

Je pense que ton premier point est précisément là où les sources et les communautés divergent. Pour moi, et dans la littérature que je connais (je précise tout de suite, je ne suis pas spécialiste, disons que je tombe régulièrement sur la notion sans la travailler vraiment), quand on parle de graphe expanseur, on entend un graphe avec un fort taux d'expansion. Par exemple on dira : "telle borne est atteinte en construisant un famille particulière de graphes expanseurs". Quand on veut être précis, on parle de (n,d,delta)-expanseur. Une solution serait de renommer cet article en "taux d'expansion" et de faire un article (n,d,delta)-expanseur. Mais encore une fois, je ne veux pas imposer mon point de vue, je connais mal le sujet, et l'article est chouette. --Roll-Morton (discuter) 17 février 2015 à 20:57 (CET)

"Enfin, "expanseur" et "fortement connecté", ce n'est pas tout à fait la même chose." oui bien sûr, il y a la densité qui rentre en jeu. C'était juste pour montrer que dans l'intro même ce n'est pas très clair (en y repensant c'est peut-être moi qui ai fait cet ajout, dans ce cas mea culpa). --Roll-Morton (discuter) 17 février 2015 à 20:59 (CET)

Merci pour le "l'article est chouette" :-)

Ben oui, on dit la même chose, "graphe expanseur" dans l'absolu, ça n'existe pas. À la limite, "graphe fortement expanseur". Je suis parti essentiellement de la version anglaise qui parle (si je me souviens bien) de "expander graph" dans l'absolu.

Les sources, si je me souviens bien, parlent de xxx-expanseur, où xxx vaut parfois (n,d,delta), mais pas toujours, et une des difficultés auxquelles je me suis heurté en rédigeant est justement qu'il y a un certain nombre de définitions convergentes dans l'idée générale, mais divergentes sur les détails.

Comme tout procède de ce fameux taux d'expansion, je me demande de plus en plus s'il ne faudrait pas renommer l'article en Taux d'expansion (théorie des graphes), et refaire le résumé introductif. Au moins dans un premier temps. Après, on pourrait voir pour une division éventuelle.

À noter que Taux d'expansion porte sur la cosmologie :-)

En tout cas, merci pour ton dialogue constant et toujours cordial. --Catarella (discuter) 17 février 2015 à 21:13 (CET)

Bonjour, je suis partisan du renommage en Taux d'expansion (théorie des graphes) que tu proposes et du petit changement d'intro qui suit. Et merci aussi pour ton attitude .--Roll-Morton (discuter) 18 février 2015 à 11:50 (CET)

OK, je te laisse faire . --Catarella (discuter) 18 février 2015 à 17:05 (CET)

 OK J'ai modifié l'intro et le premier paragraphe. Tu peux reprendre comme tu veux bien sûr.--Roll-Morton (discuter) 18 février 2015 à 18:50 (CET)

Très bien et du coup l'article est beaucoup plus lisible et logique dans son organisation. Bravo.

Il y a juste le mot "petit" de l'intro qui me gène un peu, car le "petit" sous-ensemble peut aller jusqu'à la "moitié" du graphe. Mais je n'ai pas mieux.

Par ailleurs, je n'ai pas trouvé dans la note 2 de texte correspondant à ce que tu dis (même si c'est juste au demeurant). S'agit-il d'un reliquat du résumé introductif tel qu'il était avant ? --Catarella (discuter) 18 février 2015 à 20:10 (CET)

Content que tu sois content. Le "petit" ne me plaît pas trop non plus. Et pour la note, en effet c'est un reliquat, et comme c'est un "ref name", j'ai reporté à plus tard la suppression/modification. --Roll-Morton (discuter) 18 février 2015 à 22:30 (CET)

"petit" veut dire ici "pas trop gros" mais ça heurterait mes oreilles sous cette forme. J'ai viré la référence du RI en la laissant pour les autres endroits (magie du couper-coller). J'ai transformé Taux d'expansion en page d'homonymie, aucune raison de privilégier la cosmologie.

Si cet article t'intéresse, #Directions futures pour cet article donne des idées de développement. --Catarella (discuter) 18 février 2015 à 23:13 (CET)

Peut-être "relativement petit" ? Ok pour le reste. --Roll-Morton (discuter) 19 février 2015 à 10:56 (CET)

Faute de mieux... --Catarella (discuter) 19 février 2015 à 20:09 (CET)

Déplacer l'historique

Bonjour, on pourrait peut-être déplacer l'historique après les définitions. --Roll-Morton (discuter) 20 février 2015 à 10:53 (CET)

Oui, surtout que c'est plus une liste d'applications qu'un historique. Renommer la section ? --Catarella (discuter) 20 février 2015 à 15:02 (CET)

Une référence bizarre

La référence donnée pour les graphes de Margulis ne prouve pas que $\lambda _{2}\leq 5{\sqrt {2}}$, mais que $\lambda _{2}\leq 3.65$, ce qui semble par ailleurs complètement faux...--Dfeldmann (discuter) 9 avril 2020 à 12:05 (CEST)