Searching in Random Partially Ordered Sets

(Extended Abstract)

R. Carmo^{1,2}^{⋆}, J. Donadelli^{2}^{⋆⋆}, Y. Kohayakawa^{2}^{⋆ ⋆ ⋆}, and E. Laber^{3}

1 Departamento de Informática Universidade Federal do Paraná Centro Politécnico da UFPR, 81531–990, Curitiba PR, Brazil

                    http://www.inf.ufpr.br
                      renato@inf.ufpr.br

2 Instituto de Matemática e Estatística Universidade de São Paulo Rua do Matão 1010, 05508–900 São Paulo SP, Brazil

                  http://www.ime.usp.br/mac
               {renato,jair,yoshi}@ime.usp.br

3 Departamento de Informática Pontifícia Universidade Católica do Rio de Janeiro R. Marquês de São Vicente 225, Rio de Janeiro RJ, Brazil

                  http://www.inf.puc-rio.br/
                    laber@info.puc-rio.br

Abstract. We consider the problem of searching for a given element in a partially ordered set. More precisely, we address the problem of computing efficiently near-optimal search strategies for typical partial orders. We consider two classical models for random partial orders, the random graph model and the uniform model. We shall show that certain simple, fast algorithms are able to produce nearly-optimal search strategies for typical partial orders under the two models of random partial orders that we consider. For instance, our algorithm for the random graph model produces, in linear time, a search strategy that makes O ((log n)^{1/2} log log n) more queries than the optimal strategy, for almost all partial orders on n elements. Since we need to make at least lg n = log_{2} n queries for any n-element partial order, our result tells us that one may efficiently devise near-optimal search strategies for almost all partial orders in this model (the problem of determining an optimal strategy is NP-hard, as proved recently in [1]).

⋆ Partially supported by PICDT/CAPES. ⋆⋆ Supported by a CNPq doctorate Studentship (Proc. 141633/1998-0).

⋆ ⋆ ⋆ Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–4) and by CNPq (Proc. 300334/93–1 and 468516/2000–0).

1 Introduction

A fundamental problem in data structures is the problem of representing a dynamic set S in such a way that we may efficiently search for arbitrary elements u in S. Perhaps the most common assumption about S is that its elements belong to some totally ordered set U. Here, we are interested in examining a certain variant of this problem, where the ‘universe’ U from which our elements are drawn is a partially ordered set. In fact, we address the basic problem of efficiently computing near-optimal search strategies for typical partial orders under two classical models for random partial orders: the random graph model and the uniform model.

The problem we consider is, intuitively speaking, as follows: suppose we are given a partial order S = (S, ≺), where S ⊂ U and ≺ is a partial order on U. We wish to construct a search strategy T that, given an arbitrary u ∈ U, determines whether or not u ∈ S. We suppose that T has access to an oracle that, given s ∈ S, replies whether or not s = u, and if this is not the case then tells T whether or not u ≺ s. We measure the efficiency of T by the number of queries that it needs to send to the oracle in the worst case (we maximize over all u ∈ U). Our problem may then be summarized as follows:

1. an instance is a partial order (S, ≺), its size given by the size of a directed acyclic graph representing its Hasse diagram;

2. a solution is a search strategy T;

3. the aim is to minimize number of queries in the worst-case performance of T, and

4. the number of steps needed to compute T is to be kept as low as possible.

We shall show that certain simple, fast algorithms are able to produce nearlyoptimal search strategies for typical instances under the two models of random partial orders.

1. Random graph model. In the random graph model, we randomly select a graph on the vertex set [n] = {1, …, n} and say that i ≺ j in our partial order if i < j and one may reach j from i along an ‘increasing path’ in the graph. (We in fact consider random graphs of density p, for constant p.) We present an algorithm that, in time linear in the size of the instance (S, ≺), produces a search strategy that makes at most

lg n + O ((log n)^{1/2} log log n)

queries in the worst case, for almost all n-element partial orders in this model (that is, with probability tending to 1 as n → ∞).

2. Uniform model. In the uniform model, we simply consider all partial orders on [n] equiprobable. The situation here is somewhat different: it is easy to show that almost all n-element partial orders are such that any search strategy makes at least

(\frac{1}{4} + o(1)) n

queries in the worst case. However, if we consider a slightly more ‘generous’ oracle, then almost all partial orders admit search strategies that require only

O(log n)

queries. Moreover, this search strategy may be computed in time O(n^{2}). For this result, we suppose that, presented with the query s ∈ S, the oracle replies whether or not s = u, and if this is not the case then it tells us whether u ≺ s, s ≺ u, or u is not comparable with s. Thus, our more generous oracle tells us exactly which of the three possibilities holds when u ≠ s, whereas the previous oracle only told us whether or not u ≺ s holds.

Since we need to make at least lg n queries for any n-element partial order, our result tells us that one may efficiently devise near-optimal search strategies for almost all partial orders in the first model, and we may devise search strategies for almost all partial orders in the second model that are only worse than the optimal by a constant factor. We remark that the constants hidden in the big-O notation and in the discussion above are not at all large.

Summarizing, (i) one may compute an essentially best possible search strategy for almost all random graph orders and (ii) one may compute a constant factor approximation for almost all partial orders. This is in pleasant constrast to the fact that determining an optimal strategy is NP-hard, as recently proved in [1]. Finally, as the reader will see, it will be quite surprisingly simple to prove our results.

1.1 Definitions and Notation

A partial order is a pair (U, ≺) where U is a set and ≺ a binary relation on U which is anti-symmetric, transitive and irreflexive. If x, y ∈ U then x ≺ y stands for (x, y) ∈≺. The elements u, v ∈ U are said to be comparable in (U, ≺) if u ≺ v or v ≺ u, being otherwise said to be incomparable; a chain in (U, ≺) is a set X ⊆ U of pairwise comparable elements; an antichain of (U, ≺) is a set X ⊆ U of pairwise incomparable elements; the height of (U, ≺) is the size of a maximum chain and the width is the size of a maximum antichain. An element u ∈ U is maximal in (U, ≺) if there is no x ∈ U such that u ≺ x.

An ideal of (U, ≺) is a set I ⊆ U such that u ≺ i ⇒ u ∈ I for all i ∈ I and a filter of (U, ≺) is a set F ⊆ U such that f ≺ u ⇒ u ∈ F for all f ∈ F; if X ∈ U, we denote by I(X) (resp. F (X)) the minimal ideal I (resp. filter F) of (U, ≺) such X ⊆ I (resp. X ⊆ F).

Thoughout the text, we denote a set of integers {z ∈ ℕ: x ≤ z ≤ y} by [x, y] and define [n] = [1, n] for any integer n ≥ 1. Also, ω will denote a function ω : ℕ → ℝ satisfying lim_{n→∞} ω(n) = ∞.

The problem of searching through a partially ordered set can be stated as follows. We are given a partially ordered set (U, ≺) and a finite set S ⊆ U with the partial order induced by ≺. Our goal is to determine whether a given u ∈ U is an element of S and we are allowed to pose queries about u to the elements of S.

A query about u ∈ U to s ∈ S has three possible outcomes, namely, hit, smaller and no, meaning u = s, u ≺ s and u ⊀ s, respectively. A search for u ∈ U through S is a sequence of queries allowing to decide whether u ∈ S or not. The goal is to devise a strategy for querying the elements of S in such a way that the longest search through S poses the smallest number of queries.

Such a strategy can be conveniently thought of as a binary decision tree whose internal nodes are labelled with elements of S, whose external nodes are labelled with pairs (s_{min}, s_{max}) ∈ (S ∪ {−∞}) × (S ∪ {+∞}) and whose edges are labelled with ≺ and ⊀.

A path in the decision tree from its root to an internal node labelled s represents a successful search whose outcome is u = s, while a path from the root to an external node labelled (s_{min}, s_{max}) represents an unsuccessful search whose outcome is u ∉ S with the additional information that s_{min} ≺ u ≺ s_{max}. We define the height of a binary decision tree as the length of a longest path from its root to an external node.

We can then restate our problem as follows: given a partial order (S, ≺), compute a binary decision tree of minimum height for S.

We will denote by n the number of elements of S and will assume that the partial order (S, ≺) is given as a directed acyclic graph G_{≺} of m edges and n vertices , representing its Hasse diagram. Then, given an algorithm A for computing such a decision tree, we focus on the height H_{A}(n, m) of the tree that we construct and on the number of steps T_{A}(n, m) required by A to construct such tree.

We note that when ≺ is a total order on S, the optimum decision tree for S is the usual binary search tree for S. In this case we have m = n − 1, H(n, m) = ⌈lg n⌉+1 and T (n, m) = O(n), these being the best possible values for H and T.

On the other extreme, if the whole of S is an antichain, then we have m = 0, H(n, m) = n and T (n, m) = O(n).

1.2 Organization

This extended abstract is organized as follows. In Section 2 we mention some relevant results in the context of searching in partially ordered sets. In Section 3 we present a linear time algorithm for building a decision tree which has height almost surely bounded by lg n + O ((log n)^{1/2} log log n) under the random graph model for n-element partial orders.

In Section 4 we present a O(n^{2} log n) time algorithm for building a decision tree which has height almost surely bounded by O(log n) under the uniform model for n-element partial orders (assuming the search model with the ‘generous’ oracle).

In Section 5 we make some general ramarks and briefly discuss some connections among our results and a related problem proposed in [2].

2 Related Work

It is shown in [1] that the problem of searching through a partially ordered set is NP-hard, even when restricted to the case in which (S, ≺) has a maximum element. The more restricted case in which the given partial order has a maximum element and G_{≺} is a tree (the so called rooted tree variant) can be solved in polynomial time as shown in [3], where an algorithm for computing a minimum height decision tree is presented with T (n, m) = O(n^{4}(log n)^{3}). Their algorithm does not yield an easy way to estimate H(n, m), except in a few cases: for instance, when G_{≺} is a complete binary tree, the decision tree built by their algorithm has H(n, m) = lg n + lg^{∗} n + Θ(1).

The work in [1] presents a much simpler algorithm for the case in which G_{≺} is a rooted tree, which computes in time T (n, m) = O(n log n) a decision tree whose height is at most lg n greater than the height of the optimum decision tree. Since the optimum decision tree must have height at least lg n, their algorithm constitutes a 2-approximation algorithm for the problem.

The case in which (S, ≺) has a maximum element and the maximum degree of G_{≺} is d is also studied in [1], where it is shown that d log_{d} n is an upper bound for the height of an optimum decision tree, which improves to the best possible a previous bound from [4].

Lipman and Abrahams [5] present optimized exponential time algorithms for building decision trees for searching in general partially ordered sets. Nevertheless, they considered the minimization of the expected path length of the decision tree.

Linial and Saks consider in [2] a different although related problem, motivated by the following setting: suppose we are given an m × n real matrix M whose (say, distinct) entries are known to be increasing along the rows and along the columns and suppose we wish to decide whether a given real number x occurs in M. The goal is to devise a search strategy which minimizes the number of inspections of entries of M in the worst case.

If one looks at the matrix as the product of two chains of length m and n, the problem may be thought of as a problem of searching in a partially ordered set. However, the underlying assumption that the entries of M come from a totally ordered set actually turns it into a different problem, which we discuss in Section 5.

Linial and Saks (see [2] and [6]) have determined bounds for arbitrary orders ≺ and have studied in detail the case in which ≺ is a product of chains and the case in which G_{≺} is a rooted tree.

3 The Random Graph Model

Let (S, ≺) be a partial order and denote by max_{≺} X the set of maximal elements of X ⊆ S. Consider the following recursive decomposition of S into antichains: let L_{1} = max_{≺} S, and let L_{i} = max_{≺} (S − ⋃_{j=1}^{i−1} L_{j}) for i > 1. Let h be the height of (S, ≺) and let w = max_{1≤i≤h} |L_{i}|. We will call each set L_{i} the layer i of S.

A possible adaptation of the usual binary search strategy to the case of partial orders may be described as follows.

Algorithm B

1. Let m be the index of the layer which divides S in two parts, each of them with less than |S|/2 elements, that is, m is such that | ⋃_{i=1}^{m−1} L_{i}| < |S|/2 and | ⋃_{i=m+1}^{h} L_{i}| < |S|/2. Denote these halves of S by L_{↓} and L_{↑}, respectively.

2. Perform a query about u to each s ∈ L_{m}:

(a) if the outcome of one of these queries is hit, the search is over;

(b) if the outcome of one of these queries is smaller, restart the search, restricted to L_{↓};

(c) if the outcome to all these queries is no, restart the search, restricted to L_{↑}.

Let us call the above strategy an extended binary search, and denote the algorithm which computes the respective decision tree by B(S, ≺). We clearly have H_{B}(n, m) ≤ w ⌈lg h⌉; moreover, as the layering of S can be produced in time O(m) and the building of the tree takes one step per element of S, we have T_{B}(n, m) = O(n + m).

We now turn our attention to another strategy: suppose we have {d_{i}}_{i=1}^{k} ⊆ S such that {d_{1}} = I(d_{1}) ⊂ I(d_{2}) ⊂ I(d_{3}) ⊂ … ⊂ I(d_{k}) ⊆ S. In this case we define the segments S_{i} (0 ≤ i ≤ k) of (S, ≺) by

S_{i} = \begin{cases}\{d_{1}\} & if i = 0, \\ I(d_{i+1}) − I(d_{i}) & if 0 < i < k, \\ S − I(d_{k}) & if i = k. \end{cases}

We can then formulate the following algorithm which takes advantage of the above structure.

Algorithm A

1. Perform a (usual) binary search of u through {d_{i}}_{i=1}^{k}; if u is found stop, otherwise let i be the minimum index such that u ≺ d_{i} (or k, if there is no such index).

2. Perform an extended binary search through the segment S_{i}.

We have

H_{A}(n, m) ≤ ⌈lg k⌉ + max_{1≤i≤k} H_{B}(|S_{i}|, m) ≤ lg n + w lg ( max_{1≤i≤k} |S_{i}|) ,

and this tree can be built in T_{B}(n, m) = O(n + m) steps.

In the following sections we introduce the random graph order model for partial orders and show that, in this model, we almost surely have

H_{A}(n, m) = lg n + O(\sqrt{log n} log log n).

3.1 The Random Graph Model

The random graph order probability space, denoted P_{n,p}, is the probability space of all partial orders ([n], ≺) obtained by independently choosing each pair of {(i, j) ∈ [n]^{2} : i < j} with probability p and taking the transitive closure of the resulting relation. We denote a generic partial order ([n], ≺) in P_{n,p} by P_{n,p}.

We say that d ∈ [n] is k-dominating if [d − k, d − 1] ⊆ I(d) and call d a dominating element of [n] if d is (d − 1)-dominating (that is, if x ≺ d for all 1 ≤ x < d). The conditional probability that d should be k-dominating, given that d is (k − 1)-dominating, is 1 − (1 − p)^{k}, which leads us to

ℙ(d is k-dominating) = (1 − (1 − p)^{k})ℙ(d is (k − 1)-dominating).

By induction on k, we have

ℙ(d is k-dominating) = η(k, p),

where η(k, p) = ∏_{i=1}^{k}(1 − (1 − p)^{i}). We note that η is a strictly decreasing function of k and define η(p) = lim_{k→∞} η(k, p); then, for all k ≥ 1, we have η(p) < η(k, p) ≤ p.

Lemma 1. The probability that d ∈ [n] is dominating is η(d − 1, p).

As a consequence, we note that the expected number of dominating elements in P_{n,p} is greater than nη(n, p). By setting {d_{i}}_{i=1}^{k} to be the dominating elements in P_{n,p}, we meet the necessary conditions for applying algorithm A on P_{n,p}.

In what follows, we will show that the decision tree built by A(P_{n,p}) almost surely has “small height”, by showing that both the size of each segment S_{i} and the size of each layer L_{j} are suitably small.

To show that the size of each segment is not too large we show that we have no large intervals of [n] free of dominating elements in P_{n,p}; to show that the size of each layer is not too large, we use that we cannot have large antichains in P_{n,p}.

On the Size of the Segments. Let us consider the case in which d is not dominating. In this case, there must be a minimum b such that d is (b−1)-dominating but it is not b-dominating. If we call such b a barrier for (the domination of) d, then we have, for each 0 < b < d − 1,

ℙ(b is a barrier for d) = ℙ(d − b ⊀ d and d is (b − 1)-dominating)
= ℙ(d − b ⊀ d | d is (b − 1)-dominating)

× ℙ(d is (b − 1)-dominating)

= (1 − p)^{b}η(b − 1, p).

Thus, for any 0 < s < d−1, we have that the probability that d is not dominating but d is s-dominating is

ℙ ( ⋁_{b=s+1}^{d−2} {b is a barrier for d}) = ∑_{b=s+1}^{d−2} ℙ(b is a barrier for d)

= ∑_{j=0}^{d−s−3} ℙ(j + s + 1 is a barrier for d) = ∑_{j=0}^{d−s−3}(1 − p)^{j+s+1}η(j + s, p)

≤ η(s, p)(1 − p)^{s+1} ∑_{j≥0}(1 − p)^{j} = \frac{η(s, p)}{p}(1 − p)^{s+1} ≤ (1 − p)^{s+1}.

Now, if M ⊆ [n] and d = min{|m − m′|: m, m′ ∈ M}, then the events “m is d-dominating” are mutually independent for all m ∈ M. For convenience, let D and D_{d} denote the set of dominating and d-dominating elements in P_{n,p}. We have

\begin{aligned}ℙ(D ∩ M = ∅) & = ℙ(D ∩ M = ∅ | D_{d} ∩ M = ∅)ℙ(D_{d} ∩ M = ∅) \\ & + ℙ(D ∩ M = ∅ and D_{d} ∩ M ≠ ∅) \\ & ≤ ℙ ( ⋀_{m∈M} \{m ∉ D_{d}\}) + ℙ ( ⋁_{m∈M} \{m ∉ D and m ∈ D_{d}\}) \\ & ≤ (1 − η(d, p))^{|M|} + ∑_{m∈M}(1 − p)^{d+1} \\ & = (1 − η(d, p))^{|M|} + |M|(1 − p)^{d+1}. \end{aligned} (1)

Let us put

β(p) = lg \frac{1}{1 − p},  γ(p) = lg \frac{1}{1 − η(p)},  α(p) = \frac{2}{β(p)γ(p)}.

Theorem 2. If g ≥ ⌈α(p)(lg nω(n))^{2}⌉ and x < n − g, the probability that the set [x, x + g] has no dominating element is at most 1/nω(n).

Proof. If

d ≥ \frac{γ(p)m + lg m}{β(p)} − 1,  (2)

then m(1 − p)^{d+1} ≤ (1 − η(p))^{m}, so that if |M| = m in (1) then the probability that there is no dominating element in M is 2(1 − η(p))^{m}. If

m ≥ \frac{lg 2nω(n)}{γ(p)},  (3)

then the probability that there is no dominating elements in M is ≤ (nω(n))^{−1}.

We can then set M = {x + id}_{i=0}^{m−1}, with d and m satisfying (2) and (3) so that we have M ⊆ [x, x + g] with

g ≥ dm ≥ \frac{(lg 2nω(n))^{2} + (lg 2nω(n)) (lg lg 2nω(n) − (\frac{1}{β(p)} + lg γ(p)))}{β(p)γ(p)}

≥ \frac{2(lg nω(n))^{2}}{β(p)γ(p)} = α(p)(lg nω(n))^{2}.

⊓ ⊔

Corollary 3. The probability that P_{n,p} has a segment of size ≥ α(p)(lg nω(n))^{2} is at most 1/ω(n).

Proof. Let {S_{j}}_{j=1}^{k} be the segments of P_{n,p}. Then

\begin{matrix}ℙ ( ⋁_{j=1}^{k} \{|S_{j}| > α(p)(lg nω(n))^{2}\}) ≤ ∑_{j=1}^{k} ℙ(|S_{j}| > α(p)(lg nω(n))^{2}) \\ ≤ ∑_{j=1}^{k} \frac{1}{nω(n)} = \frac{k}{nω(n)} ≤ \frac{1}{ω(n)}. \end{matrix}

⊓ ⊔

On the Size of the Layers. Consider a layer L_{i}. Since L_{i} is an antichain in P_{n,p}, we can make direct use of the following result from Barak and Erdős [7].

Theorem 4 (Barak and Erdős [7]). The probability that P_{n,p} has an antichain of size larger than

K_{n} = \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}} + \frac{1}{2}  (4)

tends to zero as n → ∞.

The Decision Tree is not Too Tall. We are now in position to prove the main result of this section.

Theorem 5. The decision tree built by algorithm A(P_{n,p}) has height almost surely bounded by lg n + O(\sqrt{log n} log log n).

Proof. Let H be the random variable in P_{n,p} whose value is the height of the decision tree built by the algorithm on the input P_{n,p}. As has been noted, we have H ≤ lg n + w lg max_{1≤i≤h} |S_{i}|, where w is the size of the greatest layer of P_{n,p}, the S_{i} are its segments, and h is its height.

Corollary 3 tells us that

ℙ ( max_{1≤i≤h} |S_{i}| > α(p)(lg nω(n))^{2}) < \frac{1}{ω(n)},

while Theorem 4 gives

ℙ (w > \frac{1}{2} + \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}}) < \frac{1}{ω′(n)},

for some function ω′ : ℕ → ℝ satisfying lim_{n→∞} ω′(n) = ∞. Therefore

ℙ ( max_{1≤i≤h} |S_{i}| ≤ α(p)(lg nω(n))^{2} and w ≤ \frac{1}{2} + \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}})

= 1 − ℙ ( max_{1≤i≤h} |S_{i}| > α(p)(lg nω(n))^{2} or w > \frac{1}{2} + \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}})

< 1 − (\frac{1}{ω(n)} + \frac{1}{ω′(n)}) = 1 − o(1).

We conclude that

lim_{n→∞} ℙ (H ≤ lg n + (\frac{1}{2} + \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}}) lg(α(p)(lg n)^{2})) = 1.

⊓ ⊔

4 The Uniform Model

In this section we study the problem of searching in a typical partial order according to the uniform model. We start by stating some definitions and a key auxiliary result.

Denote by P(n) the set of all partial orders on [n]. Taking P(n) with the uniform distribution, that is, making each partial order equally likely, we have the uniform model for random partial orders; a random element in this model will be denoted by U_{n}.

It is known that almost all U_{n} have a strong structural property, which we now describe. Let {X_{1}, X_{2}, X_{3}} be a partition of [n], and let A(X_{1}, X_{2}, X_{3}) be the set of partial orders ([n], ≺) satisfying the following conditions:

– whenever x ≺ y, for x ∈ X_{i} and y ∈ X_{j}, we have i < j,

– whenever x ∈ X_{1} and y ∈ X_{3} we have x ≺ y.

The partial orders in A(X_{1}, X_{2}, X_{3}) are said to be 3-layered.

Answering the question “what does a ‘typical’ partial order on [n] look like?”, in [8] Kleitman and Rothschild proved that, rather surprisingly, almost all partially ordered sets are 3-layered.

Theorem 6 (Kleitman and Rothschild [8]). Suppose ω(n) → ∞ as n → ∞. Almost every partial order on [n] lies in A(X_{1}, X_{2}, X_{3}) for some partition \{X_{1}, X_{2}, X_{3}\} of [n] with ||X_{2}| − n/2| < ω(n) and ||X_{1}| − n/4| < ω(n)\sqrt{n}.

Theorem 6 makes the problem of searching in typical partial orders as posed in Section 1 rather uninteresting, since our search model makes it unavoidable to query each of the maximal elements of the given order. Theorem 6 tells us that almost all orders have (1/4 + o(1))n such elements.

To make the problem more interesting, we now consider a variation of our search model where a query to s about u has four possible outcomes: smaller, greater, hit and no meaning, respectively, u ≺ s, s ≺ u, s = u and s is not comparable to u; a strategy, accordingly, is redefined to be a decision tree as described previously, with the difference that each internal node has three children. In this section we shall prove that it is almost always possible, under the uniform model, to construct a ternary decision tree of height O(log n) in time O(n^{2} log n).

Let us first make the following definition: given two disjoint sets X_{1}, X_{2}, the set of 2-layered orders A(X_{1}, X_{2}) is the set of all partial orders (X_{1} ∪ X_{2}, ≺) such that ≺ ⊆ X_{1} × X_{2}.

Given a partition {X_{1}, X_{2}, X_{3}} of [n], there is a natural correspondence between A(X_{1}, X_{2}, X_{3}) and A(X_{1}, X_{2})×A(X_{2}, X_{3}), so that we can devise a search strategy for a 3-layered order as a ‘composition’ of search strategies for 2-layered orders, by applying the latter on the suborders induced by X_{1} ∪X_{2} and X_{2} ∪X_{3}.

Our strategy for searching for u ∈ U in P ∈ A(X_{1}, X_{2}) is simple: we start by making the assumption u ∈ X_{1}, which we then verify by means of a series of queries to elements of X_{2} in such a way that, at the end, we either have found u in X_{1} or know that u ∉ X_{1}. In the latter case, we restart the algorithm with the rôles of X_{1} and X_{2} exchanged, so that, after this is done, we either have found u in X_{1} ∪ X_{2} or can conclude that u ∉ X_{1} ∪ X_{2}. The algorithm to search for u ∈ U in the layer X_{1}, say, starts by setting S = X_{1} and proceeds in two phases.

Algorithm C

querying phase: at each step, 1. choose x ∈ X_{2} such that ||S ∩ I(x)| − |S − I(x)|| is minimal.

2. query x about u:

(a) if the answer is hit, the search is over;

(b) if the answer is smaller, replace S with |S ∩ I(x)| and restart;

(c) if the answer is no, replace S with |S − I(x)| and restart. This procedure is repeated until we reach the point where S ∩ I(x) = ∅ or S − I(x) = ∅ for all x ∈ X_{2}, at which point we go to the next phase.

sweeping phase: for each s ∈ S:

1. query s about u: if the answer is hit, the search is over, otherwise, proceed.

If the search is not over after this, we can conclude that u ∉ X_{1}.

Let us call s_{i}(X_{1}, X_{2}) the size of the set S at the beginning of the ith step of the querying phase, s(X_{1}, X_{2}) the size of the set S at the beginning of the sweeping phase and q(X_{1}, X_{2}) the number of queries made at the querying phase. It is clear that the height of the decision tree corresponding to the above procedure is bounded by q(X_{1}, X_{2}) + s(X_{1}, X_{2}); moreover, we note that the choice of x at step i of the querying phase can be accomplished in s_{i}(X_{1}, X_{2})|X_{2}| steps.

From this and the above discussion, we can conclude that it is possible to construct a decision tree of height

H_{C} ≤ ∑_{(i,j)∈J} (q(X_{i}, X_{j}) + s(X_{i}, X_{j})),  (5)

and this can be done in time

T_{C} ≤ ∑_{(i,j)∈J} (s(X_{i}, X_{j}) + |X_{j}| ∑_{k=1}^{q(X_{i},X_{j})} s_{k}(X_{i}, X_{j})) ,  (6)

where J = {(1, 2), (3, 2), (2, 1)}.

At this point we define the binomial probability model A_{1/2}(X_{1}, X_{2}) for 2layered orders, given by independently choosing each (x_{1}, x_{2}) ∈ X_{1} × X_{2} with probability 1/2. We shall show that, in this model, we almost always have

1. s_{i}(X_{1}, X_{2}) ≤ (2/3)^{i}|X_{1}|,

2. q(X_{1}, X_{2}) ≤ log_{3/2} |X_{1}|,

3. s(X_{1}, X_{2}) < 40,

which, along with (5), (6) and the sizes of X_{1}, X_{2} and X_{3} in Theorem 6 show that

H_{C} ≤ 3 log_{3/2} n + 120  and  T_{C} ≤ \frac{3}{2}n|X_{2}| + 120.

There is a natural correspondence between the product space A_{1/2}(X_{1}, X_{2})× A_{1/2}(X_{2}, X_{3}) and the uniform probability space A(X_{1}, X_{2}, X_{3}). On the other hand, Theorem 6 and a standard argument give that if an event is almost certain in the space A(X_{1}, X_{2}, X_{3}) = A_{1/2}(X_{1}, X_{2}) × A_{1/2}(X_{2}, X_{3}) for any fixed partition (X_{1}, X_{2}, X_{3}) as in Theorem 6, then this event must also be an almost certain event in U_{n} (details are given in the final version [9] of this extended abstract).

Therefore, in the remaining of this section, we concentrate in proving the relevant results for A_{1/2}(X_{1}, X_{2}) × A_{1/2}(X_{2}, X_{3}), where the X_{i} are as in the Kleitman–Rothschild theorem.

In what follows, we assume S ⊆ X_{1}, x ∈ X_{2} and let d_{S}(x) = |I(x)∩S| be the number of elements in S smaller than x. The reader may notice that it is easy to prove analogous versions of the proposition and corollary below with X_{1} and X_{2} interchanged. Moreover, both, proposition and corollary, obviously remain true if we consider X_{3} instead of X_{1}.

Proposition 7. Almost surely, for a fixed S ⊆ X_{1} with |S| ≥ 40, the probability that there is no vertex x ∈ X_{2} with |S|/3 ≤ d_{S}(x) ≤ 2|S|/3 is

≤ (2 exp {−|S|/40} )^{|X_{2}|}.

Proof. Fix S ⊆ X_{1} and x ∈ X_{2}. Then, by Chernoff’s inequality, we have

ℙ (|d_{S}(x) − μ| > |S|/6) < 2 exp {−μ/20} ,

where μ = |S|/2 is the expected value of d_{S}(x). Thus, we have

ℙ( ∄x ∈ X_{2} : |S|/3 ≤ d_{S}(x) ≤ 2|S|/3) ≤ (2 exp {−|S|/40} )^{|X_{2}|},

as required. ⊓ ⊔

Corollary 8. For X_{1}, X_{2} as above, and q, s_{i}, s be as defined in the preceding discussion, the following almost surely holds:

1. s(X_{1}, X_{2}) ≤ 40,

2. s_{i}(X_{1}, X_{2}) ≤ (2/3)^{i}|X_{1}|, and so,

3. q(X_{1}, X_{2}) ≤ log_{3/2} |X_{1}|.

Proof. To prove (1) we observe that the probability of s(S, X_{2}) > 40, for some S ⊂ X_{1} with |S| > 40, is given by

ℙ (∃S ⊆ X_{1} ∀x ∈ X_{2} we have |d_{S}(x) − |S|/2| > |S|/6)

≤ ∑_{S⊆X_{1}, |S|≥40} ℙ (∀x ∈ X_{2} we have |d_{S}(x) − |S|/2| > |S|/6)

≤ ∑_{s=40}^{|X_{1}|} \binom{|X_{1}|}{s} exp \{− (s/40 − ln 2) |X_{2}|\}

≤ ∑_{s=40}^{|X_{1}|} exp {− (s/40 − ln 2) |X_{2}| + s ln |X_{1}|} = o(1).

To prove (2) and (3), it suffices to notice the following. The probability that, at some point in step 1 of the querying phase, we cannot choose x ∈ X_{2} such that |S|/3 ≤ |S ∩ I(x)| ≤ 2|S|/3 is at most

(log_{3/2} |X_{1}|)ℙ (∀x: |d_{S}(x) − |S|/2| > |S|/6) ≤ n (\frac{2}{e})^{|X_{2}|} = o(1).

Thus in both cases (b) and (c) of step 2 of algorithm C, we have reduced the search space by a factor ≤ 2/3. Therefore we have q(X_{1}, X_{2}) ≤ log_{3/2} |X_{1}|. ⊓ ⊔

Theorem 9. Almost every U_{n} admits a ternary search tree of height O(log n) which can be constructed in time O(n^{2}).

5 Concluding Remarks

We observe that one may also study the uniform model conditioning on having sparser partial orders. To carry out this investigation, the recent results in [10] and [11] are crucial. We shall come back to this in [9].

The arguments in the proofs of Corollary 3 and preceding lemmas and theorems are adapted rewritings of arguments found in [12] (Lemma 2.3 and Theorems 2.10 and 2.11). The results in that paper, on the structure of random graph orders, were what first suggested to the authors the idea of the algorithm.

In the present work we consider only the case in which p does not depend on n. It should be noted, however, that the results in [12] imply that ours remain valid even in the case in which p = p(n) is a decreasing function of n, as long as p lg n → ∞.

It is worth noting that Theorem 4 is part of a deeper investigation on the width of random graph orders found in [7], where a much stronger result is proven, namely, that the width of a random graph order is an almost determined random variable whose value, rather surprisingly, is almost surely ⌊K_{n}⌋ or ⌈K_{n}⌉, where K_{n} is given in (4).

As mentioned in Section 2, Linial and Saks [2] consider a different although related problem where the set U is assumed to be totally ordered, the given relation (S, ≺) is a partial order compatible with this total order and where each query about u ∈ U to s ∈ S is made with respect to the total order induced on S and not with respect to the given relation ≺ as is our case.

To see why this turns out to define a different problem, consider what information is gained in a search through S for u ∈ U when we query s ∈ S about u and the outcome is smaller: in our problem, such an outcome is enough to confine the remaining of the search to S ∩ I(s); in their problem, however, this is not the case: as the query is made with respect to the underlying total order in S, the outcome smaller leaves all elements in S − F (s) as valid candidates.

While not presenting explicitly an algorithm to compute an optimal decision tree for the problem, it is a consequence of the results in [2] and [6] that the height H of an optimal decision tree for their problem satisfies

lg ι(S, ≺) ≤ H ≤ k lg ι(S, ≺),  (7)

where ι(S, ≺) is the number of ideals in (S, ≺) and k = (2−lg(1+lg 5))^{−1} ≈ 3.73.

We note that this fact alone can lead us to similar results to those given in Section 3 when we consider their problem in the random graph order model. Let us briefly discuss this. Redefine an element of S to be dominating if it is comparable to every other element in (S, ≺), and a segment to be an interval free of dominating elements.

A possible search strategy, then, would be isolating one segment by means of a binary search restricted to the dominant elements of the order and then searching through this segment.

An ideal in a partial order is uniquely determined by the antichain of its maximal elements. Therefore, the number of ideals in a segment R is bounded by the number of antichains it contains, and hence if w is the width of the order, then

ι(R, ≺) ≤ ∑_{i=1}^{w} \binom{|R|}{i} ≤ |R|^{w}.

Together with the bounds in (7) and Theorem 4, this allows us to conclude that there is a decision tree for R of height at most

H ≤ k lg ι(R, ≺) ≤ kw lg |R|.

Therefore we can conclude that, for any partial order, there is a decision tree of height H ≤ lg n + w lg s, where s is the size of the largest segment in the order.

Now, the argument leading to Theorem 2 proves a result for dominating elements as defined now (with another value for α(p), of course, say α′(p)), which, together with Theorem 4 gives us

lim_{n→∞} ℙ (H ≤ lg n + k (\frac{1}{2} + \sqrt{\frac{2 lg n}{β(p)} + \frac{1}{4}}) lg(α′(p)(lg n)^{2})) = 1.

References

1. Laber, E.S., Nogueira, L.T.: Binary searching in posets. Submitted for publication (2001)

2. Linial, N., Saks, M.: Searching ordered structures. Journal of Algorithms 6 (1985) 86–103

3. Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM Journal on Computing 28 (1999) 2090–2102

4. Ben-Asher, Y., Farchi, E.: The cost of searching in general trees versus complete binary trees. Technical Report 31905, Technical Report Research Center (1997)

5. Lipman, M.J., Abrahams, J.: Minimum average cost testing for partially order. IEEE Transactions on Information Theory 41 (1995) 287–291

6. Linial, N., Saks, M.: Every poset has a central element. Journal of Combinatorial Theory, Series A 40 (1985) 195–210

7. Barak, A.B., Erdős, P.: On the maximal number of strongly independent vertices in a random acyclic directed graph. SIAM Journal on Algebraic and Discrete Methods 5 (1984) 508–514

8. Kleitman, D.J., Rothschild, B.L.: Asymptotic enumeration of partial orders on a finite set. Trans. Amer. Math. Soc. 205 (1975) 205–220

9. Carmo, R., Donadelli, J., Laber, E., Kohayakawa, Y.: Searching in random partially ordered sets. In preparation (2002)

10. Prömel, H.J., Steger, A., Taraz, A.: Counting partial orders with a fixed number of comparable pairs. Combin. Probab. Comput. 10 (2001) 159–177

11. Prömel, H.J., Steger, A., Taraz, A.: Phase transitions in the evolution of partial orders. J. Combin. Theory Ser. A 94 (2001) 230–275

12. Bollobás, B., Brightwell, G.: The structure of random graph orders. SIAM Journal on Discrete Mathematics 10 (1997) 318–335