[math-fun] Dilworth's theorem

At 07:04 PM 8/8/2006, Dan Asimov wrote:

Dilworth?

Robert Dilworth (1914-1993) was a Caltech mathematician who was a pioneer in lattice theory. His name is attached to a fundamental result: Let P be a partially ordered set. A subset of P in which any two elements are comparable is called a _chain_. A subset of P in which no two elements are comparable is an _antichain_. Dilworth's Theorem (1950): If P is finite, the minimum number of disjoint chains needed to cover P is equal to the maximum size of an antichain in P. -- Fred W. Helenius fredh@ix.netcom.com