Geodesic
Binary Trees and the n-Cutset Property
Canadian mathematical bulletin, Tome 34 (1991) no. 1, pp. 23-30

Voir la notice de l'article provenant de la source Cambridge University Press

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 ω
DOI : 10.4153/CMB-1991-004-1
Mots-clés : partially ordered set, cutset, n-cutset property, maximal element, binary tree, 06A10 
Arpin, Peter; Ginsburg, John. Binary Trees and the n-Cutset Property. Canadian mathematical bulletin, Tome 34 (1991) no. 1, pp. 23-30. doi: 10.4153/CMB-1991-004-1
@article{10_4153_CMB_1991_004_1,
     author = {Arpin, Peter and Ginsburg, John},
     title = {Binary {Trees} and the {n-Cutset} {Property}},
     journal = {Canadian mathematical bulletin},
     pages = {23--30},
     year = {1991},
     volume = {34},
     number = {1},
     doi = {10.4153/CMB-1991-004-1},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1991-004-1/}
}
TY  - JOUR
AU  - Arpin, Peter
AU  - Ginsburg, John
TI  - Binary Trees and the n-Cutset Property
JO  - Canadian mathematical bulletin
PY  - 1991
SP  - 23
EP  - 30
VL  - 34
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1991-004-1/
DO  - 10.4153/CMB-1991-004-1
ID  - 10_4153_CMB_1991_004_1
ER  - 
%0 Journal Article
%A Arpin, Peter
%A Ginsburg, John
%T Binary Trees and the n-Cutset Property
%J Canadian mathematical bulletin
%D 1991
%P 23-30
%V 34
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1991-004-1/
%R 10.4153/CMB-1991-004-1
%F 10_4153_CMB_1991_004_1

[1] 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] 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] 3. Ginsburg, J., Ladders in ordered sets, Order 3 (1986), 21–38. Google Scholar

[4] 4. Higgs, D., A companion to Grillet's Theorem on maximal chains and antichains, Order 1 (1985), 371–375. Google Scholar

[5] 5. Oxtoby, J. C., Measure and category, Springer-Verlag, New York, 1971. Google Scholar

[6] 6. I. Rival and Zaguia, N., Antichain cutsets, Order 1 (1985) 235–247. Google Scholar

[7] 7. Sauer, N. and Woodrow, R., Finite cutsets and finite antichains, Order 1 (1984), 35–46. Google Scholar

[8] 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

Cité par Sources :