We consider special types of mod-λ flows, called odd and even mod-λ flows, for directed graphs, and prove that the numbers of such flows can be interpolated by polynomials in λ with the degree given by the cycle rank of the graph. The proofs involve computation of the number of integer solutions in a polyhedral region of Euclidean space using theorems due to Ehrhart. The resulting reciprocity properties of the interpolating polynomials for even flows are considered. The analogous properties of odd and even mod-λ potential differences and their associated potentials are also developed.

A polynomial-time randomised algorithm for uniformly generating forests in a dense graph is presented. Using this, a fully polynomial randomised approximation scheme (fpras) for counting the number of forests in a dense graph is created.

In [1] we introduced and studied for product hypergraphs where ℋi = (i,ℰi), the minimal size π(ℋn) of a partition of into sets that are elements of . The main result was that

if the ℋis are graphs with all loops included. A key step in the proof concerns the special case of complete graphs. Here we show that (1) also holds when the ℋi are complete d-uniform hypergraphs with all loops included, subject to a condition on the sizes of the i. We also present an upper bound on packing numbers.

In [11] it is shown that the theory of almost all graphs is first-order complete. Furthermore, in [3] a collection of first-order axioms are given from which any first-order property or its negation can be deduced. Here we show that almost all Steinhaus graphs satisfy the axioms of almost all graphs and conclude that a first-order property is true for almost all graphs if and only if it is true for almost all Steinhaus graphs. We also show that certain classes of subgraphs of vertex transitive graphs are first-order complete. Finally, we give a new class of higher-order axioms from which it follows that large subgraphs of specified type exist in almost all graphs.

There is a close relationship between biased graph games and random graph processes. In this paper, we develop the analogy and give further interesting instances.

Paul Erdős has conjectured that Menger's theorem extends to infinite graphs in the following way: whenever A, B are two sets of vertices in an infinite graph, there exist a set of disjoint A−B paths and an A−B separator in this graph such that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

We show that the random insertion method for the traveling salesman problem (TSP) may produce a tour Ω(log log n/log log log n) times longer than the optimal tour. The lower bound holds even in the Euclidean Plane. This is in contrast to the fact that the random insertion method performs extremely well in practice. In passing, we show that other insertion methods may produce tours Ω(log n/log log n) times longer than the optimal one. No non-constant lower bounds were previously known.

An [n, k, r]-hypergraph is a hypergraph = (V, E) whose vertex set V is partitioned into n k-element sets V1, V2,…, Vn and for which, for each choice of r indices, 1 ≤ i1 < i2 < … < ir ≤ n, there is exactly one edge e ∈ E such that |e∩Vi| = 1 if i ∈ {i1, i2.…, ir} and otherwise |e ∩ Vi| = 0. An independent transversal of an [n, k, r]-hypergraph is a set T = {a1, a2,…, an} ⊆ V such that ai ∈ Vi for i = 1, 2, …, n and e ⊈ T for all e ∈ E. The purpose of this note is to estimate fr(k), defined as the largest n for which any [n, k, r]-hypergraph has an independent transversal. The sharpest results are for r = 2 and for the case when k is small compared to r.

Let f be a de Morgan read-once function of n variables. Let fε be the random restriction obtained by independently assigning to each variable of f, the value 0 with probability (1 -ε)/2, the value 1 with the same probability, and leaving it unassigned with probability ε. We show that fε depends, on the average, on only O(εαn + εn1/α) variables, where . This result is asymptotically the tightest possible. It improves a similar result obtained recently by Håstad, Razborov and Yao.

We consider the oriented binary tree and the oriented hypercube. The tree edges are oriented from the root to the leaves, while the orientation of the cube edges is induced by the direction from 0 to 1 in the coordinatewise form. The problem is to embed such a tree with l levels into the oriented n-cube as an oriented subgraph, for minimal possible n. A new approach to such problems is presented, which improves the known upper bound n/l ≤ 3/2 given by Havel [1] to n/l ≤ 4/3 + o(1) as l → ∞.

In this paper we solve the following problem on the lattice graph L(m1,…,mn) and the Hamming graph H(m1,…,mn), generalizing a result of Felzenbaum-Holzman-Kleitman on the n-dimensional cube (all mi = 2): Characterize the vectors (s1.…,sn) such that there exists a maximum matching in L, respectively, H with exactly si edges in the ith direction.

Let the Kp-independence number αp (G) of a graph G be the maximum order of an induced subgraph in G that contains no Kp. (So K2-independence number is just the maximum size of an independent set.) For given integers r, p, m > 0 and graphs L1,…,Lr, we define the corresponding Turán-Ramsey function RTp(n, L1,…,Lr, m) to be the maximum number of edges in a graph Gn of order n such that αp(Gn) ≤ m and there is an edge-colouring of G with r colours such that the jth colour class contains no copy of Lj, for j = 1,…, r. In this continuation of [11] and [12], we will investigate the problem where, instead of α(Gn) = o(n), we assume (for some fixed p > 2) the stronger condition that αp(Gn) = o(n). The first part of the paper contains multicoloured Turán-Ramsey theorems for graphs Gn of order n with small Kp-independence number αp(Gn). Some structure theorems are given for the case αp(Gn) = o(n), showing that there are graphs with fairly simple structure that are within o(n2) of the extremal size; the structure is described in terms of the edge densities between certain sets of vertices.

The second part of the paper is devoted to the case r = 1, i.e., to the problem of determining the asymptotic value of

for p < q. Several results are proved, and some other problems and conjectures are stated.

The Erdős-Turán law gives a normal approximation for the order of a randomly chosen permutation of n objects. In this paper, we provide a sharp error estimate for the approximation, showing that, if the mean of the approximating normal distribution is slightly adjusted, the error is of order log−1/2n.

Whereas the cylindrical version of an Eden cluster in the plane has a surface roughness with a fractal dimension predicted by theory, the central version has hitherto seemed to conflict with theory. However, a fresh way of analysing computer simulations of the central version shows that this anomaly is more apparent than real, and the central version can thereby be reconciled with theory. As a by-product, we obtain statistical data on the properties of the central version in the plane. The macroscopic shape of a central cluster is not circular, and microscopic roughness depends weakly upon the angular direction of portions of the surface. Rather surprisingly, the edge method of construction gives a more nearly circular shape than the external and internal methods. For higher dimensions than the plane, the corresponding treatment is more difficult, and there the situation remains obscure. Higher dimensions and certain other clusters (e.g. Richardson clusters) are treated briefly in Section 6. The theory of surface roughness uses a spatial generalization of martingales, called a serial harness: this is also described in Section 6.

We prove that almost every r-regular digraph is Hamiltonian for all fixed r ≥ 3.

A lattice basis bi,…,bm is called block reduced with block size β if for every β consecutive vectors bi,…,bi+β−1, the orthogonal projections of bi,…,bi+β−1 in span(bi,…,bi−1)⊥ are reduced in the sense of Hermite and Korkin–Zolotarev. Let λi denote the successive minima of lattice L, and let b1,…,bm be a basis of L that is block reduced with block size β. We prove that for i = 1,…, m

where γβ is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that

where the maximum is taken over all block reduced bases of all lattices L. We present critical block reduced bases achieving this maximum. Using block reduced bases, we improve Babai's construction of a nearby lattice point. Given a block reduced basis with block size β of the lattice L, and given a point x in the span of L, a lattice point υ can be found in time βO(β) satisfying

These results also give improvements on the method of solving integer programming problems via basis reduction.

Long regressive sequences in well-quasi-ordered sets contain ascendingsubsequences of length n. The complexity of the corresponding function H(n) is studied in the Grzegorczyk-Wainer hierarchy. An extension to regressive canonical colourings is indicated.

An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. Thomassen has conjectured that a countable graph is bounded if and only if its edges can be oriented, possibly both ways, so that every vertex has finite out-degree and every ray has a forward oriented tail. We present a counterexample to this conjecture.

A graph G is threshold if there exists a ‘weight’ function w: V(G) → R such that the total weight of any stable set of G is less than the total weight of any non-stable set of G. Let n denote the set of threshold graphs with n vertices. A graph is called n-universal if it contains every threshold graph with n vertices as an induced subgraph. n-universal threshold graphs are of special interest, since they are precisely those n-universal graphs that do not contain any non-threshold induced subgraph.

In this paper we shall study minimumn-universal (threshold) graphs, i.e.n-universal (threshold) graphs having the minimum number of vertices.

It is shown that for any n ≥ 3 there exist minimum n-universal graphs, which are themselves threshold, and others which are not.

Two extremal minimum n-universal graphs having respectively the minimum and the maximum number of edges are described, it is proved that they are unique, and that they are threshold graphs.

The set of all minimum n-universal threshold graphs is then described constructively; it is shown that it forms a lattice isomorphic to the n − 1 dimensional Boolean cube, and that the minimum and the maximum elements of this lattice are the two extremal graphs introduced above.

The proofs provide a (polynomial) recursive procedure that determines for any threshold graph G with n vertices and for any minimum n-universal threshold graph T, an induced subgraph G' of T isomorphic to G.