Binary Trees and the n-Cutset Property

Arpin, Peter ; Ginsburg, John

Canadian mathematical bulletin, Tome 34 (1991) no. 1, pp. 23-30

Résumé

A partially ordered set P is said to have the n-cutset property if for every element x of P, there is a subset S of P all of whose elements are noncomparable to x, with |S| ≤ n, and such that every maximal chain in P meets {x} ∪ S. It is known that if P has the n-cutset property then P has at most 2n maximal elements. Here we are concerned with the extremal case. We let Max P denote the set of maximal elements of P. We establish the following result. THEOREM: Let n be a positive integer. Suppose P has the n-cutset property and that |Max P| = 2n . Then P contains a complete binary tree T of height n with Max T = Max P and such that C ∩ T is a maximal chain in T for every maximal chain C of P. Two examples are given to show that this result does not extend to the case when n is infinite. However the following is shown. THEOREM: Suppose that P has the ω-cutset property and that |Max P| = 2ω . If P — Max P is countable then P contains a complete binary tree of height ω

Détail

DOI : 10.4153/CMB-1991-004-1

Mots-clés : partially ordered set, cutset, n-cutset property, maximal element, binary tree, 06A10