Events correlated with respect to every subposet of a fixed poset

Posets are said to be (positively) correlated with respect to a third posetR onX (we writeA _R B) ifP(AR) P(AR B). HereP(CR) is the probability that a randomly chosen linear extension ofR is also a linear extension ofC. We classify posetsR onX such that(x, y) _s (u, v) holds for all posetsS onX which are subposets ofR, wherex, y, u, v are distinct elements ofX. On the way to proving this result, we show when a correlation inequality due to Shepp holds strictly.     

Sphere orders

Ann-sphere order is a finite partially ordered set representable by containment ofn-spheres in Euclidean (n+1)-space. We present a sequence {P _i } of ordered sets such that eachP _i is ann-sphere order only forni; one consequence is that we are able to determine the dimension of a Euclidean space-time manifold from the finite suborders of its causality order.Research supported by ONR grant N00014 85-K-0769.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

Characterisation of pulp and paper mill sludge for beneficiation

Cellulose - In this study, three different pulp and paper mill sludge (PPMS) samples collected from different South African mills were chemically and physically characterised to investigate their...     

The number of k‐SAT functions

We study the number SAT(k; n) of Boolean functions of n variables that can be expressed by a k‐SAT formula. Equivalently, we study the number of subsets of the n‐cube 2ⁿ that can be represented as the union of (n ? k)‐subcubes. In The number of 2‐SAT functions (Isr J Math, 133 (2003), 45–60) the authors and Imre Leader studied SAT(k; n) for k ≤ n/2, with emphasis on the case k = 2. Here, we prove bounds on SAT(k; n) for k ≥ n/2; we see a variety of different types of behavior. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 227–247, 2003     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

Electrical and phase behaviour of the system AgI-PbI2

Mixtures of AgI and PbI₂ form a phase stable at temperatures above 125°C with a substantial solid solubility about the composition 67% AgI, this phase exhibits a high electrical conductivity (～0.1S m^-1). A proposal is made for the basic form of the AgI-PbI₂ equilibrium diagram below 200°C, and comparison made to the systems AgI-ZnI₂ and AgI-CdI₂.     

Average relational distance in linear extensions of posets

We consider a natural analogue of the graph linear arrangement problem for posets. Let P=(X,?) be a poset that is not an antichain, and let λ:X→[n] be an order-preserving bijection, that is, a linear extension of P. For any relation a?b of P, the distance between a and b in λ is λ(b)−λ(a). The average relational distance of λ, denoted , is the average of these distances over all relations in P. We show that we can find a linear extension of P that maximises in polynomial time. Furthermore, we show that this maximum is at least , and this bound is extremal.     

A Linear Bound On The Diameter Of The Transportation Polytope*

We prove that the combinatorial diameter of the skeleton of the polytope of feasible solutions of any m×n transportation problem is at most 8(m+n−2). * Research for this paper was done while the second and third author were visiting the Isaac Newton Institute for Mathematical Sciences, Cambridge, U.K. All authors were supported by the TMR Network DONET of the European Community ERB TMRXCT98-0202. † Research partially funded by the Dutch BSIK/BRICKS project.