Talk:Robertson–Seymour theorem

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Discrete mathematics

Contents

[edit] Merging

There was a request on Planetmath about merging this entry. The following was commented:

The status of Robertson-Seymour theorem seems to be very fuzzy at the moment. They have claimed to possess a proof sometime in 1980's, and the started publishing a long series of papers to establish it. So far they have not published the proof in its entirety, and what they published is published with the longest delayed I have seen ever (for example, ``Minors 18 were submitted on 5 June 1990, and published in 2003; ``Minors 15 were submitted on 15 March 1992, and published in 1996, i.e., they were submitted _two years after_ the paper they used the results from it). At such rate when (or whether) the proof will be published is questionable. So, I would hesitate to call the Wagner's conjecture to be Robertson-Seymour theorem.

Can anyone comment if this was really proved and if this theorem has been acknowledged as such by the mathematical community? --Drini 23:12, 20 Feb 2005 (UTC)

Yes. The last paper for the Robertson-Seymour theorem was already published in 2004. Graph Minors. XX. Wagner's conjecture Neil Robertson, P.D. Seymour Journal of Combinatorial Theory, Series B 92 (2004) 325-357. --glancing 21 Sep 2005

[edit] Move

I propose to move this article back to Robertson-Seymour theorem, instead of its current location Robertson%E2%80%93Seymour_theorem. Actually, I do not see the point of having a non-ascii character that is almost the same of - instead of -. - Liberatore(T) 17:22, 18 March 2006 (UTC)

[edit] Consequences

The Consequences section restates ideas. Sometimes something is restated 3 times! The motivation behind this seems to be that it may make the material easier to understand. However, it makes the text take longer to read. The only reason I can see that something is being restated is that technical terms are used and they may not be understood by some. It is much prefered (by me at least) to use more linking which would better enable the reader to discover the meanings of technical terms. --GrimRC 86.4.53.107 15:18, 25 July 2006 (UTC)

[edit] missing information

This article says the following sets of finite graphs are downwardly closed:

  • The set of all graphs that are disjoint unions of paths
  • The set of all forests
  • The set of all planar graphs
  • The set of all outerplanar graphs
  • The set of all graphs that can be embedded without edge intersections in a torus
  • the set of all graphs that can be embedded without edge intersections in a fixed arbitrary surface S
  • the set of all graphs that are knotlessly embeddable in Euclidean 3-space
  • the set of all graphs that are linklessly embeddable in Euclidean 3-space

The theorem says that in each such case there's a finite set of forbidden minors. I think the article should state explicitly what the set of forbidden minors is in each case. I know what they are in the case of planar graphs; I used to know in at least a couple of other cases---I'd have to dig out some old notes if I can find them. Michael Hardy 23:30, 19 April 2007 (UTC)


It would be great if we knew : even on the torus, the answer is not known, except that the obstruction set has more than 16889 members... F3etoiles (talk) 12:30, 21 March 2008 (UTC)