Teorema de los árboles de Kruskal

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada.
Busca fuentes: «Teorema de los árboles de Kruskal» – noticias · libros · académico · imágenes
Puedes avisar al redactor principal pegando lo siguiente en su página de discusión: {{sust:Aviso referencias|Teorema de los árboles de Kruskal}} ~~~~
Este aviso fue puesto el 26 de diciembre de 2024.

En matemáticas, el teorema de los árboles de Kruskal indica que el conjunto de árboles 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).

Lema de Higman 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 teorema de Robertson-Seymour.

Forma finita de Friedman

Friedman (2002) observó que el árbol teorema de Kruskal tiene casos especiales que se pueden exponer, pero no resultaron en primer orden la aritmética (a pesar de que fácilmente pueden ser probadas en segundo orden aritmética). Otra declaración similar es el teorema de París-Harrington.

Supongamos que P(n) es la declaración

Hay algo de m tal que si T1,...,Tm es una secuencia finita de árboles donde Tk tiene k+n vértices, a continuación, Ti ≤ Tj para algunos i < j.

Esto es esencialmente un caso especial del teorema de Kruskal, donde se especifica el tamaño del primer árbol, y los árboles están obligado a crecer en tamaño en la tasa de crecimiento no trivial más simple. Para cada n, la aritmética de Peano puede demostrar que P(n) es cierto, pero la aritmética de Peano no puede probar la afirmación "P(n) es verdadera para todo n". Además, la prueba más corta de P(n) en la aritmética de Peano crece extraordinariamente rápido como una función de n; mucho más rápido que cualquier función recursiva primitiva o la función de Ackermann, por ejemplo.

Friedman también probó la siguiente forma finita del teorema de Kruskal para los árboles etiquetados sin fin entre los hermanos, parametrización del tamaño del conjunto de etiquetas en lugar de en el tamaño del primer árbol en la secuencia (y la incorporación homeomorfo, ≤, siendo ahora INF-y la etiqueta de preservación):

Para cada n, hay una tan grande que m si T1,...,Tm es una secuencia finita de árboles con vértices etiquetados a partir de un conjunto de n etiquetas, donde cada Ti tiene en la mayoría de los vértices i, a continuación, Ti ≤ Tj para algunos i < j.

Este último teorema asegura la existencia de una función de rápido crecimiento que Friedman llama ÁRBOL, de tal manera que ÁRBOL(n) es la longitud de una secuencia más larga de n marcado con árboles T1,...,Tm en el que cada Ti tiene en la mayoría de i vértices , y ningún árbol es integrable en un árbol después.

La secuencia ÁRBOL comienza ÁRBOL(1) = 1, ÁRBOL(2) = 3, entonces de repente ÁRBOL(3) explota a un valor tan enormemente grande que muchos otros "grandes" constantes combinatorios, como de Friedman n(4), son extremadamente pequeño en comparación. Una cota inferior para n(4), y por lo tanto una muy débil cota inferior para el ÁRBOL(3), es A(A(...A(1)...)), donde el número de As es A(187196), y A() es una versión de la función de Ackermann: A(x) = 2 [x + 1] x en hiperoperación. Número de Graham, por ejemplo, es de aproximadamente A64(4), que es mucho menor que el límite inferior AA(187196)(1). Se puede demostrar que la tasa de crecimiento del ÁRBOL de funciones sea superior al de la fΓ0 función en la jerarquía de rápido crecimiento, donde Γ0 es el ordinal Feferman-Schütte.

El ordinal que mide la fuerza del teorema de Kruskal es el pequeño ordinal Veblen (a veces confundido con el ordinal Ackermann más pequeño).

Read other articles:

Birthday (lagu Katy Perry)

BirthdaySingel oleh Katy Perrydari album PrismDirilis21 April 2014GenreDiskoDurasi3:35LabelCapitolPencipta Katy Perry Lukasz Gottwald Max Martin Bonnie McKee Henry Walter Produser Dr. Luke Max Martin Cirkut Kronologi singel Katy Perry Dark Horse (2013) Birthday (2014) This Is How We Do (2014) Video musikBirthday di YouTube Birthday adalah lagu oleh penyanyi asal Amerika Serikat Katy Perry dari album studio keempatnya, Prism (2013). Perry ikut menulis lagu ini bersama Bonnie McKee dan produser...

 

A.F.H. Rosenow

Letnan Kolonel Pelaut (Purn.)A.F.H. Rosenow KRI Dewaruci 1 Informasi pribadiLahir1892Prusia, JermanMeninggal1966Kebangsaan Indonesia Jerman BelandaKarier militerPihak Jerman Indonesia Hindia Belanda JepangDinas/cabang Kriegsmarine TNI Angkatan LautPangkat Letnan KolonelSatuanKorps PelautPertempuran/perangPerang Dunia 1Perang Dunia 2Revolusi Nasional IndonesiaSunting kotak info • L • B Letkol Pelaut (Purn.) August Friederich Hermann Rosenow ...

 

So Dear to My Heart

1948 film by Walt Disney So Dear to My HeartTheatrical release posterDirected byHarold D. SchusterHamilton LuskeWritten by Ken Anderson John Tucker Battle Marc Davis Bill Peet Maurice Rapf Ted Sears Based onMidnight and Jeremiah by Sterling NorthProduced byWalt DisneyPerce PearceStarring Burl Ives Beulah Bondi Harry Carey Luana Patten Bobby Driscoll CinematographyWinton C. HochEdited byLloyd L. RichardsonThomas ScottMusic byPaul SmithProductioncompanyWalt Disney ProductionsDistributed byRKO R...

ضاحية يارين

ضاحية يارين (بالناورونية: Yaren)‏   خريطة الموقع تقسيم إداري البلد ناورو  [1] عاصمة لـ ناورو[2]  خصائص جغرافية إحداثيات 0°32′52″S 166°55′15″E / 0.5477°S 166.920867°E / -0.5477; 166.920867   المساحة 1.5 كيلومتر مربع  الارتفاع 25 متر  السكان التعداد السكاني 747 (2011)[3&#...

 

Peternakan pabrik

Pertanian Umum Agribisnis Agroindustri Agronomi Ilmu pertanian Jelajah bebas Kebijakan pertanian Lahan usaha tani Mekanisasi pertanian Menteri Pertanian Perguruan tinggi pertanian Perguruan tinggi pertanian di Indonesia Permakultur Pertanian bebas ternak Pertanian berkelanjutan Pertanian ekstensif Pertanian intensif Pertanian organik Pertanian urban Peternakan Peternakan pabrik Wanatani Sejarah Sejarah pertanian Sejarah pertanian organik Revolusi pertanian Arab Revolusi pertanian Inggris Revo...

 

Gereja Katolik di Skotlandia

Gereja Katolik di Skotlandiabahasa Gaelik Skotlandia: An Eaglais Chaitligeach ann an AlbaPenyaliban Santo Andreas, karya Juan Correa de Vivar (1540–1545)PenggolonganGereja Katolik RomaOrientasiLatinKitab suciAlkitabTeologiTeologi KatolikBentukpemerintahanKebijakan episkopalBadanpemerintahanBCOSPausPaus FransiskusPresidenHugh GilbertNunsius ApostolikClaudio GugerottiWilayah SkotlandiaBahasaInggris Skot, LatinPendiriSanto Ninian, Santo Mungo, Santo KolumbaDidirikankira-kira tahun 200...

Sikorsky S-62

S-62 / HH-52A Seaguard A U.S. Coast Guard HH-52A Seaguard using a rescue basket Jenis SAR/utility helicopter Pembuat Sikorsky Aircraft Penerbangan perdana 1959 Diperkenalkan 1961 Pengguna utama United States Coast Guard Jumlah 175 Sikorsky S-62 adalah helikopter amfibi, mesin turbin tunggal, tiga-blade rotor awalnya dikembangkan sebagai usaha komersial oleh Sikorsky Aircraft Corporation of Stratford, Connecticut. Helikopter ini digunakan oleh Penjaga Pantai Amerika Serikat sebagai Seagu...

 

Aloys Grillmeier

Aloys Grillmeier, S.J.Kardinal Diaken San Nicola in CarcereAwal masa jabatan26 November 1994Masa jabatan berakhir13 September 1998PendahuluPatrick Aloysius O'BoylePenerusZenon GrocholewskiImamatTahbisan imam24 Juni 1934Pelantikan kardinal26 November 1994PeringkatKardinal DiakenInformasi pribadiLahir(1910-01-01)1 Januari 1910Pechbrunn, Kerajaan Bayern, Kekaisaran JermanWafat13 September 1998(1998-09-13) (umur 88)Unterhaching, Bayern, JermanMakamPullach im Isartal, Bayern, JermanKewarganeg...

 

Nanda Mathew

Caluadewagey Nanda Mathew (2 February 1940 - 2020) was a Sri Lankan politician. He was a former Governor of Uva Province, Minister of Sports and a member of parliament.[1][2][3] Early life and education Born on 2 February 1940, to Sinhala Nationalist Cyril Mathew, he was educated at the S. Thomas' College, Gurutalawa and S. Thomas' College, Mount Lavinia. He became a land owner and a planter.[4] Political career He was elected to the House of Representatives of...

Islam di Thailand

Islam menurut negara Afrika Aljazair Angola Benin Botswana Burkina Faso Burundi Kamerun Tanjung Verde Republik Afrika Tengah Chad Komoro Republik Demokratik Kongo Republik Kongo Djibouti Mesir Guinea Khatulistiwa Eritrea Eswatini Etiopia Gabon Gambia Ghana Guinea Guinea-Bissau Pantai Gading Kenya Lesotho Liberia Libya Madagaskar Malawi Mali Mauritania Mauritius Maroko Mozambik Namibia Niger Nigeria Rwanda Sao Tome dan Principe Senegal Seychelles Sierra Leone Somalia Somaliland Afrika Selatan ...

 

Pembagian administratif Laos

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

List of mountain peaks of the Rocky Mountains

List of mountain summits of the Rocky Mountains of North America See also: Lists of mountains of the Rocky Mountains Mount Elbert in the Sawatch Range is the highest summit of the Rocky Mountains and the U.S. State of Colorado. This article comprises three sortable tables of major mountain peaks[1] of the Rocky Mountains of North America. The summit of a mountain or hill may be measured in three principal ways: The topographic elevation of a summit measures the height of the summit ab...

Luxembourgish Americans

Americans of Luxembourgish birth or descent This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Luxembourgish Americans – news · newspapers · books · scholar · JSTOR (November 2023) (Learn how and when to remove this template message) Luxembourger AmericansTotal population47,129 (2019)[1]Regions with sig...

 

Tennis Club Juventus

Tennis Club JuventusTennis Segni distintivi Colori sociali Bianco e nero Simboli zebra Dati societari Città Torino Paese  Italia Confederazione ITF Federazione FIT Fondazione 1923 Scioglimento 1949 Presidente Edoardo Agnelli(1923-1935)Enrico Craveri e Giovanni Mazzonis(1935-1936)Emilio de la Forest de Divonne(1936-1941)Piero Dusio(1941-1949) Allenatore informazione sconosciuta Impianto sportivo Campo Juventus(1923-1939)[1]Stadio Tennistico Juventus[2](1942-1949) (5 ...

 

Dewan Perwakilan Rakyat Daerah Kota Kediri

Dewan Perwakilan Rakyat Daerah Kota KediriDewan Perwakilan RakyatKota Kediri2019-2024JenisJenisUnikameral Jangka waktu5 tahunSejarahSesi baru dimulai21 Agustus 2019PimpinanKetuaH. Gus Sunoto Imam Mahmudi (PDI-P) sejak 28 September 2019 Wakil Ketua IDra. Firdaus (PAN) sejak 28 September 2019 Wakil Ketua IIKatino, A.Md. (Gerindra) sejak 28 September 2019 KomposisiAnggota30Partai & kursi  PDI-P (5)   NasDem (3)   PKB (3)   Hanura (2)  ...

Taioro

Oceanian fermented coconut flesh TaioroAlternative namesKora, MitioreTypeCondimentPlace of originOceaniaRegion or stateCook Islands, Fiji, French Polynesia, TongaMain ingredientsCoconut meat Taioro is a condiment made from the grated flesh of the coconut and allowed to ferment. It is traditional food found throughout the islands of Oceania and is often eaten as an accompaniment to meals. Preparation Taioro is made from the meat of the coconut drupe and allowed to ferment. The flesh from the c...

 

Post common envelope binary

Binary system consisting of a white dwarf and a main sequence star or a brown dwarf HD 101584 is a suspected post-common envelope binary. The engulfed companion triggered an outflow of gas, creating the nebula seen by ALMA. Key stages in a common envelope phase. Top: A star fills its Roche lobe. Middle: The companion is engulfed; the core and companion spiral towards one another inside a common envelope. Bottom: The envelope is ejected and forms a PCEB or the two stars merge. A post-common en...

 

Bản mẫu:Vòng loại giải vô địch bóng đá thế giới 2018 khu vực châu Âu (Bảng I)

VT Độixts ST T H B BT BB HS Đ Giành quyền tham dự 1  Iceland 10 7 1 2 16 7 +9 22 Vượt qua vòng loại vàoFIFA World Cup 2018 2  Croatia 10 6 2 2 15 4 +11 20 Giành quyền vào vòng 2 3  Ukraina 10 5 2 3 13 9 +4 17 4  Thổ Nhĩ Kỳ 10 4 3 3 14 13 +1 15 5  Phần Lan 10 2 3 5 9 13 −4 9 6  Kosovo 10 0 1 9 3 24 −21 1 Nguồn: FIFAQuy tắc xếp hạng: Các tiêu chí vòng loại Để chỉnh sửa các bảng xếp hạng: Bảng A,...

Max Planck

Untuk satuan yang dinamakan menurut tokoh ini, lihat Satuan Planck. Max Karl PlanckPlanck di tahun 1930LahirMax Karl Ernst Ludwig Planck(1858-04-23)23 April 1858Kiel, Kadipaten HolsteinMeninggal4 Oktober 1947(1947-10-04) (umur 89)Göttingen, Lower Saxony, Bizone, Pendudukan Jerman oleh SekutuPendidikanUniversitas Ludwig Maximilian München, (PhD, 1879)AlmamaterUniversitas Ludwig Maximilian MünchenSuami/istri Marie Merck ​ ​(m. 1887; meninggal 1909&#...

 

Sungai Merah (Asia)

Sungai HongSông Hồng (di Vietnam), Yuanjiang (元江) atau Hóng Hé (红河) (di Tiongkok)Sông Thao, Hồng Hà, Nhị Hà,Nhĩ Hà, Sông Cái, Nguyên GiangLokasiCountryTiongkok, VietnamProvinsiYunnan, Provinsi Lào Cai, Provinsi Yên Bái, Provinsi Phú Thọ, Hanoi, Provinsi Vĩnh Phúc, Provinsi Hưng Yên, Provinsi Hà Nam, Provinsi Thái Bình, Provinsi Nam ĐịnhCiri-ciri fisikHulu sungai  - lokasiPegunungan Hengduan - elevasi1.776 m (5.827 ft)...