Loading...
Please wait, while we are loading the content...
Similar Documents
Dilworth's Decomposition Theorem for Posets
| Content Provider | Scilit |
|---|---|
| Author | Rudnicki, Piotr |
| Copyright Year | 2009 |
| Abstract | Dilworth's Decomposition Theorem for PosetsThe following theorem is due to Dilworth [8]: 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).In this article we formalize an elegant proof of the above theorem for finite posets by Perles [13]. The result is then used in proving the case of infinite posets following the original proof of Dilworth [8].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 [11]. Mirsky states also a corollary that a poset of r x 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ős and Szekeres [9].Instead of using posets, we drop reflexivity and state the facts about anti-symmetric and transitive relations. |
| Related Links | http://www.degruyter.com/dg/viewarticle.fullcontentlink:pdfeventlink/$002fj$002fforma.2009.17.issue-4$002fv10037-009-0028-4$002fv10037-009-0028-4.pdf?t:ac=j$002fforma.2009.17.issue-4$002fv10037-009-0028-4$002fv10037-009-0028-4.xml |
| ISSN | 14262630 |
| e-ISSN | 18989934 |
| DOI | 10.2478/v10037-009-0028-4 |
| Journal | Formalized Mathematics |
| Issue Number | 4 |
| Volume Number | 17 |
| Language | English |
| Publisher | Walter de Gruyter GmbH |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Formalized Mathematics Logic Posets Clique Reflexivity Partially Ordered Independent Sets Corollary Dilworth's Decomposition Theorem Journal: Formalized Mathematics, Vol- 17, Issue- 1 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Computational Mathematics |
