Cover-Preserving Order Embeddings into Boolean Lattices

NEW

Problem: Reconstructed statement: every finite length-one TBU-poset $Q$—in particular, every finite poset whose covering graph has no $4$-cycle—admits a cover-preserving order embedding into some Boolean lattice $2^{[n]}$. Here cover-preserving means that if $x\prec_Q y$, then $\varphi(y)=\varphi(x)\cup\{i\}$ for some coordinate $i$, and order embedding means

Result: The statement is false.

Let $P$ have elements

with order generated by three disjoint saturated chains

and no other comparabilities except those forced by transitivity.

Its covering graph is the theta graph consisting of three internally disjoint paths of length $3$ from $0$ to $1$. Hence every cycle has length $6$, so the covering graph has no $4$-cycles. It is also bounded, graded, bipartite, and satisfies the usual TBU uniqueness condition: incomparable pairs have at most one common upper cover and at most one common lower cover.

Suppose, for contradiction, that $\varphi:P\to 2^{[n]}$ is a cover-preserving order embedding. Put

Along each chain $0\prec a_i\prec b_i\prec 1$, the image changes by one coordinate at each step, so

Let $D=B\setminus A$, so $|D|=3$. Since each $a_i$ covers $0$,

for distinct $s_i\in D$. Thus $\{s_1,s_2,s_3\}=D$.

Similarly, since each $b_j$ is covered by $1$,

for some $2$-element subset $T_j\subset D$. Because $a_j<b_j$, we must have $s_j\in T_j$. But $T_j$ has two elements, so it also contains some $s_i$ with $i\ne j$. Therefore

Since $\varphi$ reflects order, this implies $a_i\le_P b_j$, contradicting the definition of $P$ for $i\ne j$.

Thus $P$ is a length-one TBU-poset but has no cover-preserving order embedding into any Boolean lattice.

Citation: No external counterexample citation used. Source question: Marcel Wild, “Cover-preserving order embeddings into Boolean lattices,” Order 9 (1992), 209–232, DOI: 10.1007/BF00383945.