Given a finite poset $\mathcal{P}$, we consider pairs of linear extensions of $\mathcal{P}$ with maximal distance, where the distance between two linear extensions $L_1, L_2$ is the number of pairs of elements of $\mathcal{P}$ appearing in different orders in $L_1$ and $L_2$. A diametral pair maximizes the distance among all pairs of linear extensions of $\mathcal{P}$. Felsner and Reuter defined the linear extension diameter of $\mathcal{P}$ as the distance between a diametral pair of linear extensions. We show that computing the linear extension diameter is NP-complete in general but can be solved in polynomial time for posets of width 3. Felsner and Reuter conjectured that, in every diametral pair, at least one of the linear extensions reverses a critical pair. We construct a counterexample to this conjecture. On the other hand, we show that a slightly stronger property holds for many classes of posets: we call a poset diametrally reversing if, in every diametral pair, both linear extensions reverse a critical pair. Among other results we show that interval orders and 3-layer posets are diametrally reversing. From the latter it follows that almost all posets are diametrally reversing.

Körner and Malvenuto asked whether one can find $\binom{n}{\lfloor n/2\rfloor}$ linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions.

Let $f:{\cal L}\to\mathbb{R}$ be a submodular function on a modular lattice ${\cal L}$; we show that there is a maximal chain ${\cal C}$ in ${\cal L}$ on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of ${\cal L}$, in a certain well-behaved partial order on sequences of reals. One consequence is that the maximum value of f on ${\cal C}$ is minimized over all such paths—i.e., if one can percolate from 0 to 1 on lattice points X with $f(X)\le b$, then one can do so along a maximal chain. The partial order on real sequences is defined by putting $\langle a(0),a(1),\dots,a(m)\rangle\preceq\langle b(0),\dots,b(n)\rangle$ if there is a way to “schedule” the sequences starting at $(a(0),b(0))$ and ending at $(a(m),b(n))$ so that always $a(i)\le b(j)$. Putting ${\bf a}\equiv{\bf b}$ if ${\bf a}\preceq{\bf b}\preceq{\bf a}$, each equivalence class has a unique shortest sequence which we call a worm. We use the properties of worms to give an efficient method to schedule many real sequences in parallel. The results in the paper are applied in a number of other settings, including obstacle navigation, graph search, coordinate percolation, and finding a lost child in a field.

Abstract Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524–539], we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value T from a source s to a destination t . We also impose upper bounds on the amount of capacity we may reserve on the arcs: This alters the nature of the problem. In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum‐cost reservation that is itself an acyclic ( s , t ) flow: We show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc‐disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. © 2003 Wiley Periodicals, Inc.

We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be "resilient" against one or more arc failures. For a given pair (s,t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an (s,t) flow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to find a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network flow problems, the integral version is NP-hard: we do, however, give a polynomial time $\frac{15}{14}$-approximation algorithm in the case k=1 and show that this bound is best possible unless P = NP.

The random graph order $P_{n,p}$ is defined by taking a random graph $G_{n,p}$ on vertex set $[n]$, treating an edge $ij$ with $i\prec j$ in $[n]$ as a relation $i < j$, and taking the transitive closure. A {\it post} in a partial order is an element comparable with all others. We investigate the occurrence of posts in random graph orders, showing in particular that $P_{n,p}$ almost surely has posts if $np^{-1}e^{-\pi^2/3p}\to \infty$, but almost surely does not if this quantity tends to 0. If there are many posts, the partial order decomposes as a linear sum of smaller orders, and we use this decomposition to show that many parameters of a random graph order---for instance, the height, the logarithm of the number of linear extensions, and the number of incomparable pairs---behave as normal random variables. For instance, for the height $H_{n,p}$, we prove that, for p in an appropriate range, there are functions $\alpha_H(p) =e(1+o(1))p$ and $\beta_H(p)$ such that $(H_{n,p} - \alpha_H(p)n)/\sqrt n \beta_H(p) \tod N(0,1)$.

This is a sequel to a previous paper entitled The Order Dimension of Convex Polytopes, by the same authors [SIAM J. Discrete Math., 6 (1993), pp. 230--245]. In that paper, we considered the poset {{\bf P}\protect\boldmath$_M\!\!\!$} formed by taking the vertices, edges, and faces of a 3-connected planar map {\bf M}, ordered by inclusion, and showed that the order dimension of {{\bf P}\protect\boldmath$_M\!\!\!$} is always equal to 4. In this paper, we show that if {\bf M} is any planar map, then the order dimension of {{\bf P}\protect\boldmath$_M\!\!\!$} is still at most 4.

This paper shows that every 3-connected planar graph G can be represented as a collection of circles, one circle representing each vertex and each face, so that, for each edge of G, the four circles representing the two endpoints and the two neighboring faces meet at a point, and furthermore the vertex-circles cross the face-circles at right angles. This extends a result of W. Thurston [The Geometry and Topology of Three Manifolds, unpublished] and, independently, Andreev. From this we deduce two corollaries: (1) The partial order formed by taking the vertices, edges, and bounded faces of G, ordered by inclusion, is a circle order; (2) One can represent G and its dual simultaneously in the plane with straight-line edges so that the edges of G cross the dual edges at right angles. This answers a question first asked by W. Tutte [Proc. LMS, 13 (3) (1963), pp. 743–768].

With a convex polytope ${\text{M}}$ in $\mathbb{R}^3$, a partially ordered set ${\text{P}}_{\text{M}} $ is associated whose elements are the vertices, edges, and faces of ${\text{M}}$ ordered by inclusion. This paper shows that the order dimension of ${\text{P}}_{\text{M}} $ is exactly 4 for every convex polytope ${\text{M}}$. In fact, the subposet of ${\text{P}}_{\text{M}} $ determined by the vertices and faces is critical in the sense that deleting any element leaves a poset of dimension 3.

Some recent work [7, 14, 15] in computational learning theory has discussed learning in situations where the teacher is helpful, and can choose to present carefully chosen sequences of labelled examples to the learner. We say a function t in a set H of functions (a hypothesis space) defined on a set X is specified by S***X if the only function in H which agrees with t on S is t itself. The specification number σ(t) of t is the least cardinality of such an S. For a general hypothesis space, we show that the specification number of any hypotheis is at least equal to a parameter from [14] known as the testing dimension of H. We investigate in some detail the specification numbers of hypotheses in the set Hn of linearly separable boolean functions: We present general methods for finding upper bounds on σ(t) and we characterise those t which have largest σ(t). We obtain a general lower bound on the number of examples required and we show that for all nested hypotheses, this lower bound is attained. We prove that for any t ε Hn, there is exactly one set of examples of minimal cardinality (i.e., of cardinality σ(t)) which specifies t. We then discuss those t ε Hn which have limited dependence, in the sense that some of the variables are redundant (i.e., there are irrelevant attributes), giving tight upper and lower bounds on σ(t) for such hypotheses. In the final section of the paper, we address the complexity of computing specification numbers and related parameters.

LetX1,...,Xn be pairwise independent random variables of known (but not necessarily identical) distribution; we wish to select a subset of these whose sum will be as close as possible to some known target value T. Conditions described below force the selections to be made by a primitive distributed system (similar to one considered by Papadimitriou and Yannakakis [2] in PODC '91); here we are able to obtain a surprising amount of information about optimal solutions.The conditions are that each variable must be “programmed” in advance, joining the selected set according to its own value. Thus, for example, one variable might be programmed to join just if its value lies between a and b, while another is told to join regardless of its value. Our object is to find a strategy, that is, a collection of programs, which minimizes the mean square error in approximating T. Typical applications involve producing a steady flow of some commodity when supply is controlled at a multiplicity of random sources.It turns out that there is always an optimal strategy in which each Xi is programmed to join if its value is between 0 and ti, for appropriate choice of thresholds ti. When the variables are identically distributed, we examine conditions under which the ti's must be equal. The case of uniform distributions on [0,1], for which the above conditions are not satisfied, is analyzed in detail, showing the rather bizarre behavior of the ti's which may take place in general as the target value is gradually changed.Next, we analyze the problem in which the variables are permitted to contribute any part of themselves to the sum; here it turns out that in an optimal strategy each program will be of the form “contribute the minimum of Xi and ei” with all the ei's equal in the i.i.d. case.Finally, we show how the original target shooting problem can be generalized to a kind of load balancing, where variables are assigned to different buckets, each with its own target, and the penalty is a weighted sum of squared errors. The surprising result here is that when the weights are equal, an optimal solution assigns variables only according to their signs.

The 1/3–2/3 conjecture says that, in any finite poset that is not totally ordered, vertices x and y can be found such that the proportion of linear extensions of the poser in which x is above y lies between 1/3 and 2/3 inclusive. In this paper, the conjecture is established in the case where every element of the poser is incomparable with at most five others. The proof involves the use of a computer to eliminate a large number of cases.

We show that the problem of counting the number of linear extensions of a given partially ordered set is #P-complete.This settles a long-standing open question and contrssts with recent results giving randomized polynomial-time algorit hms for estimating the number of linear extensions.One consequence is that computing the volume of a rational polyhedron is strongly #P-hard.We also show that the closely related problems of determining the average height of an element c of a given poset, and of determining the probability that z lies below y in a random linear extension, are #P-complete.

Given a set of n elements in some unknown order, parallel comparison algorithms to select the tth highest with probability $1- o(1)$ as $n \to \infty $ are considered, where each order is assumed to be equally likely. Such an algorithm is given using four rounds and $cn$ comparisons per round, and it is shown that no such algorithm exists using three rounds and $cn$ comparisons per round.

Suppose that we have a set X of n objects in some unknown total order $ < $. For G a graph on X, we ask, for each edge $xy$, “Is $x < y$?” On processing the information thus gained we may be able to deduce more comparisons. The information we have is then in the form of a partial order $P(G; <)$. Let $t(G)$ denote the maximum, over all linear orders $ <$ on X, of the number of pairs not related in $P(G; <)$; and let $t(n,p)$ denote the minimum of $t(G)$ over all graphs G with n vertices and $\lfloor {{{pn^2 } / 2}} \rfloor $ edges. We find upper and lower bounds for $t(n,p)$ throughout the range of $p = p(n)$.