A splitting property of maximal antichains

Ahlswede, R. and Erdős, Péter and Graham, N. (1995) A splitting property of maximal antichains. COMBINATORICA, 15 (4). pp. 475-480. ISSN 0209-9683

Text AhlswedeErdosGraham-CCA95.pdf Restricted to Repository staff only Download (296kB) | Request a copy

Abstract

In any dense poset P (and in any Boolean lattice in particular) every maximal antichain S may be partitioned into disjoint subsets S-1 and S-2, such that the union of the downset of S-1 with the upset of S-2 yields the entire poset: D(S-1)boolean OR U(S-2)=P. To find a similar splitting of maximal antichains in posets is NP-hard in general.

Actions (login required)

Edit Item