Antichain

Last updated

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.

Contents

The size of the largest antichain in a partially ordered set is known as its width. By Dilworth's theorem, this also equals the minimum number of chains (totally ordered subsets) into which the set can be partitioned. Dually, the height of the partially ordered set (the length of its longest chain) equals by Mirsky's theorem the minimum number of antichains into which the set can be partitioned.

The family of all antichains in a finite partially ordered set can be given join and meet operations, making them into a distributive lattice. For the partially ordered system of all subsets of a finite set, ordered by set inclusion, the antichains are called Sperner families and their lattice is a free distributive lattice, with a Dedekind number of elements. More generally, counting the number of antichains of a finite partially ordered set is #P-complete.

Definitions

Let be a partially ordered set. Two elements and of a partially ordered set are called comparable if If two elements are not comparable, they are called incomparable; that is, and are incomparable if neither

A chain in is a subset in which each pair of elements is comparable; that is, is totally ordered. An antichain in is a subset of in which each pair of different elements is incomparable; that is, there is no order relation between any two different elements in (However, some authors use the term "antichain" to mean strong antichain, a subset such that there is no element of the poset smaller than two distinct elements of the antichain.)

Height and width

A maximal antichain is an antichain that is not a proper subset of any other antichain. A maximum antichain is an antichain that has cardinality at least as large as every other antichain. The width of a partially ordered set is the cardinality of a maximum antichain. Any antichain can intersect any chain in at most one element, so, if we can partition the elements of an order into chains then the width of the order must be at most (if the antichain has more than elements, by the pigeonhole principle, there would be 2 of its elements belonging to the same chain, contradiction). Dilworth's theorem states that this bound can always be reached: there always exists an antichain, and a partition of the elements into chains, such that the number of chains equals the number of elements in the antichain, which must therefore also equal the width. [1] Similarly, one can define the height of a partial order to be the maximum cardinality of a chain. Mirsky's theorem states that in any partial order of finite height, the height equals the smallest number of antichains into which the order may be partitioned. [2]

Sperner families

An antichain in the inclusion ordering of subsets of an -element set is known as a Sperner family. The number of different Sperner families is counted by the Dedekind numbers, [3] the first few of which numbers are

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in the OEIS ).

Even the empty set has two antichains in its power set: one containing a single set (the empty set itself) and one containing no sets.

Join and meet operations

Any antichain corresponds to a lower set

In a finite partial order (or more generally a partial order satisfying the ascending chain condition) all lower sets have this form. The union of any two lower sets is another lower set, and the union operation corresponds in this way to a join operation on antichains:

Similarly, we can define a meet operation on antichains, corresponding to the intersection of lower sets:

The join and meet operations on all finite antichains of finite subsets of a set define a distributive lattice, the free distributive lattice generated by Birkhoff's representation theorem for distributive lattices states that every finite distributive lattice can be represented via join and meet operations on antichains of a finite partial order, or equivalently as union and intersection operations on the lower sets of the partial order. [4]

Computational complexity

A maximum antichain (and its size, the width of a given partially ordered set) can be found in polynomial time. [5] Counting the number of antichains in a given partially ordered set is #P-complete. [6]

Related Research Articles

Partially ordered set Set ordered by a transitive, antisymmetric, and reflexive binary relation

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order." The word partial in the names "partial order" and "partially ordered set" is used as an indication that not every pair of elements needs to be comparable. That is, there may be pairs of elements for which neither element precedes the other in the poset. Partial orders thus generalize total orders, in which every pair is comparable.

In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :

  1. (reflexive).
  2. If and then (transitive)
  3. If and then (antisymmetric)
  4. or .
Maximal and minimal elements Element that is not ≤ (or ≥) any other element

In mathematics, especially in order theory, a maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some preordered set is defined dually as an element of S that is not greater than any other element in S.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

Order theory is a branch of mathematics which investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every two elements have a unique supremum and a unique infimum. An example is given by the natural numbers, partially ordered by divisibility, for which the unique supremum is the least common multiple and the unique infimum is the greatest common divisor.

Antimatroid

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included. Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts.

In combinatorics, a Sperner family, or clutter, is a family F of subsets of a finite set E in which none of the sets contains another. Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or irredundant set.

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

Graded poset

In mathematics, in the branch of combinatorics, a graded poset is a partially ordered set (poset) P equipped with a rank functionρ from P to the set N of all natural numbers. ρ must satisfy the following two properties:

Covering relation Mathematical relation inside orderings

In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically express the partial order by means of the Hasse diagram.

Dedekind–MacNeille completion Smallest complete lattice containing a partially ordered set

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders. It is named after Garrett Birkhoff, who published a proof of it in 1937.

Dedekind number Combinatorial sequence of numbers

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) counts the number of monotone boolean functions of n variables. Equivalently, it counts the number of antichains of subsets of an n-element set, the number of elements in a free distributive lattice with n generators, or the number of abstract simplicial complexes with n elements.

In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for Leon Mirsky (1971) and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.

In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth.

References

  1. Dilworth, Robert P. (1950), "A decomposition theorem for partially ordered sets", Annals of Mathematics , 51 (1): 161–166, doi:10.2307/1969503, JSTOR   1969503
  2. Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly , 78 (8): 876–877, doi:10.2307/2316481, JSTOR   2316481
  3. Kahn, Jeff (2002), "Entropy, independent sets and antichains: a new approach to Dedekind's problem", Proceedings of the American Mathematical Society , 130 (2): 371–378, doi: 10.1090/S0002-9939-01-06058-0 , MR   1862115
  4. Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal , 3 (3): 443–454, doi:10.1215/S0012-7094-37-00334-X
  5. Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Recognition algorithms for orders of small width and graphs of small Dilworth number", Order , 20 (4): 351–364 (2004), doi:10.1023/B:ORDE.0000034609.99940.fb, MR   2079151, S2CID   1363140
  6. Provan, J. Scott; Ball, Michael O. (1983), "The complexity of counting cuts and of computing the probability that a graph is connected", SIAM Journal on Computing , 12 (4): 777–788, doi:10.1137/0212053, MR   0721012