A Ramsey theorem for trees
| Autor: | Keith Robert Milliken |
|---|---|
| Rok vydání: | 1979 |
| Předmět: |
Combinatorics
Discrete mathematics Class (set theory) Tree (data structure) TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Integer Computational Theory and Mathematics Ramsey theory Discrete Mathematics and Combinatorics Node (circuits) Ramsey's theorem Mathematics Theoretical Computer Science |
| Zdroj: | Journal of Combinatorial Theory, Series A. 26(3):215-237 |
| ISSN: | 0097-3165 |
| DOI: | 10.1016/0097-3165(79)90101-8 |
| Popis: | We prove a Ramsey theorem for trees. The infinite version of this theorem can be stated: if T is a rooted tree of infinite height with each node of T having at least one but finitely many immediate successors, if n is a positive integer, and if the collection of all strongly embedded, height- n subtrees of T is partitioned into finitely many classes, then there must exist a strongly embedded subtree S of T with S having infinite height and with all the strongly embedded, height- n subtrees of S in the same class. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|