Yarrow (angelweed) wrote,
Yarrow
angelweed

Dilworth's theorem

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.
Subscribe

  • Julie

    Julie had surgery today to remove her left lung, a treatment for asbestos-caused lung cancer. But tonight her daughter posted: Mom is doing really…

  • Radical Muzak

    Not what I expected to hear when I stopped at Sheetz coming home from the SpiralHeart meeting: Some folks are born made to wave the flag, Ooh,…

  • Handpan Dissonance

    Here is a (very naive) attempt to estimate the potential dissonance for Pantheon Steel's Sound Models. The idea is to calculate the dissonance you…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments