Antichain

From Free net encyclopedia

In mathematics, in the area of order theory, an antichain is a relation defined on partially ordered sets.

Let S be a partially ordered set. We say two elements a and b of a partially ordered set are comparable if a ≤ b or b ≤ a. If two elements are not comparable, we say they are incomparable. A chain C in S is a pairwise comparable subset of S (i.e., for any x, y in C, x and y are comparable). Conversely, an antichain in S is a pairwise incomparable subset of S (i.e., for any x, y in C, x and y are incomparable). In other words, 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 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 <math>{n \choose \lfloor{n/2}\rfloor}</math>, in other words, the maximal antichain can be found at the "median" size subsets of X. For details see Sperner family.

Template:Combin-stubde:Antikette es:Anticadena gl:Anticadea pl:Antyłańcuch