Teorema del árbol de Milliken

En matemáticas , el teorema del árbol de Milliken en combinatoria es un teorema de partición que generaliza el teorema de Ramsey a árboles infinitos , objetos con más estructura que los conjuntos .

Sea T un árbol enraizado de división finita de altura ω, un entero positivo, y${\displaystyle \mathbb {S} _{T}^{n}}$la colección de todos los subárboles fuertemente incrustados de T de altura n. En una de sus formas simples, el teorema del árbol de Milliken establece que si${\displaystyle \mathbb {S} _{T}^{n}=C_{1}\cup ...\cup C_{r}}$entonces para algún subárbol infinito fuertemente incrustado R de T,${\displaystyle \mathbb {S} _{R}^{n}\subset C_{i}}$para algún i ≤ r.

Esto implica inmediatamente el teorema de Ramsey ; tomemos el árbol T como un ordenamiento lineal en ω vértices.

Definir${\displaystyle \mathbb {S} ^{n}=\bigcup _{T}\mathbb {S} _{T}^{n}}$donde T varía sobre árboles enraizados de división finita de altura ω. El teorema del árbol de Milliken dice que no solo es${\displaystyle \mathbb {S} ^{n}}$Partición regular para cada n < ω, pero que el subárbol homogéneo R garantizado por el teorema está fuertemente incrustado en T.

Llamamos a T un α-árbol si cada rama de T tiene cardinalidad α. Definimos Succ(p, P)=${\displaystyle \{q\in P:q\geq p\}}$, y${\displaystyle IS(p,P)}$Sea P el conjunto de sucesores inmediatos de p en P. Supongamos que S es un árbol α y T es un árbol β, con 0 ≤ α ≤ β ≤ ω. S está fuertemente incrustado en T si:

• ${\displaystyle S\subset T}$y el orden parcial en S es inducido por T,
• si${\displaystyle s\in S}$no es máximo en S y${\displaystyle t\in IS(s,T)}$, entonces${\displaystyle |Succ(t,T)\cap IS(s,S)|=1}$,
• existe una función estrictamente creciente de${\displaystyle \alpha }$a${\displaystyle \beta }$, de tal manera que${\displaystyle S(n)\subset T(f(n)).}$

Intuitivamente, para que S esté fuertemente incrustado en T,

• S debe ser un subconjunto de T con el orden parcial inducido.
• S debe preservar la estructura de ramificación de T; es decir , si un nodo no máximo en S tiene n sucesores inmediatos en T, entonces tiene n sucesores inmediatos en S.
• S conserva la estructura de niveles de T; todos los nodos que se encuentran en un nivel común de S deben estar en un nivel común en T.

• Keith R. Milliken, Un teorema de Ramsey para árboles J. Comb. Theory (Serie A) 26 (1979), 215-237
• Keith R. Milliken, Un teorema de partición para los subárboles infinitos de un árbol, Trans. Amer. Math. Soc. 263 No.1 (1981), 137-148.