The number of excluded minors for the class of graphs with path-width at most two is very large. To give a practical characterization of the obstructions, we introduce some operations which preserve path-width at most two. We give a list of ten graphs such that any graph with path-width more than two can be reduced – by taking minors and applying our operations – to one of the graphs on our list. We think that our operations and excluded substructures give a far more transparent description of the class of graphs with path-width at most two than Kinnersley and Langston's characterization by 110 excluded minors (see [4]).

Let X1, …, Xn be a sequence of r.v.s produced by a stationary Markov chain with state space an alphabet Ω = {ω1, …, ωq}, q [ges ] 2. We consider a set of words {A1, …, Ar}, r [ges ] 2, with letters from the alphabet Ω. We allow the words to have self-overlaps as well as overlaps between them. Let [Escr ] denote the event of the appearance of a word from the set {A1, …, Ar} at a given position. Moreover, define by N the number of non-overlapping (competing renewal) appearances of [Escr ] in the sequence X1, …, Xn. We derive a bound on the total variation distance between the distribution of N and a Poisson distribution with parameter [ ]N. The Stein–Chen method and combinatorial arguments concerning the structure of words are employed. As a corollary, we obtain an analogous result for the i.i.d. case. Furthermore, we prove that, under quite general conditions, the r.v. N converges in distribution to a Poisson r.v. A numerical example is presented to illustrate the performance of the bound in the Markov case.

A family of subsets of an n-set is k-locally thin if, for every k-tuple of its members, the ground set has at least one element contained in exactly one of them. For k = 5 we derive a new exponential upper bound for the maximum size of these families. This implies the same bound for all odd values of k > 3. Our proof uses the graph entropy bounding technique to exploit a self-similarity in the structure of the hypergraph associated with such set families.

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.

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.

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 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.