We describe two computational methods for the construction of cubic graphs with given girth. These were used to produce two independent proofs that the (3,9)-cages, defined as the smallest cubic graphs of girth 9, have 58 vertices. There are exactly 18 such graphs. We also show that cubic graphs of girth 11 must have at least 106 vertices and cubic graphs of girth 13 must have at least 196 vertices.

We derive identities for the probability that at least a1 and at least a2, and for the probability that exactly a1 and exactly a2, out of n and N events occur (1 ≤ a1 ≤ n, 1 ≤ a2 ≤ N). From this, we produce multivariate permutation hybrid upper bounds, and a multivariate Bonferroni-type upper bound which includes Galambos and Xu's [2] optimal result. The methodology generalizes that of Hoppe and Seneta [3, §5]. A numerical example is given.

Model 1. Consider the complete graph Kn, with vertex set [n] = {1, 2,…, n}, in which each edge e is assigned a length Xe. Colour the k shortest edges incident with each vertex green and the remaining edges blue. The graph made up of the green edges only, will be referred to as the k-th nearest neighbour graph. This graph has been studied in a variety of contexts both computational and statistical.

The main result of this paper has the following consequence. Let G be an abelian group of order n. Let {xi: 1 ≤ 2n − 1} be a family of elements of G and let {wi: 1 ≤ i ≤ n − 1} be a family of integers prime relative to n. Then there is a permutation & of [1,2n − 1] such that

Applying this result with wi = 1 for all i, one obtains the Erdős–Ginzburg–Ziv Theorem.

The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Lévy measure. Similar results are found for some related problems. These limit results imply that some different models of random regular graphs are contiguous, which means that they are qualitatively asymptotically equivalent. For example, if r > 3, then the usual (uniformly distributed) random r-regular graph is contiguous to the one constructed by taking the union of r perfect matchings on the same vertex set (assumed to be of even cardinality), conditioned on there being no multiple edges. Some consequences of contiguity for asymptotic distributions are discussed.

Numerous new properties of stochastic conditional independence are introduced. They are aimed, together with two surprisingly trivial examples, at a further reduction of the problem of probabilistic representability for four-element sets, i.e. of the problem which conditional independences within a system of four random variables can occur simultaneously. Proofs are based on fundamental properties of conditional independence and, in the discrete case, on the use of I-divergence and algebraic manipulations with marginal probabilities. A duality question is answered in the negative.

This paper gives precise isoperimetric inequalities for infinite graphs on which a group acts with finite quotient. Decay estimates are obtained for the iterated kernels of the associated random walks.