𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Size of the Largest Antichain in the Partition Lattice

✍ Scribed by E.Rodney Canfield

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
268 KB
Volume
83
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

Consider the poset 6 n of partitions of an n-element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. Let a= 1 2 &e log(2)Γ‚4. We prove the following upper bound for the ratio of the size of the largest antichain to the size of the largest rank:

for suitable constant c 2 and n>1. This upper bound exceeds the best known lower bound for the latter ratio by a multiplicative factor of O(1).

πŸ“œ SIMILAR VOLUMES

Partitioning the Boolean Lattice into Ch
Partitioning the Boolean Lattice into Chains of Large Minimum Size
✍ Tim Hsu; Mark J. Logan; Shahriar Shahriari; Christopher Towse πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 187 KB

Let 2 [n] denote the Boolean lattice of order n, that is, the poset of subsets of {1, ..., n} ordered by inclusion. Recall that 2 [n] may be partitioned into what we call the canonical symmetric chain decomposition (due to de Bruijn, Tengbergen, and Kruyswijk), or CSCD. Motivated by a question of FΓΌ

The lattice of antichain cutsets of a pa
The lattice of antichain cutsets of a partially ordered set
✍ Gerhard Behrendt πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 125 KB

## Behrendt, G., The lattice of antichain cutsets of a partially ordered set, Discrete Mathematics 89 (1991) 201-202. Every finite lattice is isomorphic to the lattice of antichain cutsets of a finite partially ordered set whose chains have at most three elements. A subset A of a partially order

The size of the largest hole in a random
The size of the largest hole in a random graph
✍ Tomasz Łuczak πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 775 KB

Let H(n, p) denote the size of the largest induced cycle in a random graph C(n, p). It is shown that if the expected average degree of G(n, p) is a constant larger than 1, then H(n, p) is of the order n with probability 1 -o(l). Moreover, for C(n, p) with large average degree, H(n, p) is determined

Chains in the lattice of noncrossing par
Chains in the lattice of noncrossing partitions
✍ Paul H. Edelman; Rodica Simion πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 735 KB

The lattice of noncrossing set partitions is known to admit an R-labeling. Under this labeling, maximal chains give rise to permutations. We discuss structural and enumerative properties of the lattice of noncrossing partitions, which pertain to a new permutation statistic, m(a), defined as the num

On the structure of the lattice of noncr
On the structure of the lattice of noncrossing partitions
✍ Rodica Simion; Daniel Ullman πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 882 KB

Simion, R. and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Mathematics 98 (1991) 193-206. We show that the lattice of noncrossing (set) partitions is self-dual and that it admits a symmetric chain decomposition. The self-duality is proved via an order-reversing i