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

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

Пусть T - конечно-расщепляющее укоренившееся дерево высоты ω, n - натуральное число, и совокупность всех сильно вложенных поддеревьев T высоты n. В одной из своих простых форм теорема Милликена о дереве утверждает, что если то для некоторого сильно вложенного бесконечного поддерева R дерева T для некоторого i ≤ r.

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

Определять где T пробегает конечно-расщепляющиеся корневые деревья высоты ω. Теорема Милликена о дереве утверждает, что не только перегородка регулярная для каждого n <ω, но однородное поддерево R, гарантированное теоремой, является сильно внедренный в Т.

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

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

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

Интуитивно для того, чтобы 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.