This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
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
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)
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)
This article says the following sets of finite graphs are downwardly closed:
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)
For many of these classes, the forbidden minors are known:
I'm not sure if this information is really relevant to the page, honestly. But many of the excluded minors are known. Pkiverson ( talk) 07:35, 16 March 2009 (UTC)
Does anyone know if R-S theorem allows for graphs with loops (i.e., graphs with edges going in and out from the same vertex)?
Are the results still valid for directed graphs? And for multigraphs?
Thanks, Jose Brox âPreceding unsigned comment added by 88.0.102.184 ( talk) 22:08, 7 April 2009 (UTC)
We can simply enumerate all obstruction sets until the right one is found. Since it always exists, this can be done in finite time. Now the algorithm is constructive. The only problem is whether we can recognize the right obstruction set when we see it. Wangzirui ( talk) 16:00, 3 January 2011 (UTC)
Can we remove the phrase âin the size of the larger graphâ, from the run-time? The two inputs are the graph-to-check, and G, the minor-to-check-for. But isn't G considered fixed, since there is also âcontains a constant factor in this polynomial that depends superpolynomially on the size of Gâ? [This seems pretty clear to me, but since I haven't read/understood the original result, I'll leave this for somebody who has. If I am missing something obvious, my apologies. If it's something non-obvious, that might be worth a clarification as well.] not-just-yeti ( talk) 14:35, 10 January 2023 (UTC)
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
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
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)
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)
This article says the following sets of finite graphs are downwardly closed:
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)
For many of these classes, the forbidden minors are known:
I'm not sure if this information is really relevant to the page, honestly. But many of the excluded minors are known. Pkiverson ( talk) 07:35, 16 March 2009 (UTC)
Does anyone know if R-S theorem allows for graphs with loops (i.e., graphs with edges going in and out from the same vertex)?
Are the results still valid for directed graphs? And for multigraphs?
Thanks, Jose Brox âPreceding unsigned comment added by 88.0.102.184 ( talk) 22:08, 7 April 2009 (UTC)
We can simply enumerate all obstruction sets until the right one is found. Since it always exists, this can be done in finite time. Now the algorithm is constructive. The only problem is whether we can recognize the right obstruction set when we see it. Wangzirui ( talk) 16:00, 3 January 2011 (UTC)
Can we remove the phrase âin the size of the larger graphâ, from the run-time? The two inputs are the graph-to-check, and G, the minor-to-check-for. But isn't G considered fixed, since there is also âcontains a constant factor in this polynomial that depends superpolynomially on the size of Gâ? [This seems pretty clear to me, but since I haven't read/understood the original result, I'll leave this for somebody who has. If I am missing something obvious, my apologies. If it's something non-obvious, that might be worth a clarification as well.] not-just-yeti ( talk) 14:35, 10 January 2023 (UTC)