Talk:Robertson–Seymour theorem

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

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)

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)

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)

For many of these classes, the forbidden minors are known:

• Disjoint union of paths: exclude K_{1,3} (easy)
• Forests: exclude K_3 (easy)
• Planar graphs: exclude K_5, K_{3,3} (Kuratowski's Theorem)
• Outerplanar graphs: exclude K_4, K_{2,3} (follows easily from Kuratowski's)
• Torus: unknown -> many
• Any surface: The only surface besides the sphere with a known list is the projective plane. There are 35 excluded minors. See Dan Archdeacon's homepage.
• Knotlessly embeddable: unknown
• Linklessly embeddable: The 7 graphs in the Peterson family (Robertson, Seymour, Thomas)

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)

Generalizations?

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)

Non-constructive?

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)

It may be "the only problem", but it is a problem, one that prevents this from being an algorithm and from being constructive. —David Eppstein (talk) 20:05, 3 January 2011 (UTC)

Polynomial time recognition

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)

It is not a polynomial time algorithm. When measured in terms of the size of its entire input (G and the supposed minor), it takes more than polynomial time. The minor does not have to be of bounded size. So no, this would be inaccurate. More technically this is fixed-parameter tractable (FPT), not polynomial (P). —David Eppstein (talk) 16:09, 10 January 2023 (UTC)

Thanks. As the section is written, it definitely seems to be fixing the minor-to-check-for: “for each fixed graph G, there is a polynomial time algorithm for testing whether larger graphs have G as a minor.” My confusion had been the phrase "this algorithm's runtime is cubic in the **larger** graph", I now think they wrote “larger” just to mean the algorithm's input, rather than meaning "cubic in max(|G|,|input|)" [which isn't sensible if G once G is fixed, which is why I was confused].

[Btw, using `G` to mean the (fixed) minor, and not the input-graph, is confusing; I'll clean that up.]

About the non-constructive nature: When the next paragraph says

> “the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it.”

I'm *thinking* that “the problem” suddenly means “given a set of graphs, is it closed under minors?” (and no longer meaning the algorithm “for fixed G, finding if a graph contains G as a minor”).

In that case, it's easy to see that the cubic algorithm doesn't constructively solve "is a set of graphs closed under minors".

But if I'm misunderstanding, and the situation is actually worse — “For an arbitrary fixed graph G, we don't know how to feasibly produce the algorithm for `contains-G-as-minor`”, then please let me know!, and I'll take a stab at clarifying that.

not-just-yeti (talk) 17:37, 10 January 2023 (UTC)

The algorithm is for testing membership of a graph G in a minor-closed family F, not for testing whether a family F is minor-closed. The algorithm is: for each obstruction H for F, test whether H is a minor of G. That part is concrete. The part that is not concrete is listing the obstructions for F. —David Eppstein (talk) 17:51, 10 January 2023 (UTC)