One of our results: let X be a finite set on the plane, 0 < ε < 1, then there exists a set F (a weak ε-net) of size at most 7/ε2 such that every convex set containing at least ε|X| elements of X intersects F. Note that the size of F is independent of the size of X.

Let σ, π be two permutations selected at random from the uniform distribution on the symmetric group Sn. By a result of Dixon [5], the subgroup G generated by σ, π is almost always (i.e. with probability approaching 1 as n → ∞) either Sn or the alternating group An. We prove that the diameter of the Cayley graph of G defined by {σ, π} is almost always not greater than exp ((½ + o(l)). (In n)2).

It is well known that a matroid is a transversal matroid if and only if it is a matching matroid (in the sense that it is the restriction of the matching structure of some graph to a subset of its vertices). A simple proof of that result is now known and in this paper it is used to answer the long-standing question of which transversal matroids are “strict” matching matroids; i.e. actually equal to the matching structure of a graph. We develop a straightforward test of “coloop-surfeit” that can be applied to any transversal matroid, and our main theorem shows that a transversal matroid is a strict matching matroid if and only if it has even rank and coloop-surfeit. Furthermore, the proofs are algorithmic and enable the construction of an appropriate graph from any presentation of a strict matching matroid.

If particles are dropped randomly on a lattice, with a placement being cancelled if the site in question or a nearest neighbor is already occupied, an ensemble of restricted random walks is created. We seek the time dependence of the expected occupation of a given site. It is shown that this problem reduces to one of enumerating walks from the given site in which a move can only be made to a previously occupied site or one of its nearest neighbors.

We study the asymptotic properties of a “uniform” random graph process in which the minimum degree of U(n, M) grows at least as fast as ⌊M/n⌋. We show that if M — n → → ∞, almost surely U(n, M) consists of one giant component and some number of small unicyclic components. We go on to study the distribution of cycles in unicyclic components as they emerge at the beginning of the process and disappear when captured by the giant one.

The smallest minimal degree of an r-partite graph that guarantees the existence of a complete subgraph of order r has been found for the case r = 3 by Bollobás, Erdő and Szemerédi, who also gave bounds for the cases r ≥ 4. In this paper the exact value is established for the cases r = 4 and 5, and the bounds for r ≥ 6 are improved.

For every n consider a subset Hn of the patterns of length n over a fixed finite alphabet. The limit distribution of the waiting time until each element of Hn appears in an infinite sequence of independent, uniformly distributed random letters was determined in an earlier paper. This time we prove that these waiting times are getting independent as n → ∞. Our result is used for applying the converse part of the Borel–Cantelli lemma to problems connected with such waiting times, yielding thus improvements on some known theorems.

We consider a random digraph Din, out(n) on vertices 1, …, n, where, for each vertex v, we choose at random one of the n possible arcs with head v and one of the n possible arcs with tail v. We show that the expected size of the largest component of Din, out is .

Notions of deletion and contraction for the class of set functions from finite sets into the integers are defined. An operation on a subclass of such set functions is a function from the subclass into itself that preserves ground sets and respects isomorphism. The operations on set functions that interchange deletion and contraction are characterised, as are those with the further property of being involutary. Similar results are given for polymatroids. There is a unique involutary operation on the class of k-polymatroids that interchanges deletion and contraction. The results generalise those of Kung [3].