KnowraAntichainAntichainAn antichain is a subset of a partially ordered set in which no two distinct elements are comparable under the order.BriefConnectPartially ordered set: A set equipped with a reflexive, antisymmetric, transitive relation. Antichains are defined as subsets of a partially ordered set.Sperner's theorem: A theorem stating that the largest antichain of subsets of an n-element set has size the middle binomial coefficient. It gives the exact maximum antichain size in the subset-inclusion order.Topological sorting: A linear ordering of a directed acyclic graph's vertices that places each vertex before its successors. The currently available vertices form an antichain in the induced precedence order.Boolean lattice: The partially ordered set of all subsets of a finite set, ordered by inclusion. Its largest antichains are exactly the middle-sized subset layers.Comparable elements: Two elements are comparable when one is less than or equal to the other in a given partial order. An antichain excludes every comparable pair of distinct elements.Dilworth's theorem: A theorem equating the minimum number of chains covering a finite partially ordered set with its width. It turns the largest antichain size into a chain-covering number.Concurrency (computer science): The execution of multiple computations whose steps may overlap or proceed independently. Concurrent events can be represented as incomparable elements of a causal partial order.Permutation poset: A partially ordered set built from permutations under a specified order relation, commonly pattern containment. Antichains here are permutation families with no member contained in another under the chosen order.Chain (order theory): A subset of a partially ordered set in which every pair of elements is comparable. Chains require pairwise comparability, the opposite condition to antichains.Mirsky's theorem: A theorem equating the minimum number of antichains partitioning a finite partially ordered set with its height. It relates antichain partitions to the longest chain.Show all 20Linked from 8 pagesPartial orderBroader topic: Antichains capture the extent of incomparability allowed by partial order.Maximal elementRelated: Every element of a nonempty antichain is maximal within that antichain.Order theoryBroader topic: Antichains isolate the incomparability that distinguishes partial orders from total orders.Minimal elementRelated: Every element of a nonempty antichain is minimal within that antichain.Show all 8