Separability, Boxicity, and Partial Orders

Order https://doi.org/10.1007/s11083-023-09628-8 Separability, Boxicity, and Partial Orders José-Miguel Díaz-Báñez1·Paul Horn2·Mario A. Lopez3·Nestaly Marín4· Adriana Ramírez-Vigueras5·Oriol Solé-Pi6·Alex Stevens2·Jorge Urrutia5 Received: 2 March 2022 / Accepted: 23 February 2023 © The Author(s) 2023 Abstract A collection S={Si,...,Sn}of disjoint closed convex sets in Rdis separable if there exists a direction (a non-zero vector) −→ vof Rdsuch that the elements of Scan be removed, one at a time, by translating them an arbitrarily large distance in the direction −→ vwithout hitting another element of S.WesaythatSi≺Sjif Sjhas to be removed before we can remove Si. The relation ≺defines a partial order P(S,≺)on Swhich we call the separability order of S and −→ v. A partial order P(X,≺)on X={x1,...,xn}is called a separability order if there is a collection of convex sets Sand a vector −→ vin some Rdsuch that xi≺xjin P(X,≺)if and only if Si≺Sjin P(S,≺). We prove that every partial order is the separability order of a collection of convex sets in R4, and that any poset of dimension 2is the separability order of a set of line segments in R3. We then study the case when the convex sets are restricted to be boxes in d-dimensional spaces. We prove that any partial order is the separability order of a family of disjoint boxes in Rdfor some d≤ n 2+1. We prove that every poset of dimension 3has a subdivision that is the separability order of boxes in R3, that there are partial orders of dimension 2that cannot be realized as box separability in R3and that for any dthere are posets with dimension dthat are separability orders of boxes in R3.Wealso prove that for any dthere are partial orders with box separability dimension d;thatis,dis the smallest dimension for which they are separable orders of sets of boxes in Rd. Keywords Partially ordered sets ·Separability ·Order dimension ·Boxicity 1 Introduction Let S={S1,...,Sn}be a set of disjoint convex sets in Rd,and−→ vbe a direction, i.e. a non-zero vector of Rd. We say that Sjblocks Siif when we translate Sialong the direction −→ vit hits Sj, i.e. if there is a point p∈Siand a point q∈Sjsuch that q=p+λ−→ vfor some λ>0. The blocking relation on Sis acyclic if there are no Sσ0,...,Sσr−1such that Sσi+1blocks Sσi,i=0,...,r−1, addition taken mod r. BOriol Solé-Pi [email protected] Extended author information available on the last page of the article 123 Order An acyclic blocking relation induces a partial order P(S,≺), which we will call the separability order of S.Inthisorder,Si≺Sjif Sjblocks Sior there is a sequence Si= Sσ1,...,Sσt=Sjof elements of Ssuch that Sσk+1blocks Sσk,k=1,...,t−1. In what follows we will deal only with separable families of disjoint convex sets and assume that −→ v=(0,...,0,1); for this reason, and to avoid cumbersome notation, we will only refer to P(S,≺), and omit −→ v.IfSi≺Sjwe will sometimes say that Siis below Sj, or that Sjis above Si; that is we will assume that we translate our sets upwards along the direction of the last coordinate axis. In particular, in R2and R3we will move our sets up, see Fig. 1. Let X={x1,...,xn},andP(X,≺)be a partial order on X. We say that P(X,≺)is the separability order of a family of sets S={S1,...,Sn}if xi≺xjif and only if Si≺Sj. It is easy to see that not all posets are separability orders of collections of connected sets in R3. Indeed, take any non-planar graph, e.g. K3,3and consider the partial order P(X,≺) such that the elements of Xare the edges and vertices of K3,3in which a vertex vis smaller than an edge eif vis a vertex of e.Sinden[1] and, independently, Ehrlich et al. [2] proved that the graph obtained by inserting a vertex in the middle of each edge of any non-planar graph, e.g. K3,3, is not an intersection graph of connected sets on the plane, for otherwise this would yield a planar representation of K3,3,seeFig.2. It follows easily that P(X,≺) is not a separability order of any family of convex sets in R3, for otherwise projecting these sets on the plane would yield a planar representation of K3,3. Sinden and Herlich et al.’s result that not all graphs are intersection graphs of connected sets on the plane does not generalize to higher dimensions. In fact, Tietze [3] proved in 1905 that any graph is the intersection graph of a family of convex sets in R3. Using Tietze’s result, we will prove that any partial order P(X,≺)is the separability order of a set of disjoint convex sets in R4. We also prove that any partial order of dimension two is the separability order of line segments in R3. We then turn our attention to the case when S={S1,...,Sn}is a set of axis-aligned boxes in Rk. Our results will use Roberts [4] boxicity theorem that any graph with nvertices is the intersection graph of a set of axis-aligned boxes in Rkfor some k≤n/2. Thebox separability dimension ofapartialorder P(X,≺)isthesmallestintegerksuchthat there is a set Sof disjoint axis-aligned boxes in Rksuch that P(X,≺)is the separability order of S. We prove that for any kthere are partial orders such that their box separability dimension Fig. 1 aA family of convex sets S={S1,...,S6}on the plane. bThe separability order P(X,≺)of S 123 Order Fig. 2 aGraph obtained from K3,3by inserting a vertex si,jin the middle of each edge joining xiand yj.b Covering graph of a partial order that is not a separability order of any family of convex sets in R3 is k, and that every partial order can be embedded, via edge subdivision, in another partial order with box separability dimension at most four. We obtain partial orders of dimension two that are not separability orders of sets of boxes in R3. Using the well-known planar partial orders of Kelly [5](seeFig.6) we prove that for any dthere is a partial order of dimension dthat is the separability order of a set of boxes in R3. 2 Previous Work Given a collection of disjoint convex sets Sin Rd,d≥2, it is well known that it is not always possible to assign to each of them a direction of motion such that all the sets in the collection can be separated, one by one, by translating each of them by an arbitrarily large distance along its assigned direction without hitting another element of S, see Dawson [6]. When such an assignment of directions is possible, we call S separable.Dawsonalsoproved that given any family of mdisjoint spheres in Rdit is always possible to remove at least min{m,d+1}spheres without disturbing other spheres. It is important to remark that if we allow the convex sets to move simultaneously, instead of one at a time, then any family of disjoint convex sets can be separated. An easy way to see this is to imagine that all the sets contract at the same rate, increasing the relative distances among them (with respect to their size). Separability problems of families of convex sets in the plane and in R3have been studied for some time in both Computational Geometry and from the point of view of ordered sets, see [7–12]. In general, separability problems involve families of disjoint convex sets in Rd which we want to remove, one at a time, while avoiding collisions with other elements. It is known that any set Sof convex sets in the plane is separable, and that the separability orders they generate are truncated planar lattices, see Rival and Urrutia [9]. If the elements of Sare assigned one of mdifferent directions of motion, P(S,≺)is called an m-directional ordered set. In [9] it is shown that every ordered set has a two-directional plane point representation using subdivisions, and that there exist posets that are not m-directional ordered sets at all. G. X. Viennot [13] studied a combinatorial problem arising from heap of pieces,which may be thought of as a collection of lego-like blocks, piled in some way. An ordered set arises in which a block Ais smaller than a block Bif the removal of Afrom the pile involves 123 Order the previous removal of B. A somewhat similar problem in which we now seek to remove sets of disjoint convex sets on the plane was studied by Díaz-Báñez et al. in [14], where the problem of removing the smallest number of convex sets enclosing a valuable object buried among them is studied. 3 Notation and Definitions Apartially ordered set P(X,≺), for short a poset, is a pair consisting of a set X,andabinary relation ≺on Xthat is irreflexive and transitive. Let X={x1,...,xn}. Two elements xiand xjof Xare comparable if xi≺xjor xj≺xi.Alinear order L of Xis a partial order such that any pair of elements of Xare comparable. Alinear extension L of P(X,≺)is a linear order such that for any xi,xj∈X,xi≺xj in P(X,≺)implies xiis smaller than xjin L. Given a set of linear orders {L1,...,Lk} on a set X,theintersection of them, is the partial order P(X,≺)such that xi≺xjif and only if xiis smaller than xjin Lr,r=1,...,k.Arealizer of P(X,≺)is a set of linear extensions {L1,L2,...,Lm}of Xsuch that m i=1Li=P(X,≺).Thedimension of P(X,≺),dim(P(X,≺)), is the least number msuch that P(X,≺)has a realizer of size m. Hiraguchi [15] showed that the dimension of a partial order on nelements is at most n 2. Achain of P(X,≺)is a set C⊆Xof pairwise comparable elements in P(X,≺).An antichain of P(X,≺)is a set A⊆Xwhose elements are pairwise incomparable in P(X,≺). The height of P(X,≺)is defined as the maximum length of a chain in P(X,≺).Wesaythat a partial order is bipartite if its height is 2. The width of P(X,≺)is the maximum size of an antichain in P(X,≺). The comparability graph of P(X,≺), denoted as GP, is the undirected graph with vertex set Xsuch that (xi,xj)∈E(GP)if and only if xiand xjare comparable. Given xi,xk∈X, we say that xkcovers xiif xi≺xkand there is no xj∈Xsuch that xi≺xj≺xk.The covering graph of P(X,≺)is the subgraph G Pof GPin which (xi,xj)is an edge of G Pif and only if xicovers xjor xjcovers xi. Asubdivision of a partial order P(X,≺)is any other partial order that can be obtained by repeated applications of the following operation: take xi,xj∈Xsuch that xi≺xjand add an element xto Xwith xi≺x≺xj, extend this relation so that it is transitive. Ak-dimensional box,ork-box, is a Cartesian product of closed intervals [a1,b1]× [a2,b2]×...×[ak,bk], that is, the set of points (y1,...,yk)in Rksuch that ai≤yi≤bi, i=1,...,k. Let Gbe a graph with nvertices {v1,...,v n}.Gis the intersection graph of a family of sets {S1,...,Sn}if two vertices vi,vjof Gare adjacent if and only if Siand Sjintersect. We will use two classical results on the representation of graphs as intersection graphs of convex sets in Euclidean spaces. Theorem 3.1 (H. Tietze [3]) Any graph is the intersection graph of families of convex sets in R3. Theorem 3.2 (Roberts [4]) Any graph with n vertices is the intersection graph of a set of k-boxes in Rk,k≤ n 2. The smallest kfor which such a set of boxes exists is called the boxicity of G,andis denoted as Box(G). 123 Order 4 Bounds on Separability Dimension In this section we will prove the following results: Theorem 4.1 Any poset is the separability order of a family of convex sets in R4. Theorem 4.2 Any poset P(X,≺)is the separability order of sets of boxes in Rk,forsome k≤n/2+1. To prove our results we need the following lemma: Lemma 4.1 Suppose that the comparability graph of a poset P(X,≺)is the intersection graph of a family of convex sets in Rk.ThenP(X,≺)is a separability order of translates of those convex sets in Rk+1. The same is true if the cover graph of P(X,≺)is an intersection graph of convex sets in Rk. Proof Let X={x1,...,xn}, and suppose that the comparability graph GPof P(X,≺)is the intersection graph of a family of convex sets {S1,...,Sn}in Rk.LetSibe the set representing xi, and suppose that the labels of the elements of Xare such that if xi≺xj,theni<j, i.e. xi<... < xnis a linear extension of P(X,≺). Lift S1,...,Snto convex sets S 1,...,S nin Rk+1in such a way that any point p= (y1,...,yk)that belongs to Siis mapped to the point p=(y1,...,yk,iλ),forsomeλ>0, i=1,...,n. It is now easy to see that P(X,≺)is the separability order of {S 1,...,S n}. The statement for cover graphs can be shown to be true in the same way.  Theorems 4.1 and 4.2 follow directly applying Tietze’s and Robert’s results to the comparability graph of P(X,≺). In view of Theorem 4.1, the reader may wonder if any poset is the separability order of sets of boxes of Rkfor a fixed k. We prove next that this is not true. We present a brief argument, in the spirit of a bound of Alon and Scheinerman from [16] regarding the dimension of containment orders, showing that any sufficiently large class of nelement posets must contain posets whose box separability dimension is large. The key observation is the following. Observation 4.1 If P(X,≺)is an n-element partial order realized as separability of boxes in Rd,thenP(X,≺)is representable as separability of boxes whose coordinates are integers in [2n]d. From this it easily follows that Theorem 4.3 Suppose Cis a collection of n element partial orders. Then if all partial orders in Care separability orders of boxes in Rd, d≥log |C| 2nlog(2n) Proof Suppose all posets in Ccan be realized in Rd. Per Observation 4.1, any partial order in Ccan be represented with coordinates in [2n]d. A single box is determined by two opposite corners and hence at most ([2n]2d)n=2n2dn distinct partial orders are representable in Rd. Noting that 2n2dn ≥|C|and solving for d gives the result. 123 Order 4.1 Boxicity and Box Separability Dimension As one might expect, the box separability dimension and the boxicity of posets turn out to be closely related. Indeed, we have that: Theorem 4.4 Let P(X,≺)be a partial order. Then Bsep(P(X,≺)) =1+min{Box(G): G P⊆G⊆GP}, where the minimum is taken over all graphs that are simultaneously supergraphs of the covering graph and subgraphs of the comparability graph. Proof We first bound Bsep(P(X,≺)) from above. Consider Gsuch that G P⊆G⊆GP. Then Gcan be realized as the intersection graph of boxes in Box(G)dimensions. Lift the boxes using one additional dimension, as was done in the proof of Lemma 4.1. In this way P(X,≺)can be realized as box separability in RBox(G)+1. Now we prove the matching lower bound. Suppose that P(X,≺)is the separability order of a set Sof boxes in Rd. Project the boxes of Sonto the (d−1)-dimensional space formed by the first d−1 coordinates, and let Gbe their intersection graph. Notice that all edges in the covering graph G Pmust be present in Gand, therefore, G P⊆G. Also note that no edges in Gwill be absent from the comparability graph of P,andsoG⊆GP. Therefore G P⊆G⊆GPand we have d−1≥Box(G). Putting everything together, Bsep(P(X,≺)) =1+min{Box(G):G P⊆G⊆GP}. Since G P=GPfor all bipartite orders, we have the following corollary. Corollary 4.1 If P(X,≺)is bipartite, then Bsep(P(X,≺)) =Box(GP)+1. 4.2 Other Bounds It was shown by Adiga et al. in [17]that Box(GP) (χ(GP)−1)≤dim(P(X,≺)) ≤2Box(GP),where χ(GP)denotes the chromatic number of the comparability graph GP. We use this result, along with Corollary 4.1, to bound Bsep(P(X,≺)). Theorem 4.5 All bipartite partial orders that can be realized as box separability in Rd+1 have dimension at most 2d. The bound is tight. Proof Since P(X,≺)is bipartite, we have that dim(P(X,≺)) 2≤Box(GP)=Bsep(P(X,≺ )) −1. To show that the bound is tight, consider Hiraguchi’s bipartite poset Hn,nconsisting of 2nelements {a1,...,an,b1,...,bn}such that aiis smaller than bjfor all i= j.Itis well known that the dimension of Hn,nis n.ItwasshownbyTrotter[18] that the boxicity of the comparability graph of Hn,nis n 2. It follows now that the box separability dimension of Hn,nis n 2+1.  From the above paragraph, we get the following. Corollary 4.2 For any d there are posets such that their box separability dimension is exactly d. Theorem 4.6 For any poset P(X,≺),Bsep(P(X,≺)) ≤dim(P(X,≺))(χ(GP)−1)+1. Proof We have Bsep(P(X,≺)) ≤Box(GP)+1≤dim(P(X,≺))(χ(GP)−1)+1, as desired. 123 Order 5 Subdivision and Separability Dimension Recall that a subdivision of a poset P(X,≺)is obtained by repeating the following operation several times: take xi,xj∈Xsuch that xi≺xjand add an element xto Xwith xi≺x≺xj. The subdivision of posets is a well studied concept, for instance it is well known that, in general subdivisions of posets may increase their dimension, as proved by Spinrad in [19]. In this section we show some somewhat surprising results. We will show that for any poset P(X,≺)it is always possible, via subdivision, to find a partial order with box separability dimension at most 4. We also prove that any poset of dimension 3 has a subdivision with box separability dimension at most 3. Theorem 5.1 Every poset of dimension at most 3has a subdivision which can be realized as box separability in R3. Proof Let P(X,≺)be a partial order of dimension 3, and {L1,L2,L3}linear extensions of P(X,≺)such that their intersection is P(X,≺).RepresentP(X,≺)as a vector dominance order in space, i.e. for each element xi∈Xassign a point with integer coordinates (ai,bi,ci) such that the values of ai,biand cicorrespond to the position of xiin Li,i=1,2,3. For each xi∈X, place a sufficiently small box Bicentered at (ai,bi,ci)such that the projections onto the xy-plane of any two boxes representing incomparable elements of P(X,≺)are disjoint. For any two elements xi≺xjthat are adjacent in the covering graph of P(X,≺),wedo the following: Consider the line segment i,jjoining (ai,bi,ci)to (aj,bj,ci).Noticethat this segment lies in the horizontal plane that contains (ai,bi,ci). Place a sufficiently large number of equidistant points {p1,...pm}in i,j, and then a sufficiently small box centered at each of these points such that the projection of the box Bpion the xy-plane intersects only the projection of boxes Bpi−1and Bpi+1; the projections of Bp1and Bpmmust intersect the projections of Biand Bjrespectively. We can alter the heights of the boxes slightly so that the boxes are disjoint and Bp1,...,Bpmare the steps of an ascending stair, see Fig. 3. Clearly, if xi≺xjthen Bi≺Bjin the separability order of the resulting collection of boxes B. All that is left to show is that no undesired comparability appears in the separability Fig. 3 aTwo elements xiand xjsuch that xi≺xj, and the line segment i,jjoining them. bA collection of boxes such that Bi≺Bjin its separability order 123 Order order. Any such comparability, if it exists, must arise from the intersection of the projections of the boxes of two stairs, as described in the last paragraph. Consider xi,xj,xk,xl∈Xsuch that xi≺xjand xk≺xland suppose that the projections of the segments i,jand k,lcross each other (if this does not happen we can easily ensure that the projections of the steps of their corresponding stairs are disjoint by taking small enough boxes). Without loss of generality, assume that ci<ck, then the stair of boxes from xito xjpasses below the one from xkto xland, thus, Bi≺Blin the separability order. The fact that the projections of i,jand k,lintersect implies that ai<aland bi<bl, furthermore, ci<ck<cl, which yields xi≺xl. This completes the proof. In a similar way we can now prove the next result: Theorem 5.2 Every poset P(X,≺)has a subdivision which can be realized as box separability in R4.1 Proof Assume that the elements of Xare labelled x1,...,xnsuch that if xi≺xjin P(X,≺), then i<j, i.e. x1< ... < xnis a linear extension of P(X,≺). Map the elements of Xto a set of points {pi=(ai,bi,ci)|1≤i≤n}in general position in R3, observe that no two segments joining pairs of points in this set intersect, except at a common endpoint. Consider the covering graph of P(X,≺), and map each pi=(ai,bi,ci)to the point p i=(ai,bi,ci,i) inR4.PlaceasmallboxBicenteredat p iforeachi.Foreachpairi,jwith xi≺xjin P(X,≺) such that the edge joining them is an edge in the covering graph G P, consider the line segment i,j∈R4joining p ito p j. Subdivide as in the proof of Theorem 5.1 and place a small box centered at each of the subdivision points. These boxes form a chain that implies Bi≺Bjin the separability order of the collection of boxes thus obtained. All that is left to do is show that there are no undesired comparabilities in the separability order. This follows from the observation that the projections of any two segments i,j, k,lonto R3do not cross.  It is not hard to construct a representation in which each edge has been subdivided at most a constant number of times and, thus, the number of boxes is O(n2). The proof of Theorem 4.3 can easily be adapted to obtain an almost matching lower bound on the number of subdivisions required. Theorem 5.3 There is an n vertex partial order P(n,≺)that requires at least ( n2 logn)boxes to represent as a subdivision in R4. Proof Suppose every nvertex partial order has a subdivision which can be realized as box separability in R4with at most Nboxes. It is easy to see, then, that a subdivision of all n element posets can be realized with exactly Nboxes. But as in the proof of Theorem 4.3, there are at most (2N)8Nposets on Nboxes representable in R4. Thus, (2N)8Nmust be at least the number of nelement posets. As there are 2(1+o(1))n2/4posets on nelements, the result follows.  Using the technique from Theorem 5.2, one can easily derive Theorem 5.4 Every poset P(X,≺)with a planar cover graph has a subdivision which can be realized as box separability in R3. 1It has been called to our attention by one of the referees that using Theorem 4.4 and Lemma 12 of [20], it is possible to obtain an alternative proof of Theorem 5.2. 123 Order 6 Low Dimension Representations While posets that are separability orders of families of disjoint convex sets on the plane are well known, they are truncates planar lattices [9], not much is known on separability orders of convex sets in R3. We start this section studying the following question: Is it true that any poset of dimension two and three is the separability order of sets of boxes in R3? We construct partial orders of dimension two and three with box separability dimension larger than three. A well-known fact in the study of order dimension of posets is that if the dimension of a poset is at least two, then substituting each element by an antichain does not affect its dimension, regardless of the size of the antichains. In Fig. 4a we substituted each element of a poset by an antichain of size 3. This observation will be key in the two following results. Theorem 6.1 There are partial orders of dimension 2that cannot be realized as box separability in R3. Proof Consider the partial order P(X,≺)with five elements shown in Fig. 4a and replace each element for an antichain with kelements for some large k(this will be made more precise in a moment), see Fig. 4b. Suppose that the resulting poset, which is of dimension 2, is realizable as box separability in R3. Take any two of the antichains such that all elements in one of them cover all elements in the other and project all the corresponding boxes onto the xy-plane. Consider a graph which has a vertex for each of these projections and an edge between two vertices if at least one of corners of the two corresponding projections lies inside the other projection. Since no two elements of an antichain are comparable, the graph is bipartite and, because no corner lies in two boxes of the opposite antichain, there are no more than 4kedges. Thus, for any integer l,ifwetakekto be large enough, we can choose 2lvertices, lon each antichain, so that no two of them are adjacent. From now on we will ignore the boxes of these antichains that do not belong to this complete bipartite graph. By taking a large enough k, we may repeat this process for each such pair of antichains to obtain a collection of boxes whose separability order is the result of substituting each element of P(X,≺)for an antichain of size 2 and, furthermore, no projection of one of these boxes contains a corner of the projection of another box. Observe that the two boxes in an antichain, because they both lie above or below another box (from the antichain directly Fig. 4 aA partial P(X,≺)order on five elements bThe result of substituting every element of P(X,≺)by an antichain of size 3 123