Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue μ of any non-bipartite graph on n vertices with diameter D and maximum degree Δ satisfies μ [ges ] −Δ + 1/(D+1)n. This improves previous estimates and is tight up to a constant factor. The second result is the determination of the precise approximation guarantee of the MAX CUT algorithm of Goemans and Williamson for graphs G = (V, E) in which the size of the max cut is at least A[mid ]E[mid ], for all A between 0.845 and 1. This extends a result of Karloff.

The maximum expected length of an increasing subsequence which can be selected by a non-anticipating policy from a random permutation of 1, …, n is known to be asymptotic to √2n. We give a new proof of this fact and demonstrate a policy which achieves this value.

We prove that if the edge probability p(n) satisfies n−1/4+ε [les ] p(n) [les ] 3/4, where 0 < ε < 1/4 is a constant, then the choice number and the chromatic number of the random graph G(n, p) are almost surely asymptotically equal.

We prove the following conjecture of J. van den Berg and H. Kesten. For any events [Ascr ] and [Bscr ] in a product probability space, Prob([Ascr ]□[Bscr ]) [les ] Prob([Ascr ])Prob([Bscr ]), where [Ascr ]□[Bscr ] is the event that [Ascr ] and [Bscr ] occur ‘disjointly’.

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).

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.

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.