WikiDer > Теорема Милликенса о дереве - Википедия

В математика, Теорема Милликена о дереве в комбинаторика является теоремой о разбиении, обобщающей Теорема Рамсея до бесконечности деревья, объекты с большей структурой, чем наборы.

Пусть T - конечно-расщепляющее укоренившееся дерево высоты ω, n - натуральное число, и ${ Displaystyle mathbb {S} _ {T} ^ {n}}$ совокупность всех сильно вложенных поддеревьев T высоты n. В одной из своих простых форм теорема Милликена о дереве утверждает, что если ${ Displaystyle mathbb {S} _ {T} ^ {n} = C_ {1} чашка ... чашка C_ {r}}$ то для некоторого сильно вложенного бесконечного поддерева R дерева T ${ displaystyle mathbb {S} _ {R} ^ {n} подмножество C_ {i}}$ для некоторого i ≤ r.

Отсюда сразу следует Теорема Рамсея; в качестве дерева T возьмем линейный порядок на ω вершинах.

Определять ${ Displaystyle mathbb {S} ^ {n} = bigcup _ {T} mathbb {S} _ {T} ^ {n}}$ где T пробегает конечно-расщепляющиеся корневые деревья высоты ω. Теорема Милликена о дереве утверждает, что не только ${ Displaystyle mathbb {S} ^ {п}}$ перегородка регулярная для каждого n <ω, но однородное поддерево R, гарантированное теоремой, является сильно внедренный в Т.

Сильное вложение

Назовем T α-деревом, если каждая ветвь T имеет мощность α. Определите Succ (p, P) = ${ displaystyle {q in P: q geq p }}$, и ${ Displaystyle IS (p, P)}$ быть множеством непосредственных последователей p в P. Предположим, что S является α-деревом, а T - β-деревом, причем 0 ≤ α ≤ β ≤ ω. S есть сильно внедренный в T, если:

• ${ displaystyle S subset T}$, а частичный порядок на S индуцируется из T,
• если ${ displaystyle s in S}$ немаксимальна в S и ${ displaystyle t in IS (s, T)}$, тогда ${ displaystyle | Succ (t, T) cap IS (s, S) | = 1}$,
• существует строго возрастающая функция из ${ displaystyle alpha}$ к ${ displaystyle beta}$, так что ${ Displaystyle S (n) подмножество T (f (n)).}$

Интуитивно для того, чтобы S было сильно вложено в T,

• S должно быть подмножеством T с индуцированным частичным порядком
• S должен сохранять ветвящуюся структуру T; т.е., если у немаксимального узла в S есть n непосредственных последователей в T, то у него есть n непосредственных последователей в S
• S сохраняет структуру уровней T; все узлы на общем уровне S должны быть на общем уровне в T.

Рекомендации

1. Кейт Р. Милликен, Теорема Рамсея для деревьев J. Comb. Теория (серия А) 26 (1979), 215-237
2. Кейт Р. Милликен, Теорема о разбиении для бесконечных поддеревьев дерева, Пер. Амер. Математика. Soc. 263 № 1 (1981), 137-148.