𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Problems on chain partitions

✍ Scribed by Jerrold R. Griggs

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
419 KB
Volume
72
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Problems on chain partitions

Recently I have come across several fundamental problems concerning the existence of partitions of posets into chains satisfying certain conditions. Other problems of this sort have been open and frustrating researchers for years. 1 have collected these problems here, together with a few of my own, to give them wider exposure. The problems can be easily stated for a broad mathematical audience. It is likely that their solutions require techniques and insights which differ greatly from those normally employed in the contexts in which the problems were initially developed.

The presentation of the problems follows a review of the necessary notation and terminology. We first discuss problems about the poset of subsets of a finite set, and then we give problems for other families of posets.

πŸ“œ SIMILAR VOLUMES

On-line chain partitions of orders
On-line chain partitions of orders
✍ Stefan Felsner πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 698 KB

We analyze the on-line chain partitioning problem as a two-person game. One person builds an order one point at a time. The other person responds by making an irrevocable assignment of the new point to a chain of a chain partition. Kierstead gave a strategy showing that width k orders can be on-line

Chain partitions of ordered sets
Chain partitions of ordered sets
✍ Willem L. FouchΓ© πŸ“‚ Article πŸ“… 1996 πŸ› Springer Netherlands 🌐 English βš– 651 KB
Nested Chain Partitions of Hamiltonian F
Nested Chain Partitions of Hamiltonian Filters
✍ David G.C. Horrocks πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 340 KB

Let P be a poset, consisting of all sets X [n]=[1, 2, ..., n] which contain at least one of a given collection F of 2-subsets of [n], ordered by inclusion. By modifying a construction of Greene and Kleitman, we show that if F is hamiltonian, that is, contains [1, 2], [2, 3], ..., [n&1, n] and [1, n]