@MISC{DILWORTH.MIZ,
  AUTHOR = {Rudnicki, Piotr},
  TITLE = {Dilworth's Decomposition Theorem for Posets},
  NOTE = {This work has been partially supported by the NSERC grant
      OGP 9207.},
  SECTION1 = {Preliminaries},
  SECTION2 = {Cliques and stable sets},
  SECTION3 = {Clique number and stability number},
  SECTION4 = {Lower and upper sets, minimal and maximal elements},
  SECTION5 = {Substructures},
  SECTION6 = {Partitions into cliques and stable sets},
  SECTION7 = {Dilworth's theorem and a dual},
  SECTION8 = {Erdos-Szekeres theorem},
  DAY = {17},
  MONTH = {September},
  YEAR = {2009},
  ADDRESS1 = {Department of Computing Science\\University of Alberta\\Edmonton, AB, Canada},
  SUMMARY = {The following theorem is due to Dilworth~\cite{Dilworth50}:
  Let $P$ be a partially ordered set. If the maximal number
  of elements in an independent subset (anti-chain) of $P$ is $k$, then $P$
  is the union of $k$ chains (cliques).\par
  In this article we formalize an elegant proof of the above theorem for
  finite posets by Perles~\cite{Perles63}.  The result is then used in
  proving the case of infinite posets following the original proof of
  Dilworth~\cite{Dilworth50}.\par
  A dual of Dilworth's theorem also holds: a poset with maximum clique $m$
  is a union of $m$ independent sets.  The proof of this dual fact
  is considerably easier; we follow the proof by Mirsky~\cite{Mirsky71}.
  Mirsky states also a corollary that a poset of $r \times s + 1$
  elements possesses a clique of size $r+1$ or an independent set of
  size $s+1$, or both.  This corollary is then used to prove the
  result of Erd\H{o}s and Szekeres~\cite{ES35}.\par
  Instead of using posets, we drop reflexivity and state the facts
  about antisymmetric and transitive relations.}}

@article{Dilworth50,
 author     = {R. P. Dilworth},
 title      = {A {D}ecomposition {T}heorem for {P}artially {O}rdered {S}ets},
 journal    = {Annals of Mathematics},
 volume     = {51},
 number     = {1},
 year      = {1950},
 pages     = {161-166}}

@article{Perles63,
  author    = {M. A. Perles},
  title     = {A {P}roof of {D}ilworth's {D}ecomposition {T}heorem for
               {P}artially {O}rdered {S}ets},
  journal   = {Israel Journal of Mathematics},
  volume    = {1},
  year      = {1963},
  pages     = {105-107}}

@article{Mirsky71,
  author    = {L. Mirsky},
  title     = {A {D}ual of {D}ilworth's {D}ecomposition {T}heorem},
  journal   = {The American Mathematical Monthly},
  volume    = {78},
  number    = {8}
  year      = {1971},
  pages     = {876-877}}

@article{ErdosSzekeres35,
  author    = {P. Erd\H{o}s and G. Szekeres},
  title     = {A combinatorial problem in geometry},
  journal   = {Compositio Mathematica},
  volume    = {2},
  year      = {1935},
  pages     = {463-470}}

