CDAM: Computational, Discrete and Applicable Mathematics@LSE

CDAM Research Report, LSE-CDAM-2007-19

August 2007

Partitioning Posets

Viresh Patel

Given a poset P=(X, <), a partition X₁,..., X_k of X is called an ordered partition of P if, whenever x ∈ X_i and y ∈ X_j 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
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM@LSE Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk