CDAM: Computational, Discrete and Applicable
CDAM Research Report, LSE-CDAM-2007-19
Viresh PatelGiven a poset P=(X, <), a partition X1,..., Xk of X is called an ordered partition of P if, whenever x ∈ Xi and y ∈ Xj with x < y, then i ≤ j. In this paper, we show that for every poset P=(X, <) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m-1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k=2, but we give an improved bound, m/k - c(k)√m, for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P=(X, <), we can find an ordered partition of P that minimises the total number of comparable pairs within parts in polynomial time. We prove more general, weighted versions of these results.
A PDF file (193 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-19, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
|Introduction to the CDAM Research Report Series.|