About: Kruskal's tree theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Kruskal's tree theorem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Theorem106752293, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FKruskal%27s_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.

Attributes	Values
rdf:type	yago:WikicatLargeNumbers yago:WikicatTheoremsInDiscreteMathematics yago:Abstraction100002137 yago:Battalion113775093 yago:Communication100033020 yago:IndefiniteQuantity113576355 yago:LargeIndefiniteQuantity113757724 yago:Measure100033615 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293
rdfs:label	Satz von Kruskal (de) Teorema de los árboles de Kruskal (es) Théorème de Kruskal (fr) Kruskal's tree theorem (en) Teoria Drzew Kruskala (pl) Теорема Краскала (ru) 克魯斯卡爾樹定理 (zh)
rdfs:comment	Der Satz von Kruskal ist ein Lehrsatz der Graphentheorie, eines der Teilgebiete der Mathematik. Er wurde von dem Mathematiker Joseph Bernard Kruskal im Jahre 1960 publiziert. Der Satz behandelt eine wichtige Eigenschaft der Klasse der endlichen Bäume. (de) En matemáticas, el árbol teorema de Kruskal indica que el conjunto de finitos más de un conjunto bien cuasi-ordenada de las etiquetas es en sí misma bien cuasi-ordenado (bajo incrustación homeomorfo). El teorema fue conjeturado por Andrew Vázsonyi y demostró por Joseph Kruskal (1960); una breve prueba fue dada por Nash-Williams (1963). es un caso especial de este teorema, de las cuales hay muchas generalizaciones que implican árboles con una incrustación plana, árboles infinitos, y así sucesivamente. Una generalización de los árboles a los gráficos arbitrarias está dado por el . (es) 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. (en) En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre. Ce théorème est un cas particulier du théorème de Robertson-Seymour, dont il a constitué une des motivations. En utilisant ce théorème, Harvey Friedman a pu définir des entiers « incompréhensiblement grands », qu'il a utilisé pour obtenir des résultats nouveaux d'indécidabilité. (fr) W matematyce Teoria Drzew Kruskala jest jednym z problemów w teorii grafów i . Mówi ona, iż skończony zbiór drzew z uporządkowanymi zasadami tworzenia jest homeomorficzny. Twierdzenie to zostało zaprezentowane przez – węgierskiego matematyka, a udowodnione przez Josepha Kruskala (1960) oraz (1963). Od tego czasu stał się znaczącym przykładem w jako stwierdzenie, którego nie można udowodnić używając ATR0 (forma arytmetycznej rekurencji transfinitowej), a finalne zastosowanie tego twierdzenia umożliwia konstrukcję bardzo szybko rosnącej funkcji TREE(n) (ang. tree – drzewo). (pl)
dcterms:subject	Order theory Trees (graph theory) Theorems in discrete mathematics Mathematical logic Wellfoundedness
Wikipage page ID	3606300 (xsd:integer)
Wikipage revision ID	1124400522 (xsd:integer)
Link from a Wikipage to another Wikipage	Primitive recursive function Paris–Harrington theorem Andrew Vázsonyi Peano axioms Reverse mathematics Kőnig's lemma Robertson–Seymour theorem Order theory Mathematics Ordinal analysis Friedman's SSCG function Kruskal's tree theorem Trees (graph theory) Tree (graph theory) Well-quasi-ordering Harvey Friedman Theorems in discrete mathematics Partially ordered set Fast-growing hierarchy Goodstein's theorem Graham's number Kanamori–McAloon theorem Ackermann function Ackermann ordinal Mathematical logic Homeomorphism (graph theory) Wellfoundedness Impredicativity Small Veblen ordinal Second-order arithmetic Finitary Arithmetical transfinite recursion Ackermann's function
Link from a Wikipage to an external page	https://users.dimi.uniud.it/~alberto.marcone/wqobqo.pdf http://www.cis.upenn.edu/~jean/kruskal.pdf%7Cdoi=10.1016/0168-0072(91)90022-E%7Cdoi-access=free https://www.ams.org/journals/tran/1960-095-02/S0002-9947-1960-0111704-1/S0002-9947-1960-0111704-1.pdf
sameAs	Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem Kruskal's tree theorem
txt	yes (en)
dbp:wikiPageUsesTemplate	dbt:Better_source_needed dbt:Citation dbt:Citation_needed dbt:Cite_journal dbt:Large_numbers dbt:Math dbt:Mvar dbt:Note_label dbt:Ref_label dbt:Reflist dbt:Short_description dbt:Su dbt:Harvs
authorlink	Crispin St. J. A. Nash-Williams (en) Joseph Kruskal (en)
b	1 (xsd:integer)
date	July 2020 (en)
first	Joseph (en) Crispin (en)
last	Kruskal (en) Nash-Williams (en)

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 38 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software