Let G be a graph with maximum degree Δ(G). In this paper we prove that if the girth g(G) of G is greater than 4 then its chromatic number, χ(G), satisfies

where o(l) goes to zero as Δ(G) goes to infinity. (Our logarithms are base e.) More generally, we prove the same bound for the list-chromatic (or choice) number:

provided g(G) < 4.

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.

Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.

Dowling lattices are a class of geometric lattices, based on groups, which have been shown to share many properties with projective geometries. In this paper we show that the automorphisms of Dowling lattices are analogs of the automorphisms of projective geometries. We also treat similar results for several related geometric lattices.

We derive bounds for eigenvalues of the Laplacian of graphs using discrete versions of the Sobolev inequalities and heat kernel estimates.

We prove the existence of an asymptotic expansion in the inverse dimension, to all orders, for the connective constant for self-avoiding walks on ℤd. For the critical point, defined as the reciprocal of the connective constant, the coefficients of the expansion are computed through order d−6, with a rigorous error bound of order d−7 Our method for computing terms in the expansion also applies to percolation, and for nearest-neighbour independent Bernoulli bond percolation on ℤd gives the 1/d-expansion for the critical point through order d−3, with a rigorous error bound of order d−4 The method uses the lace expansion.

A rule for shuffling an infinite deck of cards is considered where at each time step the first and jth card are interchanged with probability pj. Conditions are given under which this shuffling scheme, considered as a Markov chain on the space of permutations of integers, is recurrent or transient.

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.

We consider a string editing problem in a probabilistic framework. This problem is of considerable interest to many facets of science, most notably molecular biology and computer science. A string editing transforms one string into another by performing a series of weighted edit operations of overall maximum (minimum) cost. The problem is equivalent to finding an optimal path in a weighted grid graph. In this paper we provide several results regarding a typical behaviour of such a path. In particular, we observe that the optimal path (i.e. edit distance) is almost surely (a.s.) equal to αn for large n where α is a constant and n is the sum of lengths of both strings. More importantly, we show that the edit distance is well concentrated around its average value. In the so called independent model in which all weights (in the associated grid graph) are statistically independent, we derive some bounds for the constant α. As a by-product of our results, we also present a precise estimate of the number of alignments between two strings. To prove these findings we use techniques of random walks, diffusion limiting processes, generating functions, and the method of bounded difference.

Robertson and Seymour proved that excluding any fixed forest F as a minorimposes a bound on the path-width of a graph. We give a short proof of this, reobtaining the best possible bound of |F| – 2.

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.

For a graph H and an integer r ≥ 2, the induced r-size-Ramsey number of H is defined to be the smallest integer m for which there exists a graph G with m edges with the following property: however one colours the edges of G with r colours, there always exists a monochromatic induced subgraph H′ of G that is isomorphic to H. This is a concept closely related to the classical r-size-Ramsey number of Erdős, Faudree, Rousseau and Schelp, and to the r-induced Ramsey number, a natural notion that appears in problems and conjectures due to, among others, Graham and Rödl, and Trotter. Here, we prove a result that implies that the induced r-size-Ramsey number of the cycle Cℓ is at most crℓ for some constant cr that depends only upon r. Thus we settle a conjecture of Graham and Rödl, which states that the above holds for the path Pℓ of order ℓ and also generalise in part a result of Bollobás, Burr and Reimer that implies that the r-size Ramsey number of the cycle Cℓ is linear in ℓ Our method of proof is heavily based on techniques from the theory of random graphs and on a variant of the powerful regularity lemma of Szemerédi.

We focus our attention on the class RMAX(2) of NP optimization problems. Owing to recent developments in interactive proof techniques, RMAX(2) was shown to be the lowest class of logical classification that contains problems hard to approximate. Namely, the RMAX(2)-complete problem MAX CLIQUE (of finding the size of the largest clique in a graph) is not approximable in polynomial time within any constant factor unless NP=P.

We are interested in problems inside RMAX(2) that are not known to be complete but are still hard to approximate. We point out that one such problem is MAXlog n, n, considered by Berman and Schnitger: given m conjunctions, each of them consisting of log m propositional variables or their negations, find the maximal number of simultaneously satisfiable conjunctions. We also obtain the approximation hardness results for some other problems in RMAX(2). Finally, we discuss the question of whether or not the problems under consideration are RMAX(2)-complete.

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.

Béla Bollobás [1] conjectured the following. For any positive integer Δ and real 0 < c < ½ there exists an n0 with the following properties. If n ≥ n0, T is a tree of order n and maximum degree Δ, and G is a graph of order n and maximum degree not exceeding cn, then there is a packing of T and G. Here we prove this conjecture. Auxiliary Theorem 2.1 is of independent interest.

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.

For any positive integer m, let Q(m) be the least positive integer k such that ≥ m. We show that for almost all unlabelled, unrooted trees T, h(T) = Q(m), where m is the number of edges of T.

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.

A linear forest is the union of a set of vertex disjoint paths. Akiyama, Exoo and Harary, and independently Hilton, have conjectured that the edges of every graph of maximum degree Δ can be covered by linear forests. We show that almost every graph can be covered with this number of linear forests.

The square lattice site percolation model critical probability is shown to be at most .679492, improving the best previous mathematically rigorous upper bound. This bound is derived by extending the substitution method to apply to site percolation models.

We consider the performance of a simple greedy matching algorithm MINGREEDY when applied to random cubic graphs. We show that if λn is the expected number of vertices not matched by MINGREEDY, there are positive constants c1 and c2 such that C1n1/5 ≤ λn ≤ C2n1/5 log n.