Antichain - Your Art History Reference Guide!

ArtHistoryClub Information Site on Antichain Art History Art History Search        Art History Browse             News        Gallery        Forums        Articles        Weblinks        welcome to our free resource site for all art history lovers!

Antichain

In 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 xy nor yx.

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 {n \choose \lfloor{n/2}\rfloor}, in other words, the maximal antichain can be found at the "median" size subsets of X. For details see Sperner family.

Last updated: 10-14-2005 06:40:38
Last updated: 01-04-2007 01:18:57
The contents of this article are licensed from Wikipedia.org under the
GNU Free Documentation License. See original document.
Art History Search | Art History Browse | Contact | Legal info