info prev up next book cdrom email home

Antichain

Let $P$ be a finite Partially Ordered Set. An antichain in $P$ is a set of pairwise incomparable elements (e.g., a family of Subsets such that, for any two of them, neither is a Subset of the other). The Width of $P$ is the maximum Cardinality of an Antichain in $P$. For a Partial Order, the size of the longest Antichain is called the Width.

See also Chain, Dilworth's Lemma, Partially Ordered Set, Width (Partial Order)


References

Sloane, N. J. A. Sequence A006826/M2469 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.




© 1996-9 Eric W. Weisstein
1999-05-25