In this paper we investigate a partitioning problem, setting the existence problem for all group-divisible designs with first and second associates in which the blocks are 4-cycles.

In 1978, Dhar suggested a model of a lattice gas whose states are partial orders. In this context he raised the question of determining the number of partial orders with a fixed number of comparable pairs. Dhar conjectured that in order to find a good approximation to this number, it should suffice to enumerate families of layer posets. In this paper we prove this conjecture and thereby prepare the ground for a complete answer to the question.

Fix a small graph H and let YH denote the number of copies of H in the random graph G(n, p). We investigate the degree of concentration of YH around its mean, motivated by the following questions.

[bull ] What is the upper tail probability Pr(YH [ges ] (1 + ε)[ ](YH))?

[bull ] For which λ does YH have sub-Gaussian behaviour, namely

(formula here)

where c is a positive constant?

[bull ] Fixing λ = ω(1) in advance, find a reasonably small tail T = T(λ) such that

(formula here)

We prove a general concentration result which contains a partial answer to each of these questions. The heart of the proof is a new martingale inequality, due to J. H. Kim and the present author [13].

We use entropy ideas to study hard-core distributions on the independent sets of a finite, regular bipartite graph, specifically distributions according to which each independent set I is chosen with probability proportional to λ[mid ]I[mid ] for some fixed λ > 0. Among the results obtained are rather precise bounds on occupation probabilities; a ‘phase transition’ statement for Hamming cubes; and an exact upper bound on the number of independent sets in an n-regular bipartite graph on a given number of vertices.

We show that connected matroids with symmetric Tutte polynomials are not necessarily self-dual; in fact, we construct matroids that are not self-dual, have arbitrarily high connectivity, and yet have symmetric Tutte polynomials.

We investigate a graph function which is related to the local density, the maximal cut and the least eigenvalue of a graph. In particular it enables us to prove the following assertions.

Let p [ges ] 3 be an integer, c ∈ (0, 1/2) and G be a Kp-free graph on n vertices with e [les ] cn2 edges. There exists a positive constant α = α (c, p) such that:

(a) some [lfloor ]n/2[rfloor ]-subset of V (G) induces at most (c-4 − α) n2 edges (this answers a question of Paul Erdős);

(b) G can be made bipartite by the omission of at most (c-2 − α) n2 edges.

Given an r-graph F, an r-graph G is called weakly F-saturated if the edges missing from G can be added, one at a time, in some order, each extra edge creating a new copy of F. Let w-sat(n, F) be the minimal size of a weakly F-saturated graph of order n. We compute the w-sat function for a wide class of r-graphs called pyramids: these include many examples for which the w-sat function was known, as well as many new examples, such as the computation of w-sat(n,Ks + Kt), and enable us to prove a conjecture of Tuza.

Our main technique, developed from ideas of Kalai, is based on matroids derived from exterior algebra. We prove that if it succeeds for some graphs then the same is true for the ‘cones’ and ‘joins’ of such graphs, so that the w-sat function can be computed for many graphs that are built up from certain elementary graphs by these operations.

For each integer n, there is a natural family of probability distributions on the set of topologies on a set of n elements, parametrized by an integer variable, m. We will describe how these are constructed and analysed, and find threshold functions (for m in terms of n) for various topological properties; we focus attention on connectivity and the size of the largest component.

Let k be a positive integer and let G be a graph. Suppose a list S(v) of positive integers is assigned to each vertex v, such that

(1) [mid ]S(v)[mid ] = 2k for each vertex v of G, and

(2) for each vertex v, and each c ∈ S(v), the number of neighbours w of v for which c ∈ S(w) is at most k.

Then we prove that there exists a proper vertex colouring f of G such that f(v) ∈ S(v) for each v ∈ V(G). This proves a weak version of a conjecture of Reed.

We generalize a minimal 3-connectivity result of Halin from graphs to binary matroids. As applications of this theorem to minimally 3-connected matroids, we obtain new results and short inductive proofs of results of Oxley and Wu. We also give new short inductive proofs of results of Dirac and Halin on minimally k-connected graphs for k ∈ {2,3}.

In this paper, we conclude the construction of all the matroids having circumference at most five. We use this result to prove a conjecture of Hochstättler and Jackson, in a special case.

We consider an extension of the Monotone Subsequence lemma of Erdős and Szekeres in higher dimensions. Let v1,…,vn ∈ ℝd be a sequence of real vectors. For a subset I ⊆ [n] and vector [srarr ]c ∈ {0,1}d we say that I is [srarr ]c-free if there are no i < j ∈ I, such that, for every k = 1,…,d, vik < vik if and only if [srarr ]ck = 0. We construct sequences of vectors with the property that the largest [srarr ]c-free subset is small for every choice of [srarr ]c. In particular, for d = 2 the largest [srarr ]c-free subset is O(n⅝) for all the four possible [srarr ]c. The smallest possible value remains far from being determined.

We also consider and resolve a simpler variant of the problem.

We present a combinatorial lemma that provides a new approach to the two-sided exit problem and related questions for left-continuous random walks (i.e., random walks on the integers whose negative steps have size − 1). Some applications to random walks on the circle are also derived.

Let G be a planar graph without 6-cycles. We investigate structural properties of G and show that G is edge-(Δ(G) + 1)-choosable when its maximum degree Δ(G) is not 5. We also study the 3-degeneracy property of G.

We investigate the following problem of Erdős:

Determine the minimum number of k-cliques in a graph of order n with independence number [ges ] l.

We disprove the original conjecture of Erdős which was stated in 1962 for all but a finite number of pairs k, l, and give asymptotic estimates for l = 3, k [ges ] 4, and l = 4, k [ges ] 4.