|
|
|
|
|
AntichainIn the mathematical area of order theory, an antichain in a partially ordered set S is a subset A of S such that every pair of members of A is incomparable, i.e., for any x, y in A, neither x ≤ y nor y ≤ x. Dilworth's theorem states that the non-existence of an antichain A of size n+1 in S is a necessary and sufficient condition for S to be the union of n total orders. This motivates questions about the size of maximal antichain. Sperner's theorem says that in the power set of a finite set X of size n, ordered by inclusion, a maximal antichain has size at most , in other words, the maximal antichain can be found at the "median" size subsets of X. For details see Sperner family.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|