Discussion:Théorème de Robertson-Seymour/Article de qualité

Cet article a été promu comme Article de qualité en vertu de ce vote.
Merci de remplacer ce modèle par {{Contestation CdQ}} si le vote est remis en cause.

Article promu au terme du second tour.

• Bilan : 6 pour, 2 bon article, 0 attendre, 2 autre(s) vote(s).
• Commentaire : (pour) / (pour + bon article + attendre) = 75 % ≥ 75 %

Udufruduhu (d) 21 décembre 2011 à 11:07 (CET)

Article en second tour.

• Bilan : 5 pour, 1 bon article, 0 attendre, 2 autre(s) vote(s).
• Commentaire : Au moins 8 votes et (pour) / (pour + bon article + attendre) = 83,3 % ≤ 90 % mais (pour + bon article) / (pour + bon article + attendre) = 100 % > 50 %

Udufruduhu (d) 5 décembre 2011 à 08:33 (CET)

Théorème de Robertson-Seymour

Proposé par : Dfeldmann (d) 6 novembre 2011 à 10:44 (CET) Au départ, c'est une traduction de l'article anglais, mais je l'ai complété, renseigné tous les liens rouges, etc. Je ne sais trop s'il est vraiment au niveau d'un AdQ, mais justement, je voudrais bien le voir soumis à une critique sévère, y compris de non-spécialistes.

Je viens de rajouter une sous-section donnant les grandes lignes de la démonstration ; qu'en pensez vous ?--Dfeldmann (d) 10 décembre 2011 à 21:24 (CET)

Votes

Format : Motivation, signature.

Article de qualité

1.  Article de qualité Ben franchement, je vois plus ce que je pourrais encore faire pour cet article... (quoique, au vu des discussions, on peut toujours peaufiner) --Dfeldmann (d) 6 novembre 2011 à 10:47 (CET) De fait, pas mal d'améliorations, pas toujours mineures, ont déjà été apportées à cet article en cinq jours, et c'était, après tout, l'objectif essentiel. Mais que ça ne vus empêche pas de voter, hein...--Dfeldmann (d) 11 novembre 2011 à 14:14 (CET)
2.  Article de qualité Article intéressant, même si je n'ai pas tout compris. C'est pour ça que j'ai un peu hésité avant de voter, mais vu que personne ne se lance... MicroCitron ^{un souci ?} 12 novembre 2011 à 00:54 (CET)
3.  Article de qualité Article assez difficile à comprendre en effet de par son sujet pointu. Voir quelques remarques ci-dessous.--Jackverr (d) 13 novembre 2011 à 15:23 (CET)
4.  Article de qualité Après de multiples lectures, j'ai fini par comprendre un peu le sujet. Qui sait ça m'aidera peut-être à résoudre le problème de complexité exponentielle qu'est l'interaction de configuration. Ne serait-il pas possible d'en dire un peu plus sur la démonstration? Silverkey (d) 27 novembre 2011 à 21:04 (CET)

   Hélas, j'ai fait de mon mieux, mais c'est vraiment très technique. Les principales idées "neuves" viennent de la décomposition arborescente, et de considérations topologiques (ce qui est en soi déjà une surprise) sur les plongements de graphes sur des surfaces. Les divers exposés donnés en bibliographie (surtout le cours de Diestel) permettent d'en savoir un peu plus long...--Dfeldmann (d) 27 novembre 2011 à 21:18 (CET)

   Je viens de rajouter un paragraphe donnant les grandes lignes de la démonstration ; qu'en pensez vous ?--Dfeldmann (d) 10 décembre 2011 à 21:23 (CET)

5.  Article de qualité Gregory 14 (d) 3 décembre 2011 à 08:21 (CET)
6.  Article de qualité L'absence d'intervention de M. Courcelle après les dernières modifications laisse supposer que ces ajouts sont suffisants pour un expert. D'où mon changement de vote v_atekor (d) 20 décembre 2011 à 09:27 (CET)

Bon article

2. A ce que je comprends et connais sur ce que dit l'article c'est pour moi un bon article et je tiens à féliciter Dfeldmann (d · c · b) pour son travail considérable et remarquable. Maintenant je me juge incompétent pour juger si c'est ou non un AdQ, soit une référence en synthèse du savoir sur le sujet. L'avis ci-dessous de Bruno Courcelle (d · c · b) laisse à penser que l'article reste perfectible et via n'a pas atteint l'acmée wikipédienne ; je laisse ceux qui en savent beaucoup plus que moi juger. --Epsilon0 ε₀ 4 décembre 2011 à 03:33 (CET)

    Bon article Les remarques de Bruno Courcelle (d · c · b) considéré comme un spécialiste du sujet par plusieurs contributeurs font penser que l'article est incomplet pour des spécialistes. Cependant, la vulgarisation du sujet est tout à fait remarquable, et je crains que le folklore évoqué soit tout à fait indispensable pour nombre de lecteurs, voire indispensable à l'attribution du label, puisque le folklore autour d'un sujet doit y être traité (voir les autres Articles de qualité). Aussi, ma conclusion est que les parties développées de ce l'article sont de qualité, mais que certaines parties importantes sont manquantes ou insuffisamment développées : il s'agit précisément de la définition du Bon Article. D'où mon vote. v_atekor (d) 10 décembre 2011 à 12:08 (CET)

3.  Bon article Mêmes raisons. L'article est une amélioration de l'article anglais. C'est un bon travail. Je regrette que l'on n'ait pas d'autres références en français que l'article de Delahaye. Peut-être que Bruno Courcelles pourrait contribuer en donnant une liste de références en français que l'on pourrait utiliser.--Cbigorgne (d) 10 décembre 2011 à 12:28 (CET)

   Je suis en train de rédiger un paragraphe d'esquisse de démonstration ; j'y fais référence à ce document de Bruno Courcelle, mais j'ai eu le regret de constater que sa propre liste de référence ne contenait que des documents en anglais... et l'article de Delahaye (de plus, la plupart des publications récentes sur le sujet sont non seulement en anglais, mais difficiles d'accès). En revanche (et je m'en suis déjà servi), Eric Thierry organise un séminaire annuel de théorie des graphes, où ont déjà eu leu plusieurs exposés sur le théorème des mineurs (celui-ci, ou encore celui-là)... mais ils se gardent bien d'aborder la démonstration proprement dite. Du coup, je me demande même si, dans le cas où un expert (Bruno Courcelle lui-même, probablement) tenterait d'en faire un exposé plus satisfaisant, on ne tomberait pas du coup dans le TI...--Dfeldmann (d) 10 décembre 2011 à 13:50 (CET)

   Finalement, cela aura été plus rapide que prévu, grâce au cours de Reinhard Diestel. Je viens donc de rajouter la sosu-section donnant les grandes lignes de la démonstration ; qu'en pensez vous ?--Dfeldmann (d) 10 décembre 2011 à 21:26 (CET)

Neutre / autres

2. contreAdQ PAS de qualité Cet article est mal construit. Pas besoin de redéfinir un graphe avec le folklore de Konigsberg. Il vaut mieux pointer sur les pages existantes sur les graphes. L'article ne donne aucune indication des méthodes de preuves (structuration des graphes). La partie complexité paramétrée , marginale, devrait être traitée à part, dans un article du genre : existence et construction d'algorithmes FPT. Les gens qui liront cet article sauront déja ce qu'est un graphe, P et NP etc... Donc à reprendre sérieusement avant de "candidater" pour AdQ.--Bruno Courcelle (d) 29 novembre 2011 à 17:55 (CET) Vote non-valable déplacé : moins de 50 contributions au lancement de la procédure. Gemini1980 oui ? non ? 29 novembre 2011 à 18:28 (CET)

   Sur ce déplacement, conforme aux règles formelles de wp:fr (qui ont pour simple raison d'éviter des abus) je tiens à préciser, car Bruno Courcelle est un spécialiste du domaine traité par l'article , qu'un avis argumenté, même déplacé dans une section "hors vote" vaut toujours plus qu'un avis où l'on met +1 ou -1. Je fais cette simple précision afin que nonobstant ce déplacement, Bruno Courcelle n'hésite pas à continuer à donner son avis constructif sur cette page, voire participe directement à l'article. Bien cordialement à tous. --Epsilon0 ε₀ 29 novembre 2011 à 22:16 (CET)

   On est bien d'accord, ce vote est non-valable seulement dans le sens de son admissibilité sur le plan comptable, mais les arguments sont largement recevables et l'avis infiniment respectable. Gemini1980 oui ? non ? 29 novembre 2011 à 23:35 (CET)

3.  Neutre vote technique pour permettre le passage au second tour. Udufruduhu (d) 4 décembre 2011 à 20:40 (CET)

Discussions

Remarques de MicroCitron

Bonjour, j'ai lu cet article avec beaucoup d'attention et en tant que non-spécialiste. Deux remarques :

• J'ai rajouté une référence nécessaire à un endroit (l'affirmation est peut-être évidente, mais un exemple en note ne ferait pas de mal je pense...)
• La notion d'invariant de graphe devrait être brièvement expliquée (mais c'est peut-être trop long).

Voilà, sinon j'ai assez peu compris (surtout vers la fin) mais je ne pense pas que ça vienne de l'article . MicroCitron ^{un souci ?} 6 novembre 2011 à 12:07 (CET)

Bonnes remarques ; j'ai corrigé et complété en conséquence--Dfeldmann (d) 6 novembre 2011 à 12:43 (CET)

Remarques de Gemini

• La section 1, ou du moins son titre, est maladroit : la seule introduction d'un article c'est son résumé introductif.
• Il y a un peu trop de graisse ; au pire, les termes à mettre en exergue peuvent être en italique, quoi que ce n'est pas indispensable.

Salutations. Gemini1980 oui ? non ? 6 novembre 2011 à 13:17 (CET)

Ok, j'ai modifié en conséquence--Dfeldmann (d) 6 novembre 2011 à 14:07 (CET)

Remarques de Berichard

Je n'ose pas prendre part au vote mais j'avoue pour avoir survolé mais pas compris l'article y avoir appris plein de choses beaucoup plus simples et notamment la notion de mineur qui est un sujet de fond surtout dans le Pas de Calais. Puisque j'ai une nouvelle fois la chance de croiser la route de personnes aussi compétentes, pourrait on m'expliquer ce qu'est une relation canonique et éventuellement reprendre la notion de base canonique. Avec toutes mes excuses pour mon impudence. Un vieux dinosaure à la physiologie déficiente Berichard (d) 6 novembre 2011 à 16:37 (CET)

Question de Epsilon0

Si c'est important, quelle est la définition d'une "forêt" dans une démonstration d'une vingtaine de pages de ce que si l'un des mineurs exclus est une forêt, le théorème est vrai ? Je ne vois rien dans Arbre (mathématiques) qui doit donc la cacher ni dans le texte mis à la note 11 de Reinhard Diestel (qui utilise le terme forest sans le définir) ? --Epsilon0 ε₀ 7 novembre 2011 à 00:25 (CET)

Une forêt, c'est une réunion d'arbres. Plus abstraitement, c'est un graphe (simple non orienté) acyclique. J'ajoute une note.--Dfeldmann (d) 7 novembre 2011 à 01:16 (CET)

Merci ! Bon je m'en doutais un peu mais je me méfie des def intuitives ;-). Sinon, pinaille, ce ne serait pas mieux de parler d'ensemble d'arbres disjoints plutôt que de réunion disjointe d'arbres ? Je dis cela en ignorant le vocabulaire usuel en théorie des graphes. --Epsilon0 ε₀ 7 novembre 2011 à 01:56 (CET)

Je sais pas trop, mais ensemble est plus facile à lire, donc d'accord (d'autant que c'est pas un article rigoureux sur les forêts, mais juste un passage où elles servent d'exemple)--Dfeldmann (d) 7 novembre 2011 à 06:45 (CET)

Non, un ensemble d'arbres n'est pas une forêt (au sens mathématique), c'est un ensemble. Une forêt est bien une réunion disjointe d'arbres. Ambigraphe, le 9 novembre 2011 à 09:38 (CET)

Dans les 2 cas me semble t-il on est sur des ensembles (à moins qu'il y ait des réunions non ensemblistes). Et 1/La distinction est que un ensemble d'ensembles disjoints {a, b} et {c, d} donne { {a,b }, {c, d} } tandis que leur réunion donne {a, b, c, d}. 2/ Aussi, l'union disjointe de {a, b} et de {b, c} va donner {a, b1, b2, c} ou { {a,b}, {b, c} } [selon la manière dont on comprend la notion d'union disjointe : la notion me semble éventuellement floue hors contexte précis ] alors que l'ensemble des ensembles disjoints {a, b} et {b, c} ben n'existe tout simplement pas car les 2 ensembles ne sont pas disjoints (--> et je crois comprendre que c'est cette dernière chose qui est supposée dans la notion de forêt : les arbres sont disjoints). On peut faire une union disjointe de ce qu'on veut mais pas faire un ensemble d'objets disjoints, s'ils ne sont pas préalablement disjoints. Mais bon, fin de ma pinaille, comme dit Dfelmann, c'est pas un article rigoureux sur les forêts, mais juste un passage où elles servent d'exemple. --Epsilon0 ε₀ 12 novembre 2011 à 04:39 (CET)

J'arrive un peu tard, mais je comprends enfin le malentendu : il ne s'agit pas d'une « union disjointe » d'arbres (avec la construction classique rappelée par Epsilon0), mais d'une union (ensembliste) d'« arbres disjoints », c'est-à-dire d'arbres dont les ensembles de sommets sont (2 à 2) d'intersection vide. Bon, arrêtons le pinaillage, et, au besoin, essayons d'écrire un bel article forêt (théorie des graphes) ...--Dfeldmann (d) 13 novembre 2011 à 06:19 (CET)

Remarques de Jackverr

Sur le fond je n'ai rien à dire si ce n'est que je n'ai pas compris la phrase "il est considéré généralement comme un des résultats les plus importants et inattendus de la théorie des graphes". Qu'est-ce qui est inattendu : l'ensemble de la démonstration ou le résultat? Sur la forme j'aurais aimé que les citations des articles en pdf soient signalés par le modèle [PDF] et que dans la bibliographie il n'y ait que des ouvrages et non pas des ouvrages et des articles disponibles sur internet. Je pense que ce serait plus en adéquation avec les normes de cette encyclopédie. Beau boulot, sinon!--Jackverr (d) 13 novembre 2011 à 15:33 (CET)

Un peu les deux : le résultat est très important, et Wagner lui-même pensait qu'il était faux. La démonstration a nécessitée la création d'outils originaux, qui se sont avérés fort utiles, etc. Bon, va falloir légèrement réécrire cette phrase.

Pour les citations, je m'y mets sur le champ. Mais, dans l'ensemble, c'est justement parce qu'il n'y a (encore) guère de vrais livres sur la question que j'ai utilisé des textes (cours, notes de cours, etc;, souvent ayant le format de livres entiers) disponibles sur le Net--Dfeldmann (d) 13 novembre 2011 à 15:40 (CET)

bon, voilà qui est fait ; le résultat convient-il?--Dfeldmann (d) 13 novembre 2011 à 16:14 (CET)

OK. Désolé, je sais que les critiques sur la forme sont pénibles quand on a passé un certain temps sur le fond.--Jackverr (d) 13 novembre 2011 à 18:51 (CET)

Absolument pas, j'apprends beaucoup de chaque critique. Merci, au contraire.--Dfeldmann (d) 13 novembre 2011 à 19:11 (CET)

Remarques de 140FLo

Je ne prendrai pas part au vote, étant incapable de juger le fond de l'affaire. Je voulais juste dire que je ne vois pas d'objection à la promotion de l'article si on se refère aux critères d'admissibilités et que c'est indiscutablement du bon travail. Cela dit peut être qu'une promotion en deux temps avec d'abord la qualification de "bon article" aurait permis d'attirer d'autres contributeurs et donc par la confrontation d'avis d'améliorer encore l'article (il est peu être un peu "aride" mais c'est vrai qu'étant donné le sujet c'est probabement dificile de faire autrement) avant de lui accorder le précieux "Adq". --140FLo(d) 16 novembre 2011 (CET)

Mmm... Ben oui, mais qu'est-ce qu'on fait des articles spécialisés, alors ? Par définition, le lecteur incapable de "juger du fond" doit pouvoir quand même tirer quelque chose de l'article (surtout ce lecteur là, dirais-je) Et c'est même , à mon avis, une vraie pierre d'achoppement pour un AdQ : si le lecteur lambda ressort de l'article aussi ignorant qu'avant, l'article est forcément raté quelque part. J'ai du mal à croire, par exemple, que les votes d'AdQ pour des articles tels que Obéron (lune) venaient tous d'astronomes chevronnés, et l'article est pourtant plutôt indigeste pour le botaniste moyen...--Dfeldmann (d) 16 novembre 2011 à 19:43 (CET)

Oui bien sûr le lecteur lambda doit pouvoir y trouver son compte et à ce niveau là, je pense que l'article essai d'impliquer le lecteur non spécialiste. Simplement pour lui accorder un label "Adq" il faut aussi être sûr-et-certain de son contenu mathématique et là je ne peux pas juger correctement de ce qui est exposé, c'était justement aussi pour attirer quelques connaisseurs et des contributeurs plus nombreux qu'une classification en "bon article" aurait pu différer un chouilla la labelisation de l'article. --140FLo(d) 16 novembre 2011 (CET)