A cladogram is a tree with labelled leaves and unlabelled degree-3 branchpoints. A certain Markov chain on the set of n-leaf cladograms consists of removing a random leaf (and its incident edge) and re-attaching it to a random edge. We show that the mixing time (time to approach the uniform stationary distribution) for this chain is at least O(n2) and at most O(n3).

Answering a question of Wilf, we show that, if n is sufficiently large, then one cannot cover an n × p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only Θ(p(n)/log n):

In this paper, we study a statistical property of classes of real-valued functions that we call approximation from interpolated examples. We derive a characterization of function classes that have this property, in terms of their ‘fat-shattering function’, a notion that has proved useful in computational learning theory. The property is central to a problem of learning real-valued functions from random examples in which we require satisfactory performance from every algorithm that returns a function which approximately interpolates the training examples.

The twisted odd graphs are obtained from the well-known odd graphs through an involutive automorphism. As expected, the twisted odd graphs share some of the interesting properties of the odd graphs but, in general, they seem to have a more involved structure. Here we study some of their basic properties, such as their automorphism group, diameter, and spectrum. They turn out to be examples of the so-called boundary graphs, which are graphs satisfying an extremal property that arises from a bound for the diameter of a graph in terms of its distinct eigenvalues.

Given a graph G = (V, E) and a set of κ pairs of vertices in V, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of κ paths so found is edge-disjoint. (For arbitrary graphs the problem is [Nscr ][Pscr ]-complete, although it is in [Pscr ] if κ is fixed.)

We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph Gn,r, for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every Gn,r is such that all sets of κ = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum.

For any fixed l < k we present families of asymptotically good packings and coverings of the l-subsets of an n-element set by k-subsets, and an algorithm that, given a natural number i, finds the ith k-subset of the family in time and space polynomial in log n.

This paper describes methods for counting the number of nonnegative integer solutions of the system Ax = b when A is a nonnegative totally unimodular matrix and b an integral vector of fixed dimension. The complexity (under a unit cost arithmetic model) is strong in the sense that it depends only on the dimensions of A and not on the size of the entries of b. For the special case of ‘contingency tables’ the run-time is 2O(√dlogd) (where d is the dimension of the polytope). The method is complementary to Barvinok's in that our algorithm is effective on problems of high dimension with a fixed number of (non-sign) constraints, whereas Barvinok's algorithms are effective on problems of low dimension and an arbitrary number of constraints.