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.

Item Type: | Article |
---|---|

Subjects: | Q Science / természettudomány > QA Mathematics / matematika |

SWORD Depositor: | MTMT SWORD |

Depositing User: | MTMT SWORD |

Date Deposited: | 06 Feb 2014 03:50 |

Last Modified: | 06 Feb 2014 03:50 |

URI: | http://real.mtak.hu/id/eprint/9925 |

### Actions (login required)

Edit Item |