?

Log in

No account? Create an account
Dilworth's theorem - Yarrow [entries|archive|friends|userinfo]
Yarrow

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Dilworth's theorem [Nov. 25th, 2008|10:21 pm]
Yarrow
A set P is partially ordered if for every x, y, and z in P:
  • Reflexivity: x is less than or equal to x;
  • Antisymmetry: If x is less than or equal to y and y is less than or equal to x, then x equals y; and
  • Transitivity: If x is less than or equal to y and y is less than or equal to z, then x is less than or equal to z.
If x is less than or equal to y or y is less than or equal to x, then we say that x and y are comparable.  If it is neither the case that x is less than or equal to y or y is less than or equal to x, then we say x and y are incomparable.

A chain in P is a subset of P where every two members of the subset are comparable.

An antichain in P is a subset of P where no two members of the subset are comparable (unless they are equal).

The width of a finite partial order is the size of its largest antichain.

Dilworth's theorem says that the width of P is equal to the smallest n such that P can be written as the union of n chains.

I keep nibbling away at the proof of this one, but it's slippery.

Offering:
Doors are solemn things, guarding entrances,
Opening to the favored,
Closing to thieves and weather.
Doors are solemn things, but
Cat doors are for cats.
linkReply