The size of the largest antichain in the partition lattice
type: Item
instance of: scholarly article
title: The size of the largest antichain in the partition lattice
zbMATH Open document ID: 0908.05008
author: E. Rodney Canfield
published in: Journal of Combinatorial Theory. Series A
publication date: 1999-03-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 1212977
zbMATH Keywords: regular poset
zbMATH Keywords: poset of partitions
zbMATH Keywords: antichain
zbMATH Keywords: Stirling number
zbMATH Keywords: Sperner theory
reviewed by: Konrad Engel
MaRDI profile type: Publication
OpenAlex ID: W2066116816
cites work: Q3050437
cites work: Q4044544
cites work: Independent process approximations for random combinatorial structures
cites work: A generalization of Sperner's lemma
cites work: On a problem of Rota
cites work: Large antichains in the partition lattice
cites work: Q4863412
cites work: A counterexample to the generalisation of Sperner's theorem
cites work: Optimal representations of partially ordered sets and a limit Sperner theorem
cites work: Q4338928
cites work: Some Results on Matching in Bipartite Graphs
cites work: Stirling Behavior is Asymptotically Normal
cites work: On a continuous analog of Sperner's problem
cites work: Maximal sized antichains in partial orders
cites work: Q3226891
cites work: On Rota's problem concerning partitions
cites work: Random set partitions: Asymptotics of subset counts
cites work: A simple counterexample to a conjecture of Rota
DOI: 10.1006/JCTA.1998.2871
Recommended article: Size of the largest antichain in a partition poset
Recommended article: Large antichains in the partition lattice
Recommended article: An upper bound for the size of the largest antichain in the poset of partitions of an integer
Recommended article: Q4863412
Recommended article: On the size of maximal antichains and the number of pairwise disjoint maximal chains
Recommended article: On the size of maximal chains and the number of pairwise disjoint maximal antichains
Recommended article: Maximal antichains of minimum size
Recommended article: Maximum-sized antichains in minimal posets
Recommended article: About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
description: scientific article; zbMATH DE number 1212977