Теорема Милликенса о дереве - Millikens tree theorem

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

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

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

Определять ${\displaystyle \mathbb {S} ^{n}=\bigcup _{T}\mathbb {S} _{T}^{n}}$ где T пробегает конечно-расщепляющиеся корневые деревья высоты ω. Теорема Милликена о дереве утверждает, что не только ${\displaystyle \mathbb {S} ^{n}}$ перегородка регулярная для каждого 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)\subset 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.