Cover-Preserving Order Embeddings into Boolean Lattices

NEW

Problem: Reconstructed question: for a finite poset $P$, not necessarily having $0,1$, characterize when there is an isometric Boolean order embedding

such that

where $\Gamma(P)$ is the undirected cover graph. The section title “Isometric Order Embeddings” supports including the distance condition. The strict formulation is equivalent to the non-strict one for injective maps. A connected-cover-graph hypothesis is necessary, since ordinary graph distance is not finite between different components; $0,1$-posets automatically satisfy it.

Result: Yes. Let $\Theta$ be the Djoković–Winkler relation on edges of $\Gamma(P)$. For an oriented edge $ab$, write

Then a finite poset $P$ with connected cover graph admits such a $\varphi$ iff:

1. $\Gamma(P)$ is a partial cube;
2. the upward cover orientation is coherent on each $\Theta$-class: if $a\prec b$, $c\prec d$, and $ab\,\Theta\,cd$, then

Proof. Necessity: an isometric embedding of $\Gamma(P)$ into a hypercube makes $\Gamma(P)$ a partial cube. If $a\prec b$, then $\varphi(b)=\varphi(a)\cup\{i\}$ for a unique coordinate $i$. Edges in the same $\Theta$-class change the same coordinate, so all upward edges in that class cross the associated semicube cut in the same direction.

Sufficiency: assume (1) and (2). Let the coordinates be the $\Theta$-classes. For each class $C$, choose $a_C\prec b_C\in C$, set

and define

By the standard partial-cube embedding theorem, this map is isometric. Coherence gives, for every cover $x\prec y$ in class $C$,

Hence $x<y\Rightarrow \varphi(x)\subsetneq\varphi(y)$. Conversely, if $\varphi(x)\subsetneq\varphi(y)$, take a shortest path from $x$ to $y$. Its image is a shortest hypercube path from $\varphi(x)$ to $\varphi(y)$, so it only adds coordinates. Each step is therefore an upward cover edge, giving a directed cover chain from $x$ to $y$. Thus $x<y$.

This gives the desired adaptation; the minimal $n$ is the number of $\Theta$-classes.

Citation: Uses the classical partial-cube characterization of Djoković–Winkler: D. Ž. Djoković, “Distance-preserving subgraphs of hypercubes,” J. Combin. Theory B 14 (1973), 263–267. Source question: Marcel Wild, “Cover-preserving order embeddings into Boolean lattices,” Order 9 (1992), 209–232.