Věta o Millikensově stromu - Millikens tree theorem - Wikipedia

v matematika, Millikenova věta o stromu v kombinatorika je zobecňující věta o oddílu Ramseyova věta do nekonečna stromy, objekty s větší strukturou než sady.

Nechť T je konečně rozdělení zakořeněný strom výšky ω, n kladné celé číslo a ${ displaystyle mathbb {S} _ {T} ^ {n}}$ sbírka všech silně vložených podstromů T výšky n. V jedné ze svých jednoduchých forem Millikenova stromová věta uvádí, že pokud ${ displaystyle mathbb {S} _ {T} ^ {n} = C_ {1} pohár ... pohár C_ {r}}$ pak pro nějaký silně vložený nekonečný podstrom R T, ${ displaystyle mathbb {S} _ {R} ^ {n} podmnožina C_ {i}}$ pro některé i ≤ r.

To okamžitě naznačuje Ramseyova věta; vezměte strom T jako lineární uspořádání na ω vrcholech.

Definovat ${ displaystyle mathbb {S} ^ {n} = bigcup _ {T} mathbb {S} _ {T} ^ {n}}$ kde T se pohybuje přes konečně štěpící zakořeněné stromy výšky ω. Millikenova věta o stromu říká, že to nejen je ${ displaystyle mathbb {S} ^ {n}}$ oddíl pravidelný pro každé n <ω, ale homogenní podstrom R zaručený teorémem je silně vložený v T.

Silné vkládání

Zavolejte T jako α-strom, pokud má každá větev T mohutnost α. Definujte Succ (p, P) = ${ displaystyle {q v P: q geq p }}$, a ${ displaystyle IS (p, P)}$ být množinou bezprostředních následníků p v P. Předpokládejme, že S je α-strom a T je β-strom, s 0 ≤ α ≤ β ≤ ω. S je silně vložený v T, pokud:

• ${ displaystyle S podmnožina T}$, a částečný řád na S je indukován z T,
• -li ${ displaystyle s v S}$ není v S a ${ displaystyle t v IS (s, T)}$, pak ${ displaystyle | Succ (t, T) cap IS (s, S) | = 1}$,
• existuje přísně rostoucí funkce z ${ displaystyle alpha}$ na ${ displaystyle beta}$, takový, že ${ displaystyle S (n) podmnožina T (f (n)).}$

Intuitivně, aby S bylo silně vloženo do T,

• S musí být podmnožinou T s indukovaným dílčím řádem
• S musí zachovat rozvětvenou strukturu T; tj., pokud má nemaximální uzel v S n bezprostředních následníků v T, pak má n bezprostředních následníků v S
• S zachovává strukturu úrovně T; všechny uzly na společné úrovni S musí být na společné úrovni v T.

Reference

1. Keith R. Milliken, Ramseyova věta pro stromy J. Comb. Teorie (řada A) 26 (1979), 215-237
2. Keith R. Milliken, věta o rozdělení pro nekonečné podstromy stromu, Trans. Amer. Matematika. Soc. 263 Č. 1 (1981), 137-148.