Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-20T11:32:54.648Z Has data issue: false hasContentIssue false
  • English
  • Français

Binary Trees and the n-Cutset Property

Published online by Cambridge University Press:  20 November 2018

Peter Arpin  and
John Ginsburg
Peter Arpin
Affiliation:
University of Winnipeg Winnipeg, Manitoba R3B 2E9
John Ginsburg
Affiliation:
University of Winnipeg Winnipeg, Manitoba R3B 2E9
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 ω

Keywords

partially ordered setcutsetn-cutset propertymaximal elementbinary tree06A10
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 34 , Issue 1 , 01 March 1991 , pp. 23 - 30
Copyright
Copyright © Canadian Mathematical Society 1991

References

1. Ginsburg, J., On the number of maximal elements in a partially ordered set, Can. Math. Bull. 30(3)(1987), 351–357.Google Scholar
2. Ginsburg, J., Rival, I. and Sands, B., Antichains and finite sets that meet all maximal chains, Can. Jour. Math. 28(3)( 1986), 619–632.Google Scholar
3. Ginsburg, J., Ladders in ordered sets, Order 3 (1986), 21–38.Google Scholar
4. Higgs, D., A companion to Grillet's Theorem on maximal chains and antichains, Order 1 (1985), 371–375.Google Scholar
5. Oxtoby, J. C., Measure and category, Springer-Verlag, New York, 1971.Google Scholar
6. I. Rival and Zaguia, N., Antichain cutsets, Order 1 (1985) 235–247.Google Scholar
7. Sauer, N. and Woodrow, R., Finite cutsets and finite antichains, Order 1 (1984), 35–46.Google Scholar
8. Sauer, N. and El Zahar, M., The length, the width and the cuset number of finite ordered sets, Order 2( 1985), 243–248.Google Scholar