We present versions of concentration inequalities for products of Markov kernels and graph products. We also present discussions of a variety of consequences such as sharp upper bounds, in terms of the diameter of the state space, on the spectral gap.

Simulated annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of simulated annealing to the 3-colouring problem is considered. In contrast to many good empirical results we will show for a certain class of graphs that the expected first hitting time of a proper colouring, given an arbitrary cooling scheme, is of exponential size.

These results are complementary to those in [13], where we prove the convergence of simulated annealing to an optimal solution in exponential time.

We show that there exist universal constants C(r) < ∞ such that, for all loopless graphs G of maximum degree [les ] r, the zeros (real or complex) of the chromatic polynomial PG(q) lie in the disc [mid ]q[mid ] < C(r). Furthermore, C(r) [les ] 7.963907r. This result is a corollary of a more general result on the zeros of the Potts-model partition function ZG(q, {ve}) in the complex antiferromagnetic regime [mid ]1 + ve[mid ] [les ] 1. The proof is based on a transformation of the Whitney–Tutte–Fortuin–Kasteleyn representation of ZG(q, {ve}) to a polymer gas, followed by verification of the Dobrushin–Kotecký–Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree [les ] r, the zeros of PG(q) lie in the disc [mid ]q[mid ] < C(r) + 1. Along the way, I give a simple proof of a generalized (multivariate) Brown–Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.

Fix a small graph H and let YH denote the number of copies of H in the random graph G(n, p). We investigate the degree of concentration of YH around its mean, motivated by the following questions.

[bull ] What is the upper tail probability Pr(YH [ges ] (1 + ε)[ ](YH))?

[bull ] For which λ does YH have sub-Gaussian behaviour, namely

(formula here)

where c is a positive constant?

[bull ] Fixing λ = ω(1) in advance, find a reasonably small tail T = T(λ) such that

(formula here)

We prove a general concentration result which contains a partial answer to each of these questions. The heart of the proof is a new martingale inequality, due to J. H. Kim and the present author [13].