 Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem^{[1]}) states that the undirected graphs, partially ordered by the graph minor relationship, form a wellquasiordering.^{[2]} Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K_{5} and the complete bipartite graph K_{3,3} as minors.
The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004.^{[3]} Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it.^{[4]}
A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal and S. Tarkowski.^{[5]}
Contents
Statement
A minor of an undirected graph G is any graph that may be obtained from G by a sequence of zero or more contractions of edges of G and deletions of edges and vertices of G. The minor relationship forms a partial order on the set of all distinct finite undirected graphs, as it obeys the three axioms of partial orders: it is reflexive (every graph is a minor of itself), transitive (a minor of a minor of G is itself a minor of G), and antisymmetric (if two graphs G and H are minors of each other, then they must be isomorphic). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a preorder, a relation that is reflexive and transitive but not necessarily antisymmetric.^{[6]}
A preorder is said to form a wellquasiordering if it contains neither an infinite descending chain nor an infinite antichain.^{[7]} For instance, the usual ordering on the nonnegative integers is a wellquasiordering, but the same ordering on the set of all integers is not, because it contains the infinite descending chain 0, −1, −2, −3...
The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a wellquasiordering. It is obvious that the graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a nonnegative integer).^{[8]} The nontrivial part of the theorem is that there are no infinite antichains, infinite sets of graphs that are all unrelated to each other by the minor ordering. If S is a set of graphs, and M is a subset of S containing one representative graph for each equivalence class of minimal elements (graphs that belong to S but for which no proper minor belongs to S), then M forms an antichain; therefore, an equivalent way of stating the theorem is that, in any infinite set S of graphs, there must be only a finite number of nonisomorphic minimal elements.
Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of the other.^{[8]} The statement that every infinite set has finitely many minimal elements implies this form of the theorem, for if there are only finitely many minimal elements, then each of the remaining graphs must belong to a pair of this type with one of the minimal elements. And in the other direction, this form of the theorem implies the statement that there can be no infinite antichains, because an infinite antichain is a set that does not contain any pair related by the minor relation.
Forbidden minor characterizations
A family F of graphs is said to be closed under the operation of taking minors if every minor of a graph in F also belongs to F. If F is a minorclosed family, then let S be the set of graphs that are not in F (the complement of F). According to the Robertson–Seymour theorem, there exists a finite set H of minimal elements in S. These minimal elements form a forbidden graph characterization of F: the graphs in F are exactly the graphs that do not have any graph in H as a minor.^{[9]} The members of H are called the excluded minors (or forbidden minors, or minorminimal obstructions) for the family F.
For example, the planar graphs are closed under taking minors: contracting an edge in a planar graph, or removing edges or vertices from the graph, cannot destroy its planarity. Therefore, the planar graphs have a forbidden minor characterization, which in this case is given by Wagner's theorem: the set H of minorminimal nonplanar graphs contains exactly two graphs, the complete graph K_{5} and the complete bipartite graph K_{3,3}, and the planar graphs are exactly the graphs that do not have a minor in the set {K_{5}, K_{3,3}}.
The existence of forbidden minor characterizations for all minorclosed graph families is an equivalent way of stating the Robertson–Seymour theorem. For, suppose that every minorclosed family F has a finite set H of minimal forbidden minors, and let S be any infinite set of graphs. Define F from S as the family of graphs that do not have a minor in S. Then F is minorclosed and the finite set H of minimal forbidden minors in F must be exactly the minimal elements in S, so S must have only a finite number of minimal elements.
Examples of minorclosed families
Main article: Forbidden graph characterizationThe following sets of finite graphs are minorclosed, and therefore (by the Robertson–Seymour theorem) have forbidden minor characterizations:
 forests, linear forests (disjoint unions of path graphs), pseudoforests, and cactus graphs;
 planar graphs, outerplanar graphs, apex graphs (formed by adding a single vertex to a planar graph), toroidal graphs, and the graphs that can be embedded on any fixed twodimensional manifold;^{[10]}
 graphs that are linklessly embeddable in Euclidean 3space, and graphs that are knotlessly embeddable in Euclidean 3space;^{[10]}
 graphs with a feedback vertex set of size bounded by some fixed constant; graphs with Colin de Verdière graph invariant bounded by some fixed constant; graphs with treewidth, pathwidth, or branchwidth bounded by some fixed constant.
Obstruction sets
Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson–Seymour theorem was proved. For example, the obstruction for the set of all forests is the loop graph (or, if one restricts to simple graphs, the cycle with three vertices). This means that a graph is a forest if and only if none of its minors is the loop (or, the cycle with three vertices, respectively). The sole obstruction for the set of paths is the tree with four vertices, one of which has degree 3. In these cases, the obstruction set contains a single element, but in general this is not the case. Wagner's theorem states that a graph is planar if and only if it has neither K_{5} nor K_{3,3} as a minor. In other words, the set {K_{5}, K_{3,3}} is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that K_{4} and K_{2,3} are the forbidden minors for the set of outerplanar graphs.
Although the Robertson–Seymour theorem extends these results to arbitrary minorclosed graph families, it is not a complete substitute for these results, because it does not provide an explicit description of the obstruction set for any family. For example, it tells us that the set of toroidal graphs has a finite obstruction set, but it does not provide any such set. The complete set of forbidden minors for toroidal graphs remains unknown, but contains at least 16000 graphs.^{[11]}
Polynomial time recognition
The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph G, there is a polynomial time algorithm for testing whether larger graphs have G as a minor. The running time of this algorithm can be expressed as a cubic polynomial in the size of the larger graph (although there is a constant factor in this polynomial that depends superpolynomially on the size of G). As a result, for every minorclosed family F, there is polynomial time algorithm for testing whether a graph belongs to F: simply check, for each of the forbidden minors for F, whether the given graph contains that forbidden minor.^{[12]}
However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomialtime algorithm for solving it. Such proofs of polynomiality are nonconstructive: they prove polynomiality of problems without providing an explicit polynomialtime algorithm.^{[13]} In many specific cases, checking whether a graph is in a given minorclosed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.
Fixedparameter tractability
For graph invariants with the property that, for each k, the graphs with invariant at most k are minorclosed, the same method applies. For instance, by this result, treewidth, branchwidth, and pathwidth, vertex cover, and the minimum genus of an embedding are all amenable to this approach, and for any fixed k there is a polynomial time algorithm for testing whether these invariants are at most k, in which the exponent in the running time of the algorithm does not depend on k. A problem with this property, that it can be solved in polynomial time for any fixed k with an exponent that does not depend on k, is known as fixedparameter tractable.
However, this method does not directly provide a single fixedparametertractable algorithm for computing the parameter value for a given graph with unknown k, because of the difficulty of determining the set of forbidden minors. Additionally, the large constant factors involved in these results make them highly impractical. Therefore, the development of explicit fixedparameter algorithms for these problems, with improved dependence on k, has continued to be an important line of research.
Finite form of the graph minor theorem
Friedman, Robertson & Seymour (1987) showed that the following theorem exhibits the independence phenomenon by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:
 Theorem: For every positive integer n, there is an integer m so large that if G_{1}, ..., G_{m} is a sequence of finite undirected graphs,
 where each G_{i} has size at most n+i, then G_{j} ≤ G_{k} for some j < k.
(Here, the size of a graph is the total number of its nodes and edges, and ≤ denotes the minor ordering.)
See also
 Graph structure theorem
Notes
 ^ Bienstock & Langston (1995).
 ^ Robertson & Seymour (2004).
 ^ Robertson and Seymour (1983, 2004); Diestel (2005, p. 333).
 ^ Diestel (2005, p. 355).
 ^ Diestel (2005, pp. 335–336); Lovász (2005), Section 3.3, pp. 78–79.
 ^ E.g., see Bienstock & Langston (1995), Section 2, "wellquasiorders".
 ^ Diestel (2005, p. 334).
 ^ ^{a} ^{b} Lovász (2005, p. 78).
 ^ Bienstock & Langston (1995), Corollary 2.1.1; Lovász (2005), Theorem 4, p. 78.
 ^ ^{a} ^{b} Lovász (2005, pp. 76–77).
 ^ Chambers (2002).
 ^ Robertson & Seymour (1995); Bienstock & Langston (1995), Theorem 2.1.4 and Corollary 2.1.5; Lovász (2005), Theorem 11, p. 83.
 ^ Fellows & Langston (1988); Bienstock & Langston (1995), Section 6.
References
 Bienstock, Daniel; Langston, Michael A. (1995), "Algorithmic implications of the graph minor theorem", Network Models, Handbooks in Operations Research and Management Science, 7, pp. 481–502, doi:10.1016/S09270507(05)801252, http://www.cs.utk.edu/~langston/courses/cs594fall2003/BL.pdf.
 Chambers, J. (2002), Hunting for torus obstructions, M.Sc. thesis, Department of Computer Science, University of Victoria.
 Diestel, Reinhard (2005), "Minors, Trees, and WQO", Graph Theory (Electronic Edition 2005 ed.), Springer, pp. 326–367, http://www.math.unihamburg.de/home/diestel/books/graph.theory/preview/Ch12.pdf.
 Fellows, Michael R.; Langston, Michael A. (1988), "Nonconstructive tools for proving polynomialtime decidability", Journal of the ACM 35 (3): 727–739, doi:10.1145/44483.44491.
 Friedman, Harvey; Robertson, Neil; Seymour, Paul (1987), "The metamathematics of the graph minor theorem", in Simpson, S., Logic and Combinatorics, Contemporary Mathematics, 65, American Mathematical Society, pp. 229–261.
 Lovász, László (2005), "Graph Minor Theory", Bulletin of the American Mathematical Society (New Series) 43 (1): 75–86, doi:10.1090/S0273097905010888.
 Robertson, Neil; Seymour, Paul (1983), "Graph Minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B 35 (1): 39–61, doi:10.1016/00958956(83)900795.
 Robertson, Neil; Seymour, Paul (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B 63 (1): 65–110, doi:10.1006/jctb.1995.1006.
 Robertson, Neil; Seymour, Paul (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.
External links
Categories: Graph minor theory
 Wellfoundedness
 Theorems in discrete mathematics
Wikimedia Foundation. 2010.
Look at other dictionaries:
Théorème de RobertsonSeymour — En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour (parfois également appelé le théorème des mineurs, et connu, avant qu il soit démontré, sous le nom de conjecture de Wagner), est un théorème démontré… … Wikipédia en Français
Neil Robertson (mathematician) — Neil Robertson Born November 30, 1938 Canada Residence United States, Canada N … Wikipedia
Paul Seymour — Paul Seymour. Paul D. Seymour (* 26. Juli 1950 in Plymouth) ist ein englischer Mathematiker, der wichtige Beiträge zur Kombinatorik lieferte. Leben und Werk Seymour besuchte die Schule in Plymouth und studierte, nachdem er im landesweiten… … Deutsch Wikipedia
Paul Seymour (mathematician) — This article is about the mathematician. For other people with the same name, see Paul Seymour (disambiguation). Paul Seymour Residence … Wikipedia
Kruskal's tree theorem — In mathematics, Kruskal s tree theorem states that the set of finite trees over a well quasi ordered set of labels is itself well quasi ordered (under homeomorphic embedding). The theorem was proved byharvstxt=yesyear= 1960 authorlink=Joseph… … Wikipedia
Four color theorem — Example of a four colored map A four colori … Wikipedia
VierFarbenTheorem — Der Vier Farben Satz (früher auch als Vier Farben Vermutung oder Vier Farben Problem bekannt) ist ein mathematischer Satz und besagt, dass vier Farben immer ausreichen, um eine beliebige Landkarte in der euklidischen Ebene so einzufärben, dass… … Deutsch Wikipedia
Five color theorem — The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent… … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
Matroid — In combinatorics, a branch of mathematics, a matroid ( /ˈmeɪ … Wikipedia