Discussion:Théorème de Robertson-Seymour

Croissance

1. La phrase « ainsi, on verra plus loin que les ensembles d'obstructions correspondant à un invariant de graphe borné par k sont des antichaînes dont la taille est une fonction au moins exponentielle de k » me semble prématurée et trop digressive pour cette section (on n'a même pas encore parlé d'obstruction) il suffirait de dire : « voir plus loin », et avec un lien plutôt vers la sous-section « Reconnaissance en temps polynomial » que « Complexité paramétrée ». D'ailleurs, a-t-elle vraiment un sens ? (si I est un invariant, exp(I) aussi).
2. « la constante de proportionnalité croît avec la taille de G de manière exponentielle » : peut-être « non polynomiale » serait plus prudent ?

Anne Bauval (d) 10 novembre 2011 à 10:29 (CET)

Ok pour le premier point, qiute à rédiger comme une note : les ens d'obstructions ... En revanche, l'ensemble d'obstructions corresopndant à la famille des graphes dont la largeur arborescente, mettons (ou tout simplement le nombre de sommets) est inférieur à n est bien un ensemble de taille au moins n (et en fait, surexponentiel en n), ce qui suffit à justifier l'argument...--Dfeldmann (d) 10 novembre 2011 à 13:08 (CET)

1. Note ok, puisque tu précises maintenant un exemple « raisonnable » d'invariant
2. ? : sur :en il disent « superpolynomially »

Anne Bauval (d) 10 novembre 2011 à 19:18 (CET)

En fait, j'ai nettement mieux ; le temps de rédiger ça proprement (mais je sais même pas si je vais le laisser en note, ou le mettre dans le corps du texte), et tu verras qu'on a même une croissance factorielle du nombre d'obstructions...--Dfeldmann (d) 10 novembre 2011 à 19:47 (CET)

Titres des sections

Bonjour,

après une première lecture, j'ai été gêné par les titres de section. Je pense que il serait plus clair de diviser la section == Définitions préliminaires et énoncé du théorème == en deux parties

• Notions de mineur d'un graphe et relation d'ordre associée
• Énoncé du théorème.

Cela rendrait plus clair (à mon avis) le plan de l'article.

Couper en sous-sections, peut-être... Mais c'est déjà très court, non? Bon, je vais essayer

J'ai également été gêné par le titre de section « == présentation informelle du théorème == » où je m'attendais à des explications plus détaillées sur le théorème. Je pense que

« Un cas particulier du théorème : la caractérisation des graphes planaires »

ou

« Un cas particulier : le théorème de Kuratowski »

seraient plus précis comme titres de section.

là, par contre, non : l'idée, c'est justement que l'article graphe planaire existe déjà (avec les théorèmes de Wagner et de Kuratowski), et que le théorème des mineurs en est une généralisation : c'est sur ce point qu'il faut peut-être insister plus...--Dfeldmann (d) 20 novembre 2011 à 18:01 (CET)

Cordialement.--Cbigorgne (d) 20 novembre 2011 à 11:39 (CET)

Précision sur l'introduction

Je continue ici, puisque la discussion concerne la rédaction de l’article. Ce n’est pas un problème de détail, il s’agit seulement de rendre compréhensible l’énoncé de manière aussi autonome que possible. Pour moi, l’introduction doit être lisible sans effort par n’importe qui, ou presque. Comme j’ai dit au début, le fait de caractériser quelque chose comme ne contenant pas autre chose est déconcertant (je finis par m’y habituer, d’ailleurs, mais je pense que ma première réaction est significative). Donc j’ai essayé de trouver une formulation qui soit aussi simple que possible: "la liste finie de graphes qu’elle ne contient pas" est simple, on comprend que cela peut caractériser quelque chose ; "une liste finie de graphes qu’elle ne contient pas", l’est un peu moins (à quel point cette liste est bien définie, est-ce que le "qu’elle ne contient pas" est une précision, ou une définition de la liste, etc.). Ensuite, tu as expliqué qu’en fait "ne contient pas" n’était pas correct, donc j’ai essayé d’adapter, mais c’est indépendant de la question de départ. On peut aussi envisager d’expliquer l’énoncé à l’envers : "le théorème de Robertson-Seymour généralise le théorème de Kuratowski qui caractérise les graphes plantaires etc. Il dit que…, donc permet de caractériser de nombreuses familles de graphes à partir d’une liste finie/de la liste finie des graphes (et ici qu’elle ne contient pas, ou bien qui ne peuvent se déduire de graphes de la famille par des constructions simples). Cordialement, --Cgolds (d) 16 janvier 2013 à 14:15 (CET)

Ponctuations et références

Bonjour,

j'ai remarqué que dans cette article les références sont mises après la ponctuation, contrairement à la typo habituelle sur wikipedia, est-ce qu'il y a une raison ? --Roll-Morton (discuter) 9 mars 2014 à 20:37 (CET)

C'est ma faute, j’ai restauré la version avant mes modifs. Je trouve carrément inhestétique et bizarre d'avoir des fin de phrase comme ça    .

(avec plein d'espace entre la dernière lettre et la ponctuation), mais apparemment c'est la manière habituelle de faire. J'aime pas du tout parce qu'en lecture rapide c'est un peu perturbant, comme les virgules avec des espaces préfixes , mais apparemment il n’y a que moi que ça gène. Quitte à faire comme ça je préfèrerai que les références ne soient pas en exposants comme dans les papiers de recherches en info. — TomT0m ^[bla] 9 mars 2014 à 20:48 (CET)

Ok. Je trouve aussi que c'est un peu gênant d'avoir des " ." mais à force d'être sur wikipédia le " .^{note1}" me choque aussi !--Roll-Morton (discuter) 9 mars 2014 à 20:56 (CET)