Anti chain

Antikchain is a mathematical term from the sub-area of set theory and belongs to the conceptual field of the order relation . In the English-language literature it corresponds to the term antichain , sometimes also referred to as the Sperner family or Sperner system .

The term antichain, like the term chain, belongs to the core of that part of mathematics that deals with questions about order relations. Here is next to the set theory in particular, the combinatorics of finite partially ordered sets ( English combinatorial order theory ) to mention. Of the key findings include phrases like the set of Sperner , the set of Dilworth , the marriage rate , and many more.

Clarification of the term

definition

A subset of a partial order is called an anti-chain if neither nor holds for two different elements . ${\displaystyle A\subseteq P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle a,b\in A}$ ${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$

illustration

Looking at the order relation only within the subset , then one finds no two in each other relative standing elements. So within the anti- chain the situation is opposite to that which is given in a chain of partial order . ${\displaystyle \leq }$ ${\displaystyle A}$ ${\displaystyle A}$

A good idea of ​​the concept of the anti-chain can be obtained by looking at the Hasse diagram of the semi-ordered set . In the Hasse diagram, anti-chains can be recognized as subsets for which no two elements are connected by an edge . ${\displaystyle (P,\leq )}$

The intersection of an anti- chain and a chain always has the thickness , i.e. it always consists of at most one element. This is how the term can also be understood: A subset of a semi-ordered set is an anti-chain if and only if it does not intersect a chain of two or more elements. ${\displaystyle \leq 1}$ ${\displaystyle A\subseteq P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq )}$

Examples

The real numbers

The real numbers form a chain with the usual strict order . The only anti-chains are the trivial ones: the empty set and the one-element subsets. ${\displaystyle \mathbb {R} }$ ${\displaystyle \leq }$ ${\displaystyle \varnothing }$

The prime numbers

Consider the natural numbers as a set of carriers and the known divisor relation as the order relation . For two natural numbers and is synonymous with the fact that is a divisor of , that is, that there is a natural number such that applies. ${\displaystyle \mathbb {N} =\{1,2,3,\ldots \}}$ ${\displaystyle \leq }$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle k\leq l}$ ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle n}$ ${\displaystyle k\cdot n=l}$

According to this stipulation, in this semi-ordered set, for example, the set of all prime numbers is an anti-chain. ${\displaystyle (\mathbb {N} ,\leq )}$

The divisors of 60

Choose the set of divisors of 60 as the carrier set and the divisor ratio again as the order relation. Then there is an anti chain of . ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle \{4,6,10,15\}}$ ${\displaystyle (P,\leq )}$

Sets of finite sets of the same size

Consider an arbitrary system of sets over the basic set . Choose the inclusion relation as the order relation . ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle \subseteq }$

For set , the system of -element subsets of . Then every anti chain is from . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle {\mathcal {X}}_{n}=\{\,A\in {\mathcal {X}}\;:\;\left|A\right|=n\,\}}$ ${\displaystyle {\mathcal {X}}_{n}}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {X}}_{n}}$ ${\displaystyle ({\mathcal {X}},\subseteq )}$

Orbits

The automorphism group of the partially ordered set operates as a subgroup of the symmetric group on naturally by a link for and is taken. ${\displaystyle \operatorname {Aut} (P,\leq )}$ ${\displaystyle (P,\leq )}$ ${\displaystyle S_{P}}$ ${\displaystyle P}$ ${\displaystyle \phi \cdot x=\phi (x)}$ ${\displaystyle x\in P}$ ${\displaystyle \phi \in \operatorname {Aut} (P,\leq )}$

The given orbits with are, in the case that is finite , always anti-chains of . ${\displaystyle \operatorname {Aut} (P,\leq )\cdot x=\{\,\phi (x)\;:\;\phi \in \operatorname {Aut} (P,\leq )\,\}}$ ${\displaystyle x\in P}$ ${\displaystyle P}$ ${\displaystyle (P,\leq )}$

The Sperner number

definition

The Spernerzahl ( English Sperner number ) of the ordered set is defined as the supremum of the widths of all in occurring anti chains. Today, the Sperner number is usually designated with the letter , according to the custom in English-language literature. ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq )}$ ${\displaystyle w}$

In the German-language literature, the Sperner number of (corresponding to the term width, which is also used in English-language literature ) is sometimes also called the width of . ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq )}$

Formal representation

${\displaystyle w(P,\leq )=\sup\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}}$

If it is clear from the context what the ordered set is, write briefly and simply . ${\displaystyle (P,\leq )}$ ${\displaystyle w}$

Explanation

The number of Sperner is always at most as large as the thickness of the carrier quantity of . In the case that there is a finite set , the Sperner number is also finite and therefore a natural number . Then the supremum is accepted and the following applies: ${\displaystyle w}$ ${\displaystyle |P|}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P}$

${\displaystyle w(P,\leq )\ =\max\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}.}$

Examples

The real numbers

${\displaystyle \mathbb {R} }$like any non-empty chain . ${\displaystyle w=1}$

The divisors of 60

The anti-chain given above (see Hasse diagram) is the largest possible. So here applies . ${\displaystyle \{\,4,6,10,15\,\}}$ ${\displaystyle w=4}$

The power sets

For the power set of a finite set with elements it always holds . Because this is exactly what Sperner's theorem says . ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle |X|=n}$ ${\displaystyle w({\mathcal {P}}(X))={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

For infinite the mightiness holds . ${\displaystyle X}$ ${\displaystyle |X|=\aleph _{\alpha }}$ ${\displaystyle w({{\mathcal {P}}(X)})=2^{\aleph _{\alpha }}}$

Bandage properties

Explanation

The system of the anti-chains of is always non-empty and carries the following order relation, which naturally continues the order relation from : ${\displaystyle {\mathcal {D}}={\mathcal {D}}(P,\leq )}$ ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq )}$ ${\displaystyle {\mathcal {D}}}$

For two anti-chains there is then and only if to each one exists with . ${\displaystyle A,B\in {\mathcal {D}}}$ ${\displaystyle A\leq B}$ ${\displaystyle b\in B}$ ${\displaystyle a\in A}$ ${\displaystyle a\leq b}$

The order relation defined in this way , which is also referred to as, gives the anti-chain system the structure of a distributive association . ${\displaystyle \leq }$ ${\displaystyle {\mathcal {D}}}$

The result of Dilworth

In the case of finite , special attention is now paid to the subsystem of the anti-chains of maximum size: ${\displaystyle (P,\leq )}$ ${\displaystyle {\mathcal {S}}={\mathcal {S}}(P,\leq )}$

${\displaystyle {\mathcal {S}}=\{\,A\in {\mathcal {D}}\;:\;|A|=w(P,\leq )\,\}}$

The following fundamental result from Robert Dilworth applies here :

For finite is a sub-lattice of , where the associated lattice operations and have the following representation: ${\displaystyle (P,\leq )}$ ${\displaystyle ({\mathcal {S}},\leq )}$ ${\displaystyle ({\mathcal {D}},\leq )}$ ${\displaystyle \land }$ ${\displaystyle \lor }$

(1) ${\displaystyle A\land B=\operatorname {Min} ({A}\cup {B})}$

(2) ${\displaystyle A\lor B=\operatorname {Max} ({A}\cup {B})}$

( ) ${\displaystyle A,B\in {\mathcal {S}}}$

Here, with or with for the subset of those elements of which are minimal or maximal with respect to the induced order relation within . ${\displaystyle \operatorname {Min} (X)}$ ${\displaystyle \operatorname {Max} (X)}$ ${\displaystyle X\subseteq P}$ ${\displaystyle X}$ ${\displaystyle X}$

The result of Kleitman, Edelberg, Lubell and Freese and Sperner's theorem

The conclusion is:

A finite ordered set always contains an anticchain of maximum size, which is mapped onto itself by all automorphisms . ${\displaystyle (P,\leq )}$ ${\displaystyle \phi \in \operatorname {Aut} (P,\leq )}$

Or in other words:

A finite ordered set always contains a antichain maximum size which the association of certain orbits with can be displayed. ${\displaystyle (P,\leq )}$ ${\displaystyle \operatorname {Aut} (P,\leq )\cdot x}$ ${\displaystyle x\in P}$

This leads directly to Sperner's theorem . Because in the case that is with a finite basic set , the orbits are identical to the cardinality classes . ${\displaystyle (P,\leq )=(2^{M},\subseteq )}$ ${\displaystyle M}$ ${\displaystyle {M \choose k}}$ ${\displaystyle (k=0,\dots ,\left|{M}\right|)}$

Number of anti-chains of finite power sets

The problem of determining the number of all anti-chains in the power set for and goes back to Richard Dedekind . This problem is therefore referred to as the Dedekind problem ( English Dedekind’s problem ) and the numbers as Dedekind numbers ( English Dedekind numbers ). ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle X=\{1,2,\ldots ,n\}}$ ${\displaystyle M(n)}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle M(n)}$

The number is (essentially) identical to the number of monotonically growing surjective functions from to and just as identical to the number of free distributive lattices with generating elements . ${\displaystyle M(n)}$ ${\displaystyle {\mathcal {P}}(\{1,2,\ldots ,n\})}$ ${\displaystyle 2=\{0,1\}}$ ${\displaystyle n}$

Since these numbers show significant growth , the exact determination of so far has only been successful for: ${\displaystyle M(n)}$ ${\displaystyle n=0,1,\ldots ,8}$

${\displaystyle {\begin{aligned}M(0)&=2\\M(1)&=3\\M(2)&=6\\M(3)&=20\\M(4)&=168\\M(5)&=7.581\\M(6)&=7.828.354\\M(7)&=2.414.682.040.998\\M(8)&=56.130.437.228.687.557.907.788\\\end{aligned}}}$

For an assessment of the magnitude of the growth , however, lower and upper bounds are known , for example the following, which goes back to the work of the mathematician Georges Hansel from 1966: ${\displaystyle M(n)}$

${\displaystyle 2^{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}\leq M(n)\leq 3^{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

As Daniel J. Kleitman and George Markowsky showed in 1975, the above-mentioned upper bound can be tightened further:

${\displaystyle M(n)\leq 2^{{\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}\cdot {\bigl (}1+{\mathcal {O}}{({\frac {\ln(n)}{n}})}{\bigr )}}}$

and there are even better barriers.

The Dedekind problem is still unsolved. The noted Hungarian mathematician Paul Erdős (1913–1996) is credited with remarking that the problem is too difficult for this century . It is true that the Polish mathematician Andrzej P. Kisielewicz presented a correct formula in 1988. However, this is considered useless , as it is not even possible to verify the already known Dedekind numbers for reasons of computing effort.

Delimitation of the term

In set theory , the term anti-chain is sometimes used differently. The anti chain property is in certain contexts to the incompatibility knotted or two different elements in Boolean algebra to Disjunktheitsbedingungen . Thomas Jech's monograph provides details.

literature

Original work

• Hans-Joachim Burscheid: About the breadth of the finite cardinal product of finite chains. In: Mathematical News. Volume 52, 1971, ISSN  0025-584X , pp. 283-295, doi: 10.1002 / mana.19720520121 .
• RP Dilworth : Some combinatorial problems on partially ordered sets . In: Richard Bellman , Marshall Hall, Jr. (Eds.): Combinatorial Analysis. Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society, held at Columbia University, April 24-26, 1958 (=  Proceedings of Symposia in Applied Mathematics . Volume 10 ). American Mathematical Society, 1960, ISSN  0160-7634 , pp. 85-90 .
• Ralph Freese: An application of Dilworth's lattice of maximal antichains. In: Discrete Mathematics. Volume 7, No. 1/2, 1974, ISSN  0012-365X , pp. 107-109, doi: 10.1016 / S0012-365X (74) 80022-1 .
• Curtis Greene , Daniel J. Kleitman: The structure of Sperner k-Families. In: Journal of Combinatorial Theory. Series A, Vol. 20, No. 1, 1976, ISSN  0097-3165 , pp. 41-68, doi: 10.1016 / 0097-3165 (76) 90077-7 .
• Curtis Greene, Daniel J. Kleitman: Proof Techniques on the Theory of Finite Sets . In: Gian-Carlo Rota (Ed.): Studies in Combinatorics (=  Studies in Mathematics . Volume 17 ). Math. Assoc. America, Washington, DC 1978, ISBN 0-88385-117-2 , pp. 23-79 ( MR0513002 ).
• D. Kleitman, M. Edelberg, D. Lubell: Maximal sized antichains in partial orders. In: Discrete Mathematics. Volume 1, No. 1, 1971, pp. 47-53, doi: 10.1016 / 0012-365X (71) 90006-9 .
• Hans-Josef Scholz: About the combinatorics of finite power sets in connection with Sperner's theorem. Dissertation, University of Düsseldorf 1987.
• Emanuel Sperner : A theorem about subsets of a finite set. In: Mathematical Journal. Volume 27, No. 1, 1928, ISSN  0025-5874 , pp. 544-548, doi: 10.1007 / BF01171114 .
• Georges Hansel: Sur le nombre des fonctions booléennes monotones de n variables . In: CR Acad. Sci. Paris Sér. A . tape 262 , 1966, pp. 1088-1090 ( MR0224395 ).
• Andrzej Kisielewicz: A solution of Dedekind's problem on the number of isotone Boolean functions . In: J. Reine Angew. Math. Band 386 . Washington, DC 1988, p. 139-144 , doi : 10.1515 / crll.1988.386.139 ( MR0936995 ).
• D. Kleitman , G. Markowsky : On Dedekind's problem: The number of Isotone Boolean functions. II . In: Trans. Amer. Math. Soc . tape 213 , November 1975, p. 373-390 , JSTOR : 1998052 ( MR0382107 ).

Monographs

• Martin Aigner : Combinatorics II: Matroids and transversal theory (=  university text ). Springer Verlag, Berlin (among others) 1976, ISBN 3-540-07949-1 , doi : 10.1007 / 978-3-642-66235-5 ( MR0460127 ).
• Martin Aigner: Combinatorial Theory (=  Basic Teachings of Mathematical Sciences . Volume 234 ). Springer Verlag, Berlin (among others) 1979, ISBN 3-540-90376-3 ( MR0542445 ).
• Martin Aigner: Discrete Mathematics (=  documents on the history of mathematics . Volume 6 ). 6th edition. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8 ( MR1085963 ).
• Ian Anderson: Combinatorics of Finite Sets . Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 ( MR0892525 ).
• Oliver Deiser : Basic Concepts in Scientific Mathematics. Language, numbers and initial explorations . Springer Verlag, Heidelberg et al. 2010, ISBN 978-3-642-11488-5 ( excerpt in the Google book search).
• Konrad Engel : Sperner Theory (=  Encyclopedia of Mathematics and its Applications . Volume 65 ). Cambridge University Press, Cambridge et al. 1997, ISBN 0-521-45206-6 ( MR1429390 ).
• Bernhard Ganter : Discrete Mathematics: Ordered Sets (=  Springer textbook ). Springer Spectrum, Berlin / Heidelberg 2013, ISBN 978-3-642-37499-9 .
• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag, New York 2005, ISBN 0-387-24219-8 , pp. 206 ff . ( MR2127991 ).
• Thomas Jech : Set Theory . The Third Millennium edition, revised and expanded (=  Springer Monographs in Mathematics ). Springer Verlag, Berlin et al. 2003, ISBN 3-540-44085-2 ( MR1940513 ).
• Stasys Jukna : Extremal Combinatorics (=  Texts in Theoretical Computer Science ). Springer Verlag, Heidelberg (ua) 2011, ISBN 978-3-642-17363-9 ( MR2865719 ).
• Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way (=  Cambridge Mathematical Library ). Cambridge University Press, Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 ( MR2483561 ).

Web links

• Gy. Károlyi: Lectures on extremal set systems and two-colorings of hypergraphs. (PDF; 237 kB)
• Combinatorial Methods in Computer Science. (PDF; 1.36 MB; script of a lecture by Peter Hauck, Uni Tübingen, SS 2008)

Individual evidence

1. ↑ Scholz: p. 3.
2. ^ Sperner: Math. Z. Band 27 , 1928, pp. 544 ff .
3. ↑ See Harzheim: Ordered Sets. Theorem 9.1.25, p. 296; however, the latter result presupposes the axiom of choice.
4. ↑ Kung-Rota-Yan: p. 130.
5. ^ Dilworth: Proceedings of Symposia in Applied Mathematics . 1958, p. 88 ff .
6. ^ Greene-Kleitman: J. Comb. Theory (A) . tape 20 , 1993, p. 45 .
7. ↑ Kung-Rota-Yan: p. 131.
8. ^ Kleitman-Edelberg-Lubell: Discrete Math . tape 1 , 1971, p. 47 ff .
9. ↑ Freese: Discrete Math . tape 7 , 1974, p. 107 ff .
10. ^ Greene / Kleitman: Studies in Combinatorics . 1978, p. 27 ff .
11. ↑ Scholz: p. 6 ff.
12. ^ ^{A b c} Greene-Kleitman: Studies in Combinatorics . 1978, p. 33 .
13. ↑ Ganter: pp. 42–46.
14. ↑ Kung-Rota-Yan: p. 147.
15. ↑ If one does not consider the two single-element anti - chains and . ${\displaystyle \{\emptyset \}}$ ${\displaystyle \{X\}}$
16. ↑ The number of free distributive lattices with generators is referred to as or also with . So it is . ${\displaystyle n}$ ${\displaystyle {\psi }(n)}$ ${\displaystyle D(n)}$ ${\displaystyle M(n)={\psi }(n)+2=D(n)+2}$
17. ↑ Status: 2013
18. ↑ ^{a b} Ganter: p. 43.
19. ↑ Follow A000372 in OEIS
20. ↑ is the national capital O symbol . ${\displaystyle {\mathcal {O}}}$
21. ↑ Kung-Rota-Yan: p. 147.
22. ↑ Ganter: p. 42.
23. ↑ Jech: pp. 84 ff, 114 ff, 201 ff.