Millikens ağaç teoremi - Millikens tree theorem - Wikipedia

İçinde matematik, Milliken'in ağaç teoremi içinde kombinatorik genelleştiren bir bölüm teoremidir Ramsey teoremi sonsuza ağaçlar, daha fazla yapıya sahip nesneler setleri.

T sonlu bir bölme olsun köklü ağaç yüksekliği ω, n pozitif bir tam sayı ve ${ displaystyle mathbb {S} _ {T} ^ {n}}$ T yüksekliğinin tüm güçlü gömülü alt ağaçlarının toplanması. Basit formlarından birinde Milliken'in ağaç teoremi şunu belirtir: ${ displaystyle mathbb {S} _ {T} ^ {n} = C_ {1} cup ... cup C_ {r}}$ daha sonra güçlü bir şekilde gömülü sonsuz alt ağaç R, T için, ${ displaystyle mathbb {S} _ {R} ^ {n} alt küme C_ {i}}$ bazı i ≤ r için.

Bu hemen ima eder Ramsey teoremi; T ağacını ω köşelerde doğrusal sıralama olarak alın.

Tanımlamak ${ displaystyle mathbb {S} ^ {n} = bigcup _ {T} mathbb {S} _ {T} ^ {n}}$ T, ω yüksekliğindeki sonlu bölünmüş köklü ağaçların üzerinde değişir. Milliken'in ağaç teoremi, sadece ${ displaystyle mathbb {S} ^ {n}}$ normal bölüm her n <ω için, ancak teorem tarafından garanti edilen homojen alt ağaç R, güçlü bir şekilde gömülü T.

Güçlü yerleştirme

T'nin her dalının kardinalitesi α varsa T'ye α-ağacı deyin. Succ (p, P) = tanımlayın ${ displaystyle {q in P: q geq p }}$, ve ${ displaystyle IS (p, P)}$ Diyelim ki, S'nin bir α-ağacı ve T'nin 0 ≤ α ≤ β ≤ ω ile bir β-ağacı olduğunu varsayalım. S güçlü bir şekilde gömülü T cinsinden eğer:

• ${ displaystyle S alt kümesi T}$ve S üzerindeki kısmi düzen T'den indüklenir,
• Eğer ${ displaystyle s S olarak}$ S'de maksimal değildir ve ${ displaystyle t IS (s, T)}$, sonra ${ displaystyle | Succ (t, T) cap IS (s, S) | = 1}$,
• kesinlikle artan bir fonksiyon var ${ displaystyle alpha}$ -e ${ displaystyle beta}$, öyle ki ${ Displaystyle S (n) alt küme T (f (n)).}$

Sezgisel olarak, S'nin T'ye güçlü bir şekilde gömülmesi için,

• S, indüklenen kısmi sırayla T'nin bir alt kümesi olmalıdır
• S, T'nin dallanma yapısını korumalıdır; yani, eğer S'deki maksimal olmayan bir düğüm T'de n hemen ardılına sahipse, S'de n hemen ardılına sahiptir.
• S, T'nin seviye yapısını korur; ortak bir S düzeyindeki tüm düğümler T'de ortak bir düzeyde olmalıdır.

Referanslar

1. Keith R. Milliken, Ağaçlar İçin Bir Ramsey Teoremi J. Comb. Teori (Seri A) 26 (1979), 215-237
2. Keith R. Milliken, Bir Ağacın Sonsuz Alt Ağaçları İçin Bir Bölme Teoremi, Trans. Amer. Matematik. Soc. 263 No. 1 (1981), 137-148.