We consider graphs Gn generated by multisets [Iscr ]n with n random integers as elements, such that vertices of Gn are connected by edges if the elements of [Iscr ]n that the vertices represent are the same, and prove asymptotic results on the sparsity of edges connecting the different subgraphs Gn of the random graph generated by ∪∞n=1[Iscr ]n. These results are of independent interest and, for two models of the bootstrap, we also use them here to link almost sure and complete convergence of the corresponding bootstrap means and averages of related randomly chosen subsequences of a sequence of independent and identically distributed random variables with a finite mean. Complete convergence of these means and averages is then characterized in terms of a relationship between a moment condition on the bootstrapped sequence and the bootstrap sample size. While we also obtain new sufficient conditions for the almost sure convergence of bootstrap means, the approach taken here yields the first necessary conditions.

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.

We compare the Euclidean operator norm of a random matrix with the Euclidean norm of its rows and columns. In the first part of this paper, we show that if A is a random matrix with i.i.d. zero mean entries, then E∥A∥h [les ] Kh (E maxi ∥ai[bull ] ∥h + E maxj ∥aj[bull ] ∥h), where K is a constant which does not depend on the dimensions or distribution of A (h, however, does depend on the dimensions). In the second part we drop the assumption that the entries of A are i.i.d. We therefore consider the Euclidean operator norm of a random matrix, A, obtained from a (non-random) matrix by randomizing the signs of the matrix's entries. We show that in this case, the best inequality possible (up to a multiplicative constant) is E∥A∥h [les ] (c log1/4 min {m, n})h (E maxi ∥ai[bull ] ∥h + E maxj ∥aj[bull ] ∥h) (m, n the dimensions of the matrix and c a constant independent of m, n).

An asymptotics, as n → ∞, for the expected number of distinct part sizes in a random composition of an integer n is obtained.

In this paper, we combine two previous works, the first being by the first author and K. Nelander, and the second by J. van den Berg and the second author, to show (1) that one can carry out a Propp–Wilson exact simulation for all Markov random fields on ℤd satisfying a certain high noise assumption, and (2) that all such random fields are a finitary image of a finite state i.i.d. process. (2) is a strengthening of the previously known fact that such random fields are so-called Bernoulli shifts.

Let A be an m × n matrix and q := [lfloor ]log2(m)[rfloor ]+1. In this article we improve the well-known bound lindisc(A) [les ] 2 herdisc(A) and show that

formula here

As with the previous proofs relating to this problem, ours is constructive. We will give an on-line algorithm and analyse it using game theory.

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 a finite multigraph G, the reliability function of G is the probability RG(q) that if each edge of G is deleted independently with probability q then the remaining edges of G induce a connected spanning subgraph of G; this is a polynomial function of q. In 1992, Brown and Colbourn conjectured that, for any connected multigraph G, if q ∈ [Copf ] is such that RG(q) = 0 then [mid ]q[mid ] [les ] 1. We verify that this conjectured property of RG(q) holds if G is a series-parallel network. The proof is by an application of the Hermite–Biehler theorem and development of a theory of higher-order interlacing for polynomials with only real nonpositive zeros. We conclude by establishing some new inequalities which are satisfied by the f-vector of any matroid without coloops, and by discussing some stronger inequalities which would follow (in the cographic case) from the Brown–Colbourn conjecture, and are hence true for cographic matroids of series-parallel networks.

A type of evolution of graphs with maximum vertex degree at most d is introduced. This evolution can start from any initial graph whose set of vertices of degree less than d is independent. The main concern is the regularity of graphs generated by this graph process when the initial graph has no edges. By analysis of the solutions of systems of differential equations it is shown that the final graph of this evolution is asymptotically almost surely a d-regular graph (subject to the usual parity condition).

Consider sequences {Xi}mi=1 and {Yj}nj=1 of independent random variables, taking values in a finite alphabet, and assume that the variables X1, X2, … and Y1, Y2, … follow the distributions μ and v, respectively. Two variables Xi and Yj are said to match if Xi = Yj. Let the number of matching subsequences of length k between the two sequences, when r, 0 [les ] r < k, mismatches are allowed, be denoted by W.

In this paper we use Stein's method to bound the total variation distance between the distribution of W and a suitably chosen compound Poisson distribution. To derive rates of convergence, the case where E[W] stays bounded away from infinity, and the case where E[W] → ∞ as m, n → ∞, have to be treated separately. Under the assumption that ln n/ln(mn) → ρ ∈ (0, 1), we give conditions on the rate at which k → ∞, and on the distributions μ and v, for which the variation distance tends to zero.

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k [ges ] 3. The best known polynomial time approximation algorithms require nδ (for a positive constant δ depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be k-coloured almost surely in polynomial time.

In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into k colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) [ges ] n−1+ε where ε is a constant greater than 1/4.

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.

In [9, p. 469], Oxley made the following conjecture, which is a geometric analogue of a conjecture of Lovász (see [1, p. 290]) about complete graphs.

Conjecture 1.1.Let G be a rank-n GF(q)-representable simple matroid with critical exponent n − γ. If, for every coline X in G, c(G/X; q) = c(G; q) − 2 = n − γ − 2, then G is the projective geometry PG(n − 1, q).

We shall call the rank n, the critical ‘co-exponent’ γ, and the order q of the field the parameters of Oxley's conjecture. We exhibit several counterexamples to this conjecture. These examples show that, for a given prime power q and a given positive integer γ, Oxley's conjecture holds for only finitely many ranks n. We shall assume familiarity with matroid theory and, in particular, the theory of critical problems. See [6] and [9].

A subset C of points of PG(n − 1, q) is a (γ, k)-cordon if, for every k-codimensional subspace X in PG(n − 1, q), the intersection C ∩ X contains a γ-dimensional subspace of PG(n − 1, q). In this paper, our primary interest will be in constructing (γ, 2)-cordons. With straightforward modifications, our methods will also yield (γ, k)-cordons.

Complements of counterexamples to Oxley's conjecture are (γ, 2)-cordons.

The intersection exponent ξ for simple random walk in two and three dimensions gives a measure of the rate of decay of the probability that paths do not intersect. In this paper we show that the intersection exponent for random walks is the same as that for Brownian motion and show in fact that the probability of nonintersection up to distance n is comparable (equal up to multiplicative constants) to n−ξ.

Let 0 < p < 1, q = 1 − p and b be fixed and let G ∈ [Gscr ](n, p) be a graph on n vertices where each pair of vertices is joined independently with probability p. We show that the probability that every vertex of G has degree at most pn + b √npq is equal to (c + o(1))n, for c = c(b) the root of a certain equation. Surprisingly, c(0) = 0.6102 … is greater than ½ and c(b) is independent of p. To obtain these results we consider the complete graph on n vertices with weights on the edges. Taking these weights as independent normal N(p, pq) random variables gives a ‘continuous’ approximation to [Gscr ](n, p) whose degrees are much easier to analyse.

We generalize the notion of choice number from graphs to hypergraphs and estimate the sharp order of magnitude of the choice number of random hypergraphs. It turns out that the choice number and the chromatic number of a random hypergraph have the same order of magnitude, almost surely. Our result implies an earlier bound on the chromatic number of random hypergraphs, proved by Schmidt [23] using a different method.

A graph G is quasi 4-connected if it is simple, 3-connected, has at least five vertices, and for every partition (A, B, C) of V(G) either [mid ]C[mid ] [ges ] 4, or G has an edge with one end in A and the other end in B, or one of A,B has at most one vertex. We show that any quasi 4-connected nonplanar graph with minimum degree at least three and no cycle of length less than five has a minor isomorphic to P−10, the Petersen graph with one edge deleted. We deduce the following weakening of Tutte's Four Flow Conjecture: every 2-edge-connected graph with no minor isomorphic to P−10 has a nowhere-zero 4-flow. This extends a result of Kilakos and Shepherd who proved the same for 3-regular graphs.

This paper gives a general expression for the Tutte polynomial of perfect matroid designs, that is, for matroids in which all ats of the same rank are equicardinal. In particular, explicit expressions are given for the Tutte polynomial of projective and affine geometries over a finite field.

We derive improved isoperimetric inequalities for discrete product measures on the n-dimensional cube. As a consequence, a general theorem on the threshold behaviour of monotone properties is obtained. This is then applied to coding theory when we study the probability of error after decoding.

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.