The size of the largest antichain in the partition lattice
Let \(\Pi_n\) be the poset of partitions of an \(n\)-element set, ordered by refinement, and let \(d(\Pi_n)\) be the size of the largest antichain in \(\Pi_n\). Moreover, let \(b(\Pi_n)\) be the size of the largest level in \(\Pi_n\), i.e. the largest Stirling number of the second kind where \(n\) is fixed and \(k\) varies. Let \(a:= 1/2-(e\log 2)/4\). The author proves that \(d(\Pi_n)/b(\Pi_n)\leq c\cdot n^a\cdot(\log n)^{-a-1/4}\) for a suitable constant \(c\) and \(n>1\). By a result of \textit{E. R. Canfield} and \textit{L. H. Harper} [Large antichains in the partition lattice, Random Struct. Algorithms 6, No. 1, 89-104 (1995; Zbl 0813.06002)] this upper bound is the best possible up to a multiplicative factor \(O(1)\). The main idea in the proof is the definition of an appropriate suborder (on the same basic set) for which the size of an antichain can be estimated using results from Sperner theory.
- Size of the largest antichain in a partition poset
- Large antichains in the partition lattice
- An upper bound for the size of the largest antichain in the poset of partitions of an integer
- Publication:4863412
- On the size of maximal antichains and the number of pairwise disjoint maximal chains
- On the size of maximal chains and the number of pairwise disjoint maximal antichains
- Maximal antichains of minimum size
- Maximum-sized antichains in minimal posets
- About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
- A counterexample to the generalisation of Sperner's theorem
- A generalization of Sperner's lemma
- A simple counterexample to a conjecture of Rota
- scientific article; zbMATH DE number 3645097 (Why is no real title available?)
- scientific article; zbMATH DE number 3112944 (Why is no real title available?)
- scientific article; zbMATH DE number 3458586 (Why is no real title available?)
- scientific article; zbMATH DE number 1016362 (Why is no real title available?)
- scientific article; zbMATH DE number 841566 (Why is no real title available?)
- Independent process approximations for random combinatorial structures
- Large antichains in the partition lattice
- Maximal sized antichains in partial orders
- On a continuous analog of Sperner's problem
- On a problem of Rota
- On Rota's problem concerning partitions
- Optimal representations of partially ordered sets and a limit Sperner theorem
- Random set partitions: Asymptotics of subset counts
- Some Results on Matching in Bipartite Graphs
- Stirling Behavior is Asymptotically Normal
- On a continuous analog of Sperner's problem
- About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
- An upper bound for the size of the largest antichain in the poset of partitions of an integer
- Chains, antichains, and complements in infinite partition lattices
- Size of the largest antichain in a partition poset
- Integer partitions and the Sperner property
- Order-matchings in the partition lattice
- The restricted partition lattices
- The width of downsets
- Morphisms for resistive electrical networks
- Superantichains in the Lattice of Partitions of a Set
- Chain lengths in the dominance lattice
- Large antichains in the partition lattice
- scientific article; zbMATH DE number 841566 (Why is no real title available?)
- The symmetric group, ordered by refinement of cycles, is strongly Sperner
- A lazy approach to symmetry reduction
This page was built for publication: The size of the largest antichain in the partition lattice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1269889)
