# Efficiently embedding finite Boolean algebras into lattices of set partitions?

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
• 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$. – Richard Stanley Nov 22 '17 at 17:17
• @RichardStanley, thank you, that is an observation that eluded me but completely answers the question. – András Salamon Nov 22 '17 at 23:15

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".