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.

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.

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.

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.

We define and efficiently compute the canonical flow on a graph, which is a certain feasible solution for the concurrent flow problem and exhibits invariance under the action of the automorphism group of the graph. Using estimates for the congestion of our canonical flow, we derive lower bounds on the crossing number, bisection width, and the edge and vertex expansion of a graph in terms of sizes of the edge and vertex orbits and the average distance in the graph. We further exhibit classes of graphs for which our lower bounds are tight within a multiplicative constant. Also, in cartesian product graphs a concurrent flow is constructed in terms of the concurrent flows in the factors, and in this way lower bounds for the edge and vertex expansion of the power graphs are derived in terms of that of the original graph.

We introduce five probability models for random topological graph theory. For two of these models (I and II), the sample space consists of all labeled orientable 2-cell imbeddings of a fixed connected graph, and the interest centers upon the genus random variable. Exact results are presented for the expected value of this random variable for small-order complete graphs, for closed-end ladders, and for cobblestone paths. The expected genus of the complete graph is asymptotic to the maximum genus. For Model III, the sample space consists of all labeled 2-cell imbeddings (possibly nonorientable) of a fixed connected graph, and for Model IV the sample space consists of all such imbeddings with a rotation scheme also fixed. The event of interest is that the ambient surface is orientable. In both these models the complete graph is almost never orientably imbedded. The probability distribution in Models I and III is uniform; in Models II and IV it depends on a parameter p and is uniform precisely when p = 1/2. Model V combines the features of Models II and IV.