2
$\begingroup$

Let $P_n$ be the lattice of set partitions of $[n] = \{1,2,\dots,n\}$, let $B_n$ be the Boolean algebra of subsets of $[n]$.

Is there some $n_0$ such that for all $n \ge n_0$ it is possible to embed $B_n$ into $P_n$?

If this is indeed possible, then I would be interested in extending the construction to embedding $B_n$ into $P_{N(n)}$ for all sufficiently large $n$, where $N(n) < n$, or even $N(n) = o(n)$.


Background

As pointed out in the question What is the smallest partition lattice PART(M) containing the lattice P(N) of subsets of a finite set of N elements it is a textbook exercise that $N(n)=n+1$ suffices. Use the additional element to indicate which block of the partition contains the chosen subset, by including it in that block. In this case $n_0 = 1$. Moreover, with $n_0=1$ we cannot do better than $N(n)\ge n+1$ because of the sequences of sizes of $B_n$ and $P_n$ for small $n$ (see http://oeis.org/A000110 for the sequence of sizes of $P_n$, which begins 1, 2, 5, 15, 52 versus the sequence $2^n$ which begins 2, 4, 8, 16, 32). However, the size of $P_n$ grows as $n^{n(1-o(1))}$, so for large enough $n$ there might be "enough room" for an embedding to be possible.

In any case, we cannot do better than $N(n) = \Omega(n/\log n)$, but is perhaps $N(n) = O(n/\log \log n)$ possible?

Pudlák and Tůma showed that every finite lattice can be embedded into some $P_n$ for large enough $n$, even preserving the least and greatest elements. (See also related question Embedding finite lattices into the lattice of partitions of a finite set.) Their result is via products and it is not clear that it is possible to provide constructive upper bounds on $N(n)$ using their construction. It does seem clear that $N(n) \gg n$ in their very general setting, which has to "make room" for every possible finite lattice structure, not just Boolean algebras.

  • Pavel Pudlák and Jiří Tůma, Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis 10 74–95, 1980. doi:10.1007/BF02482893
$\endgroup$
  • 5
    $\begingroup$ I do not understand your question. The longest chain of $P_n$ has length $n-1$. The longest chain of $B_n$ has length $n$. Therefore it is never possible to embed $B_n$ into $P_n$. $\endgroup$ – Richard Stanley Nov 22 '17 at 17:17
  • $\begingroup$ @RichardStanley, thank you, that is an observation that eluded me but completely answers the question. $\endgroup$ – András Salamon Nov 22 '17 at 23:15
2
$\begingroup$

As to embedding $B(n)$ into $\operatorname{Part}(n+1)$, it is easily seen that more generally each distributive lattice $D$ of length $n$ embeds into $\operatorname{Part}(n+1)$. In fact, many modular length $n$ lattices $M$ work as well. More details can be found in the paper "Tight embedding of modular lattices into partition lattices: progress and program".

Regards, Marcel Wild

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.