Millikens ағаштар туралы теорема - Millikens tree theorem - Wikipedia

Жылы математика, Милликен ағашы туралы теорема жылы комбинаторика жалпылайтын бөлім теоремасы Рэмси теоремасы шексізге дейін ағаштар, қарағанда құрылымы жоғары нысандар жиынтықтар.

T ақырлы бөліну болсын тамырланған ағаш биіктігі ω, n оң бүтін сан, және ${ displaystyle mathbb {S} _ {T} ^ {n}}$ биіктігі n биіктікте орналасқан барлық суб-ағаштардың жиынтығы. Милликен ағашының теоремасы өзінің қарапайым формаларының бірінде, егер ${ displaystyle mathbb {S} _ {T} ^ {n} = C_ {1} cup ... cup C_ {r}}$ содан кейін кейбір қатты ендірілген шексіз кіші R ағашы үшін T, ${ displaystyle mathbb {S} _ {R} ^ {n} ішкі жиын C_ {i}}$ кейбіреулері үшін

Бұл бірден көздейді Рэмси теоремасы; Т ағашын ω төбелерінде сызықтық ретке келтіру үшін қабылдаңыз.

Анықтаңыз ${ displaystyle mathbb {S} ^ {n} = bigcup _ {T} mathbb {S} _ {T} ^ {n}}$ мұндағы T биіктіктегі тамырланған ағаштарды бөлуге қатысты. Милликеннің ағаш теоремасы тек қана емес дейді ${ displaystyle mathbb {S} ^ {n}}$ бөлім тұрақты әрбір n <ω үшін, бірақ теоремамен кепілдендірілген біртекті R кіші ағашы қатты енгізілген Т.-да

Күшті ендіру

Егер T-дің әр тармағында α мәні бар болса, α ағашын шақырыңыз. Сукканы анықтаңыз (p, P) = ${ displaystyle {q in P: q geq p }}$, және ${ displaystyle IS (p, P)}$ $ P $ -дан кейінгі ізбасарлардың жиынтығы болу керек, егер S - α-ағаш, ал T - is-ағаш болса, онда 0 α ≤ β ≤ ω болады. S - қатты енгізілген егер T:

• ${ displaystyle S subset T}$, және S бойынша ішінара тәртіп T,
• егер ${ displaystyle s in S}$ S және максималды емес ${ displaystyle t IS (s, T)} ішінде$, содан кейін ${ displaystyle | Succ (t, T) cap IS (s, S) | = 1}$,
• бастап қатаң түрде өсетін функция бар ${ displaystyle alpha}$ дейін ${ displaystyle beta}$, осылай ${ displaystyle S (n) subset T (f (n)).}$

S интенсивті түрде T-ге енуі үшін,

• S индукцияланған ішінара реті бар T жиынтығы болуы керек
• S Т-ның тармақталған құрылымын сақтауы керек; яғни, егер S-дегі максималды емес түйінде T-де n бірден ізбасар болса, онда S-де n бірден ізбасар болады
• S Т деңгейінің құрылымын сақтайды; жалпы S деңгейіндегі барлық түйіндер Т деңгейінде бір деңгейде болуы керек.

Әдебиеттер тізімі

1. Кит Р.Милликен, Ағаштарға арналған Рамси теоремасы J. тарақ. Теория (А сериясы) 26 (1979), 215-237
2. Кит Р.Милликен, Ағаштың шексіз кіші ағаштары үшін бөлу теоремасы, Транс. Amer. Математика. Soc. 263 No1 (1981), 137-148.