Robertson–Seymour theorem (original) (raw)
Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung.
| Property | Value |
|---|---|
| dbo:abstract | Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung. (de) En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. Le théorème de Robertson–Seymour est également appelé le théorème des mineurs, car le classement partiel évoqué dans son énoncé est défini par la relation « être un mineur ». Le théorème équivaut ainsi à dire que toute famille F de graphes fermée, c'est-à-dire telle que les mineurs des graphes de F appartiennent aussi à F, peut être caractérisée par un ensemble fini de « mineurs exclus ». Connu, avant qu'il soit démontré, sous le nom de conjecture de Wagner, ce théorème, démontré en 2004 par Neil Robertson et Paul Seymour, est considéré généralement comme un des résultats les plus importants de la théorie des graphes. Il a une démonstration extrêmement complexe et délicate, dont la publication, comportant plus de cinq cents pages, s'étale de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory. Le théorème n'est pas constructif (on ne connait d'ailleurs les listes explicites de mineurs exclus que dans très peu de cas), mais Robertson et Seymour ont montré qu'il a d'importantes conséquences en théorie de la complexité, car il garantit l'existence d'algorithmes rapides pour de nombreux problèmes de décision. (fr) In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. 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 K5 or the complete bipartite graph K3,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. 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. 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. (en) In teoria dei grafi il teorema di Robertson-Seymour costituisce unageneralizzazione di ampia portata del considerato comeaffermazione che e sono "minori proibiti"per i grafi planari. (it) Na teoria dos grafos, o teorema de Robertson–Seymour (também chamado teorema menor dos grafos) estabelece que os grafos não direcionados, parcialmente ordenados pelo relacionamento do , formam um . (pt) Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов. Например, множество планарных графов замкнуто по операциям удаления и стягивания рёбер; запрещёнными графами в этом случае являются полный граф K5 и полный двудольный граф K3,3. Последнее утверждение называется теоремой Вагнера и тесно связано с теоремой Понтрягина — Куратовского. Теорема широко известна элементарностью формулировки при отсутствии простого доказательства. Она носит имя Нила Робертсона и Пола Сеймура, которые доказали её в серии из двадцати статей общим объёмом в 500 страниц, вышедших с 1983 по 2004 годы. До доказательства утверждение теоремы было известно как гипотеза Вагнера, хотя сам Вагнер утверждал, что он никогда не высказывал этой гипотезы. Более слабое утверждение для деревьев следует из теоремы Краскала о деревьях. Утверждение было высказано в виде гипотезы в 1937 году венгерским математиком Эндрю Важоньи и доказано в 1960 независимо Джозефом Краскалом и С. Тарковским. (ru) Теорема Робертсона — Сеймура (також звана теоремою про мінори графа) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів. Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського. Теорема широко відома елементарністю формулювання за відсутності простого доведення. Вона носить ім'я і , які довели її в серії з двадцяти статей загальним обсягом 500 сторінок, що вийшли від 1983 до 2004 року. До доведення твердження теорема була відомою як гіпотеза Вагнера, хоча сам стверджував, що він ніколи не висловлював цієї гіпотези. Слабше твердження для дерев випливає з . Твердження 1937 року висловив у вигляді гіпотези угорський математик і довели 1960 року незалежно і С. Тарковським. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen_family.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch12.pdf http://research.nii.ac.jp/~k_keniti/quaddp1.pdf%7C https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p16 |
| dbo:wikiPageID | 351769 (xsd:integer) |
| dbo:wikiPageLength | 19365 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123036750 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbr:Minor_(graph_theory) dbr:Andrew_Vázsonyi dbr:Antichain dbc:Graph_minor_theory dbr:Joseph_Kruskal dbr:Path_graph dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:Peano_arithmetic dbr:Undirected_graph dbr:Independence_(mathematical_logic) dbr:Infinite_descending_chain dbr:Pseudoforest dbr:Complement_(set_theory) dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Graph_(discrete_mathematics) dbr:Graph_structure_theorem dbr:Antisymmetric_relation dbr:Apex_graph dbr:Linkless_embedding dbr:Cactus_graph dbr:Closure_(mathematics) dbr:Feedback_vertex_set dbr:Kruskal's_tree_theorem dbr:Transitive_relation dbr:Tree_(graph_theory) dbr:Treewidth dbr:Well-quasi-ordering dbr:American_Mathematical_Society dbr:Forbidden_graph_characterization dbr:Outerplanar_graph dbr:Graph_embedding dbr:Graph_isomorphism dbr:Graph_theory dbr:Journal_of_the_ACM dbc:Theorems_in_graph_theory dbr:Fixed-parameter_tractable dbr:Colin_de_Verdière_graph_invariant dbr:Toroidal_graph dbr:Branchwidth dbr:ZFC dbr:Disjoint_union dbc:Wellfoundedness dbr:Manifold dbr:Planar_graph dbr:Graph_invariant dbr:Polynomial_time dbr:Knot_(mathematics) dbr:Neil_Robertson_(mathematician) dbr:Reflexive_relation dbr:Non-constructive dbr:Forest_(graph_theory) dbr:Partial_order dbr:Wagner's_theorem dbr:Klaus_Wagner_(mathematician) dbr:Forbidden_minor dbr:Minimal_element dbr:Cubic_polynomial dbr:File:Petersen_family.svg |
| dbp:mode | cs2 (en) |
| dbp:title | Robertson-Seymour Theorem (en) |
| dbp:urlname | Robertson-SeymourTheorem (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Main dbt:Mathworld dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_minor_theory dbc:Theorems_in_graph_theory dbc:Wellfoundedness |
| rdf:type | yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”. Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung. (de) In teoria dei grafi il teorema di Robertson-Seymour costituisce unageneralizzazione di ampia portata del considerato comeaffermazione che e sono "minori proibiti"per i grafi planari. (it) Na teoria dos grafos, o teorema de Robertson–Seymour (também chamado teorema menor dos grafos) estabelece que os grafos não direcionados, parcialmente ordenados pelo relacionamento do , formam um . (pt) En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. (fr) In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. 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 K5 or the complete bipartite graph K3,3 as minors. (en) Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов. Например, множество планарных графов замкнуто по операциям удаления и стягивания рёбер; запрещёнными графами в этом случае являются полный граф K5 и полный двудольный граф K3,3. Последнее утверждение называется теоремой Вагнера и тесно связано с теоремой Понтрягина — Куратовского. (ru) Теорема Робертсона — Сеймура (також звана теоремою про мінори графа) стверджує, що будь-яке сімейство графів, замкнуте відносно операцій видалення і стягування ребер, можна визначити скінченним набором заборонених графів. Наприклад, множина планарних графів замкнута за операціями видалення і стягування ребер; забороненими графами в цьому випадку є повний граф K5 і повний двочастковий граф K3,3. Останнє твердження називається теоремою Вагнера і тісно пов'язане з теоремою Понтрягіна — Куратовського. (uk) |
| rdfs:label | Minorentheorem (de) Teorema di Robertson-Seymour (it) Théorème de Robertson-Seymour (fr) Robertson–Seymour theorem (en) Teorema de Robertson–Seymour (pt) Теорема Робертсона — Сеймура (ru) Теорема Робертсона — Сеймура (uk) |
| owl:sameAs | freebase:Robertson–Seymour theorem wikidata:Robertson–Seymour theorem dbpedia-de:Robertson–Seymour theorem dbpedia-fr:Robertson–Seymour theorem dbpedia-it:Robertson–Seymour theorem dbpedia-pt:Robertson–Seymour theorem dbpedia-ru:Robertson–Seymour theorem dbpedia-uk:Robertson–Seymour theorem https://global.dbpedia.org/id/3Fey9 |
| prov:wasDerivedFrom | wikipedia-en:Robertson–Seymour_theorem?oldid=1123036750&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Petersen_family.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Robertson–Seymour_theorem |
| is dbo:knownFor of | dbr:Neil_Robertson_(mathematician) |
| is dbo:wikiPageRedirects of | dbr:Obstruction_set dbr:Graph_Minor_Theorem dbr:Graph_minor_theorem dbr:Graph_minors_theorem dbr:Robertson-Seymour_theorem dbr:Robertson-Seymour dbr:Robertson-Seymour_Theorem dbr:Robertson-Seymour_graph_minor_theorem dbr:Downwardly_closed dbr:Wagner's_conjecture dbr:Wagner_conjecture |
| is dbo:wikiPageWikiLink of | dbr:Book_embedding dbr:Brandon_University dbr:Andrew_Vázsonyi dbr:Apollonian_network dbr:Julia_Chuzhoy dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:Petersen_family dbr:List_of_long_mathematical_proofs dbr:Pseudoforest dbr:Obstruction_set dbr:Non-constructive_algorithm_existence_proofs dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Graph_structure_theorem dbr:Bounded_expansion dbr:Branch-decomposition dbr:Apex_graph dbr:Linkless_embedding dbr:Combinatorics:_The_Rota_Way dbr:Friedman's_SSCG_function dbr:Frucht's_theorem dbr:Fulkerson_Prize dbr:Halin's_grid_theorem dbr:Kruskal's_tree_theorem dbr:P_(complexity) dbr:Matroid dbr:Matroid_minor dbr:Well-quasi-ordering dbr:Forbidden_graph_characterization dbr:Tree-depth dbr:Hadwiger_conjecture_(graph_theory) dbr:Haven_(graph_theory) dbr:Courcelle's_theorem dbr:Jim_Geelen dbr:Large_numbers dbr:Colin_de_Verdière_graph_invariant dbr:Hereditary_property dbr:Homeomorphism_(graph_theory) dbr:Toroidal_graph dbr:Planar_graph dbr:Graph_Minor_Theorem dbr:Graph_minor_theorem dbr:Graph_minors_theorem dbr:Implicit_graph dbr:Neil_Robertson_(mathematician) dbr:Orders_of_magnitude_(numbers) dbr:Klaus_Wagner dbr:List_of_theorems dbr:List_of_unsolved_problems_in_mathematics dbr:Michael_Langston dbr:Partial_k-tree dbr:Planar_cover dbr:Wagner's_theorem dbr:Robertson-Seymour_theorem dbr:Robertson-Seymour dbr:Robertson-Seymour_Theorem dbr:Robertson-Seymour_graph_minor_theorem dbr:Downwardly_closed dbr:Wagner's_conjecture dbr:Wagner_conjecture |
| is dbp:knownFor of | dbr:Neil_Robertson_(mathematician) |
| is foaf:primaryTopic of | wikipedia-en:Robertson–Seymour_theorem |
