Embeddings

 

The most recent activity in Boolean layer cakes as orders has concerned their suborders: Let Q be any Boolean layer cake; we seek to characterize ordered sets P which have an order-preserving embeddeding e into Q, possibly with additional constraints on the map e.

There exists a vast literature on an ``unordered version'' of this problem: Let the covering graph of the Boolean lattice (for some natural number n); is commonly called a hypercube. Here the question reads: Which graphs may be (graph-)embedded into , possibly with certain constraints on the embedding map? Such questions are surveyed in [30]. We note here that graphs allowing an embedding into some hypercube are characterized in [29], and that it is an NP-complete problem to decide whether a given graph occurs as a subgraph of of a hypercube ([37]. Embeddability with constraints is studied, e.g., in [12] (preserving distances) or in [7] (minimizing dilation or expansion).

The first to consider the ordered version apparently is Wild [49]. Focussing on the ``full'' layer cake , he characterizes 0,1-orders P which embed into some such that covers are preserved, i.e., satisfies whenever in P.

Wild's characterization is in terms of a certain graph associated to P: Assume that P has 0 and 1. Let PQ(P) be the set of all prime quotients of P, i.e., . Call an upper transpose of iff , but ; lower transposes are defined dually. (x,y) and (u,v) are strongly projective iff one pair may be obtained from the other via a sequence of upper and lower transposes. Strong projectivity is an equivalence relation on PQ(P), denote by G(P) the set of all strong projevtivity classes of PQ(P). Abusing notation, let G(P) also be the graph with vertex set G(P) and an edge between iff there are and such that or .

An order P is called ranked iff it admits a rank function such that whenever in P. The chromatic number of a graph G is the least number of colors needed to color the vertices of G in such a way that no edge joins two vertices of the same color. Wild's main result in [49] now states that a 0,1-order P admits a cover-preserving embedding e into iff .

The following result from [49] concerns a border-line case between the ordered and unordered version of our problem. Call an order-preserving embedding between orders P and Q isometric iff the derived graph embedding between the covering graphs of P resp. Q preserves graph distance (that is, the number of edges in a shortest path between any two vertices). Wild proves that any 0,1-order P is isometrically order-preserving embeddable into iff the covering graph of P is isometrically embeddable into the corresponding hypercube graph . In other words, the property of being ``isometrically order embeddable into a Boolean lattice'' is an invariant of covering graphs of 0,1-orders.

We now turn to 2-layer cakes P(i,i+1;n) and address the question which orders Q allow a cover-preserving embedding into P(i,i+1;n). These orders are characterized by Mitas and Reuter in [42] in terms of certain edge-colorings of their covering graphs, much in the spirit of [29]. Of course, such orders must be of height one, respectively their covering graphs bipartite. Let G be any bipartite graph endowed with some edge-coloring. Given any path in G, write for the number of colors which occur an odd number of times on . Call the coloring admissible iff it satisfies the following conditions: (1) If two edges of the same color are connected by a path of other colors, then the number of edges of is even (and nonzero); (2) If is any path between any two vertices x and y, then 2.1 iff x=y, 2.2 iff and is an edge of G, 2.3 iff and is not an edge of G. The main result of [42] states that a height one order P admits a cover-preserving embedding into some P(i,i+1;n) iff there exists an admissible edge-coloring of the covering graph of P.

Mitas and Reuter also prove that there is no finite family of forbidden suborders whose absence characterizes orders admitting a cover-preserving embedding into some P(i,i+1;n). They pose the following (open) problem: Is it NP-complete to decide whether a given height one order admits such an embedding?

In [43], Mitas and Reuter provide an in-depth study of - in parallel - graph homomorphisms into hypercubes and of order-preserving maps into Boolean lattices (that is, ``full'' layer cakes). We report here on the ordered part. If P is any ordered set, write C(P) for its directed covering graph. We need to formulate a number of conditions on arc-colorings of C(P). Given any such coloring and any path in C(P), let be the set of colors appearing an odd number of times on , and (as above). Consider the following conditions: (D) The direction of the arcs of the same color alternate on every path in C(P); (1) oc(C)=0 for every circuit C in C(P); (2) for every path in C(P); for every path between any two vertices x and y of C(P), implies that x and y are adjacent.

Some of the main results of [43] are, for an ordered set P:

• P admits a cover-preserving mapping into some iff C(P) dmits an arc-coloring satisying (D) and (1) iff P is ranked,
• P admits a cover-preserving embedding into some iff C(P) admits an arc-coloring satisfying (D), (1) and (2),
• P admits an embedding e into some such that in P if and only iff C(P) admits an arc-coloring satisfying (D), (1), (2) and (3).

A more intricate condition even characterizes embeddings such that both e and preserve both covers and order. Again, none of the situations just considered may be characterized by excluding a finite list of orders as suborders of P.