Cover-Preserving Order Embeddings into Boolean Lattices

NEW

Problem: Reconstructed statement: for a finite poset $Q$, characterize when there is an isometric order embedding

$$\varphi:Q\to 2^{[n]}$$

such that

$$x\le_Q y \iff \varphi(x)\subseteq \varphi(y), \qquad d_{\Gamma(Q)}(x,y)=|\varphi(x)\triangle\varphi(y)|$$

for all $x,y\in Q$, where $\Gamma(Q)$ is the undirected cover graph. The section title “Isometric Order Embeddings of Posets into $2^n$” and the phrase “map $\varphi$ as above” support including both order-embedding and distance-preserving conditions. Assume $\Gamma(Q)$ is connected; otherwise ordinary graph distance is not finite between components.

Result: Such posets are exactly those whose cover graph is a partial cube and whose cover orientation is coherent on every Djoković–Winkler class.

Precisely, for an edge $ab$ of $\Gamma(Q)$, let

$$W_{ab}:=\{z:d(z,a)<d(z,b)\}.$$

Then $Q$ admits such a $\varphi$ iff:

1. $\Gamma(Q)$ is a partial cube;
2. whenever $a\prec b$ and $c\prec d$ are cover edges in the same Djoković–Winkler $\Theta$-class, one has

$$c\in W_{ab},\qquad d\in W_{ba}.$$

Equivalently, all upward cover edges in a fixed $\Theta$-class cross the corresponding partial-cube cut in the same direction.

Proof. If $\varphi$ exists, then $\Gamma(Q)$ is isometrically embedded in a hypercube, hence is a partial cube. A cover edge $a\prec b$ maps to two subsets differing in one coordinate, and because $\varphi$ is order-preserving, that coordinate is added, not removed. Edges in the same $\Theta$-class are precisely edges changing the same hypercube coordinate, so all upward edges in that class cross the same coordinate cut in the same direction. Thus condition 2 holds.

Conversely, assume 1 and 2. Let $\mathcal C=E(\Gamma(Q))/\Theta$. For each $\Theta$-class $C$, choose an upward edge $a_C\prec b_C\in C$, and define

$$H_C^-:=W_{a_Cb_C},\qquad H_C^+:=W_{b_Ca_C}.$$

By coherence this choice orients the cut consistently. Define

$$\varphi(x):=\{C\in\mathcal C:x\in H_C^+\}.$$

The standard partial-cube embedding theorem says this map is an isometric embedding of $\Gamma(Q)$ into $2^{\mathcal C}$. For a cover edge $x\prec y$ in class $C$, coherence gives

$$\varphi(y)=\varphi(x)\cup\{C\}.$$

Hence along every saturated chain the image only increases, so $x\le_Q y\Rightarrow \varphi(x)\subseteq\varphi(y)$.

Conversely, if $\varphi(x)\subseteq\varphi(y)$, take a shortest path in $\Gamma(Q)$ from $x$ to $y$. Its image is a shortest hypercube path from $\varphi(x)$ to $\varphi(y)$. Since the endpoint subsets are nested, every step adds one coordinate and removes none. By coherence, each corresponding cover edge is traversed upward in $Q$. Thus the path is a saturated chain from $x$ to $y$, so $x\le_Q y$. Therefore $\varphi$ is an isometric order embedding.

The least possible $n$ is $|E(\Gamma(Q))/\Theta|$.

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.