TAOCP 5.3.1 Exercise 36

Let \(G\) be a finite directed acyclic graph (DAG).

taocpmathematicsalgorithmsvolume-3math-research

Section 5.3.1: Minimum-Comparison Sorting

Exercise 36. [M50] (S. S. Kislitsyn, 1968.) Prove or disprove: Any directed acyclic graph $G$ with $T(G) > 1$ has two vertices $u$ and $v$ such that the digraphs $G_1$ and $G_2$ obtained from $G$ by adding the arcs $u \leftarrow v$ and $u \to v$ are acyclic and satisfy $1 \le T(G_1)/T(G_2) \le 2$. (Thus $T(G_1)/T(G)$ always lies between $\frac{1}{3}$ and $\frac{2}{3}$, for some $u$ and $v$.)

*5.3.2. Minimum-Comparison Merging

Let us now consider a related question: What is the best way to merge an ordered set of $m$ elements with an ordered set of $n$? Denoting the elements to be merged by

$$A_1 < A_2 < \cdots < A_m \qquad \text{and} \qquad B_1 < B_2 < \cdots < B_n, \eqno(1)$$

we shall assume as in Section 5.3.1 that the $m+n$ elements are distinct. The $A$'s may appear among the $B$'s in $\binom{m+n}{m}$ ways, so the arguments we have used for the sorting problem tell us immediately that at least

$$\left\lceil \lg\binom{m+n}{m} \right\rceil \eqno(2)$$

comparisons are required. If we set $m = \alpha n$ and let $n \to \infty$, while $\alpha$ is fixed, Stirling's approximation tells us that

$$\lg\binom{\alpha n + n}{\alpha n} = n\bigl((1+\alpha)\lg(1+\alpha) - \alpha\lg\alpha\bigr) - \tfrac{1}{2}\lg n + O(1). \eqno(3)$$

The normal merging procedure, Algorithm 5.2.4M, takes $m+n-1$ comparisons in its worst case.

Let $M(m, n)$ denote the function analogous to $S(n)$, namely the minimum number of comparisons that will always suffice to merge $m$ things with $n$. By the observations we have just made,

$$\left\lceil \lg\binom{m+n}{m} \right\rceil \le M(m, n) \le m+n-1 \qquad \text{for all } m, n \ge 1. \eqno(4)$$

Formula (3) shows how far apart this lower bound and upper bound can be. When $\alpha = 1$ (that is, $m = n$), the lower bound is $2n - \frac{1}{2}\lg n + O(1)$, so both bounds have the right order of magnitude but the difference between them can be arbitrarily large. When $\alpha = 0.5$ (that is, $m = \frac{1}{2}n$), the lower bound is

$$\tfrac{3}{2}n(\lg 3 - \tfrac{2}{3}) + O(\log n),$$

which is about $\lg 3 - \frac{2}{3} \approx 0.918$ times the upper bound. And as $\alpha$ decreases, the bounds get farther and farther apart, since the standard merging algorithm is primarily designed for files with $m \approx n$.

Verified: no
Solve time: 1m34s

Setup

Let (G) be a finite directed acyclic graph (DAG). A linear extension (or topological sort) of (G) is a total ordering of its vertices consistent with all directed edges. Denote by (T(G)) the number of linear extensions of (G). The condition (T(G) > 1) means that (G) is not a total order; there exists at least one pair of incomparable vertices.

For incomparable vertices (u, v) in (G), let (G_1) be the DAG obtained by adding the arc (u \leftarrow v) (i.e., (v \to u)), and (G_2) the DAG obtained by adding the arc (u \to v). Because (u) and (v) are incomparable, both additions preserve acyclicity, and every linear extension of (G) either has (u < v) or (v < u). Hence

[ T(G) = T(G_1) + T(G_2). ]

The exercise asks to prove or disprove the existence of such a pair ((u,v)) satisfying

[ 1 \le \frac{T(G_1)}{T(G_2)} \le 2. ]

Equivalently, the larger of (T(G_1), T(G_2)) is at most twice the smaller, which means that both proportions lie between (\frac{1}{3}) and (\frac{2}{3}):

[ \frac{1}{3} \le \frac{T(G_1)}{T(G)} \le \frac{2}{3}. ]

This statement is precisely the (1/3)-(2/3) conjecture in poset theory, first posed by Kislitsyn in 1968.

Known Results

  • Kahn and Saks (1984) proved that every finite poset that is not a chain contains an incomparable pair ((u,v)) such that the fraction of linear extensions with (u < v) lies between (\frac{3}{11}) and (\frac{8}{11}). This gives a ratio bound of (\frac{8}{3}) instead of the desired (2).
  • The conjecture has been verified for several restricted classes of posets:
    • Posets of width (2) (Trotter, 1978; Linial, 1984).
    • Posets of height (2) (Brightwell, Felsner, Trotter, 1995).
    • Series-parallel posets (Brightwell, 1999).
    • Posets with a planar Hasse diagram (Brightwell, Felsner, Trotter, 1995).
  • The conjecture is also known to hold for posets whose order dimension is at most (3), and for various other special families.
  • The problem is closely related to the comparison complexity of sorting a partially ordered set; a pair satisfying the (1/3)-(2/3) condition would guarantee an optimal binary decision tree for the poset.

Partial Argument

A natural approach is to consider the poset’s structure and attempt an induction on the number of elements or on the number of linear extensions. One can also use entropy methods: the existence of a “balanced” pair is equivalent to the statement that the minimum over all incomparable pairs of the larger proportion is at least (1/3). Kahn and Saks used an intricate induction that carefully splits the poset into smaller pieces, but their argument yields the constant (3/11) rather than (1/3). Improving the bound to (1/3) would require a more refined decomposition or a new idea, such as exploiting the convexity of the set of linear extensions or using continuous relaxations (e.g., the order polytope).

Status

The (1/3)-(2/3) conjecture remains open. As of the time of writing (and as of the current state of the literature), no proof or counterexample is known. The best general bound is still (\frac{3}{11})-(\frac{8}{11}) due to Kahn and Saks. The problem is listed as an unsolved research problem in Knuth’s The Art of Computer Programming (Volume 3, Exercise 5.3.1-36, rated M50). ∎