Millikens daraxtlari teoremasi - Millikens tree theorem - Wikipedia

Yilda matematika, Millikenning daraxt teoremasi yilda kombinatorika umumlashtiruvchi bo'lim teoremasi Ramsey teoremasi cheksizgacha daraxtlar, dan ortiq tuzilishga ega bo'lgan ob'ektlar to'plamlar.

T cheklangan bo'linish bo'lsin ildiz otgan daraxt balandligi ω, n musbat butun son va ${ displaystyle mathbb {S} _ {T} ^ {n}}$ balandlik n balandlikdagi barcha kuchli ko'milgan pastki daraxtlarning to'plami. Oddiy shakllaridan birida Millikenning daraxtlar teoremasi, agar shunday bo'lsa ${ displaystyle mathbb {S} _ {T} ^ {n} = C_ {1} cup ... cup C_ {r}}$ keyin ba'zi bir T-ning mustahkam o'rnatilgan cheksiz pastki daraxti R uchun, ${ displaystyle mathbb {S} _ {R} ^ {n} subset C_ {i}}$ ba'zilar uchun ≤ r.

Bu darhol nazarda tutadi Ramsey teoremasi; $ T $ daraxtini $ vertikal $ vertikal tartibda oling.

Aniqlang ${ displaystyle mathbb {S} ^ {n} = bigcup _ {T} mathbb {S} _ {T} ^ {n}}$ bu erda $ T $ balandlikdagi ildiz otgan daraxtlarni cheklangan ravishda ajratib turadi. Millikenning daraxt teoremasi nafaqat shunday deb aytadi ${ displaystyle mathbb {S} ^ {n}}$ bo'lim muntazam har bir $ n < phi $ uchun, lekin teorema tomonidan kafolatlangan $ R $ bir hil subtree kuchli singdirilgan T.da

Kuchli joylashtirish

Agar T ning har bir shoxida kardinallik al bo'lsa, T a a daraxtini chaqiring. Succ (p, P) = ni aniqlang ${ displaystyle {q in P: q geq p }}$va ${ displaystyle IS (p, P)}$ $ P $ ning zudlik bilan davom etuvchilar to'plami bo'lishini taxmin qilaylik $ S $ a-daraxt, $ T $ $ b-daraxt, $ 0 alpha-n-ph $ bilan. S kuchli singdirilgan agar Tda:

• ${ displaystyle S subset T}$, va S bo'yicha qisman tartib T dan hosil bo'ladi,
• agar ${ displaystyle s in S}$ S va $IS (lar, T) da { displaystyle t }$, keyin ${ displaystyle | Succ (t, T) cap IS (s, S) | = 1}$,
• dan qat'iyan ortib boruvchi funktsiya mavjud ${ displaystyle alpha}$ ga ${ displaystyle beta}$, shu kabi ${ displaystyle S (n) subset T (f (n))}.$

Intuitiv ravishda, S ning T ga qattiq singdirilishi uchun,

• S induksiya qilingan qisman tartib bilan T ning kichik to'plami bo'lishi kerak
• S T ning tarmoqlangan tuzilishini saqlab turishi kerak; ya'ni, agar S-dagi nomsimon tugun T-da n zudlik bilan vorislarga ega bo'lsa, u holda S-da n zudlik bilan vorislar bo'ladi
• S T ning tuzilishini saqlaydi; umumiy S darajadagi barcha tugunlar T da umumiy darajada bo'lishi kerak.

Adabiyotlar

1. Keyt R. Milliken, Daraxtlar uchun Ramsey teoremasi J. Taroq. Nazariya (A seriyasi) 26 (1979), 215-237
2. Keyt R. Milliken, Daraxtning cheksiz kichik daraxtlari uchun bo'linish teoremasi, Trans. Amer. Matematika. Soc. 263 №1 (1981), 137-148.