A Ramsey theorem for trees (Q1137591)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3668650
Language Label Description Also known as
default for all languages
No label defined
    English
    A Ramsey theorem for trees
    scientific article; zbMATH DE number 3668650

      Statements

      A Ramsey theorem for trees (English)
      0 references
      0 references
      1979
      0 references
      Ramsey theorem for trees
      0 references
      finite version
      0 references
      infinite version
      0 references
      partition
      0 references
      strongly embedded subtrees
      0 references
      rooted tree
      0 references
      partially ordered set
      0 references
      finite sequence of trees
      0 references
      This paper contains infinite and finite versions for trees of Ramsey's Theorem. For example, the infinite version of the theorem states that if \(T\) is an infinite, leafless, rooted binary tree, and if the collection of all strongly embedded, height two subtrees of \(T\) is partitioned into two classes, then there must exist a strongly embedded, infinite, leafless subtree \(S\) of \(T\) such that all strongly embedded, height two subtrees of \(\mathrm{S}\) are in the same class. There have been earlier, finite versions for trees of Ramsey's Theorem, due to W. Deuber and K. Leeb. The new idea in this paper that enables generalization to an infinite version is the consideration of strongly embedded subtrees. (Consider a rooted tree to be a special kind of partially ordered set with the root being the minimum element.) For \(t\) to be a strongly embedded subtree of a tree \(T\), a node of \(t\) (that is not on the highest level of \(t\) ) must have the same branching structure as it has in \(T\), the infimum of two nodes in \(t\) must be identical to the infimum of those nodes in \(T\), and nodes on a common level of \(t\) must also reside on a common level of \(T\). The proof of the main theorem of the paper requires consideration of arbitrarily long, finite sequences of trees instead of a single tree. The paper contains a proof of a previously unpublished reformulation due to Laver and Pincus of the Halpern, Laichli theorem for sequences of trees. This reformulation is exactly the ``pigeon-hole principle'' necessary for the proof of the tree version of Ramsey's Theorem described in the first paragraph. Once this ``pigeon-hole principle'' has been established, the main theorem follows by mimicking a standard proof of Ramsey's Theorem in the context of an arbitrary finite sequence of trees. However, there are many details required in the consideration of such sequences of trees. The paper also shows how the earlier, finite versions for trees of Ramsey's Theorem (due to Deuber and Leeb) are consequences of the result for strongly embedded trees. Thus it seems that by restricting the class of subtrees that are considered to strongly embedded subtrees, there is no loss of generality.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references