Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.

We prove the existence of an asymptotic expansion in the inverse dimension, to all orders, for the connective constant for self-avoiding walks on ℤd. For the critical point, defined as the reciprocal of the connective constant, the coefficients of the expansion are computed through order d−6, with a rigorous error bound of order d−7 Our method for computing terms in the expansion also applies to percolation, and for nearest-neighbour independent Bernoulli bond percolation on ℤd gives the 1/d-expansion for the critical point through order d−3, with a rigorous error bound of order d−4 The method uses the lace expansion.

For a graph H and an integer r ≥ 2, the induced r-size-Ramsey number of H is defined to be the smallest integer m for which there exists a graph G with m edges with the following property: however one colours the edges of G with r colours, there always exists a monochromatic induced subgraph H′ of G that is isomorphic to H. This is a concept closely related to the classical r-size-Ramsey number of Erdős, Faudree, Rousseau and Schelp, and to the r-induced Ramsey number, a natural notion that appears in problems and conjectures due to, among others, Graham and Rödl, and Trotter. Here, we prove a result that implies that the induced r-size-Ramsey number of the cycle Cℓ is at most crℓ for some constant cr that depends only upon r. Thus we settle a conjecture of Graham and Rödl, which states that the above holds for the path Pℓ of order ℓ and also generalise in part a result of Bollobás, Burr and Reimer that implies that the r-size Ramsey number of the cycle Cℓ is linear in ℓ Our method of proof is heavily based on techniques from the theory of random graphs and on a variant of the powerful regularity lemma of Szemerédi.

Béla Bollobás [1] conjectured the following. For any positive integer Δ and real 0 < c < ½ there exists an n0 with the following properties. If n ≥ n0, T is a tree of order n and maximum degree Δ, and G is a graph of order n and maximum degree not exceeding cn, then there is a packing of T and G. Here we prove this conjecture. Auxiliary Theorem 2.1 is of independent interest.

A linear forest is the union of a set of vertex disjoint paths. Akiyama, Exoo and Harary, and independently Hilton, have conjectured that the edges of every graph of maximum degree Δ can be covered by linear forests. We show that almost every graph can be covered with this number of linear forests.

The conditional independences within a system of four discrete random variables are studied simultaneously. The problem of where independences can occur at the same time, called the problem of probabilistic representability, is attacked by an analysis of cones of polymatroids. New results on the cone of all polymatroids satisfying Ingleton inequalities imply a substantial reduction of the problem and an explicit description of the remaining open cases.†

Suppose X1, X2,… is a sequence of independent and identically distributed random elements whose values are taken in a finite set S of size |S| ≥ 2 with probability distribution ℙ(X = s) = p(s) > 0 for s ∈ S. Pevzner has conjectured that for every probability distribution ℙ there exists an N > 0 such that for every word A with letters in S whose length is at least N, there exists a second word B of the same length as A, such that the event that B appears before A in the sequence X1, X2,… has greater probability than that of A appearing before B. In this paper it is shown that a distribution ℙ satisfies Pevzner's conclusion if and only if the maximum value of ℙ, p, and the secondary maximum c satisfy the inequality . For |S| = 2 or |S| = 3, the inequality is true and the conjecture holds. If , then the conjecture is true when A is not allowed to consist of pure repetitions of that unique element for which the distribution takes on its mode.

This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2). Here the diameter refers to the maximum distance from a vertex υ to a vertex w where (υ, w) is from the transitive closure of G – which is also the transitive closure of G ∪ S. This result provides support for the author's previous conjecture that such a set S achieving a diameter polylogarithmic in the number of vertices exists for any digraph. The result also adresses an open question of Chazelle, who did some related work on trees, and suggested the generalization to the planar cases.