Let and be sets of functions from domain X to ℝ. We say that validly generalises from approximate interpolation if and only if for each η > 0 and ∈, δ ∈ (0,1) there is m0(η, ∈, δ) such that for any function t ∈ and any probability distribution on X, if m > m0 then with m-probability at least 1 – δ, a sample X = (x1, X2,…,xm) ∈ Xm satisfies

We find conditions that are necessary and sufficient for to validly generalise from approximate interpolation, and we obtain bounds on the sample length m0{η,∈,δ) in terms of various parameters describing the expressive power of .

We consider unlabelled flowgraphs for a model of binary logic without the constraints of structured programming. The number of such flowgraphs is asymptotic to (3.4n)n/2, where n is the number of nodes in the flowgraph. This is to be compared with bounds of between (8.8)n/2 and of (9.8)n/2 for unlabelled structured flowgraphs of the Böhm and Jacopini type. Of the space of flowgraphs we study, 41% are prime, that is contain no proper sub-flowgraphs. The main obstructions to primality being the Dijkstra-structures, which are based on If_Then_Else and Do_While constructs.

Kuratowski's Theorem, perhaps the most famous result in graph theory, states that K5 and K3,3 are the only non-planar graphs for which both G\e, the deletion of the edge e, and G/e, the contraction of the edge e, are planar for all edges e of G. We characterize the almost-planar graphs, those non-planar graphs for which G\e or G/e is planar for all edges e of G. This paper gives two characterizations of the almost-planar graphs: an explicit description of the structure of almost-planar graphs; and an excluded minor criterion. We also give a best possible bound on the number of edges of an almost-planar graph.

Thinking of a deterministic function s: ℤ → ℕ as ‘scenery’ on the integers, a simple random walk on ℤ generates a random record of scenery ‘observed’ along the walk. We address this question: If t:ℤ → ℕ is another scenery on the integers and we are handed a random scenery record obtained from either s or t, under what circumstances can the source be distinguished? We allow ourselves to use information about s and t together with information contained in the scenery record. It has been conjectured that it is sufficient for t to be neither a translate of s nor a translate of the reflection of s. We show that this condition is sufficient to ensure distinguishability if s−1(δ) is finite and non-empty for some δ ∈ℕ.

Let M be a matroid and let Xr count copies of M in a random matroid of rank r. The Poisson and normal convergence of Xr are investigated under some restriction.

We consider a «Maker-Breaker’ version of the Ramsey Graph Game, RG(n), and present a winning strategy for Maker requiring at most (n − 3)2n−1 + n + 1 moves. This is the fastest winning strategy known so far. We also demonstrate how the ideas presented can be used to develop winning strategies for some related combinatorial games.

A dominating set for a graph G is a set D of vertices of G such that every vertex of G not in D is adjacent to a vertex of D. We prove that any graph G of minimum degree at least three contains a dominating set D of size at most 3|V(G)|/8. A star S is a graph consisting of a centre x and a set of edges from x to S — x. Clearly, a dominating set D for a graph G corresponds to a set of |D| stars which cover V(G). Thus, we show that the vertices of any graph G of minimum degree 3 can be covered by at most 3|V(G)|/8 vertex disjoint stars. We also show that any connected cubic graph G can be covered by [|V(G)|/9] vertex disjoint paths. Both these results are sharp.

Jackson [10] gave a polynomial sufficient condition for a bipartite tournament to contain a cycle of a given length. The question arises as to whether deciding on the maximum length of a cycle in a bipartite tournament is polynomial. The problem was considered by Manoussakis [12] in the slightly more general setting of 2-edge coloured complete graphs: is it polynomial to find a longest alternating cycle in such coloured graphs? In this paper, strong evidence is given that such an algorithm exists. In fact, using a reduction to the well known exact matching problem, we prove that the problem is random polynomial.

This paper deals with infinite binary sequences. Each sequence is treated as generated by a nondeterministic shift register. A measure-theoretic criterion helpful in finding a deterministic generator of the set of sequences is proposed.