On triangle-free random graphs

We show that for every k greater than or equal to 1 and delta > 0 there exi sts a constant c > 0 such that, with probability tending to 1 as n --> infi nity, a graph chosen uniformly at random among all triangle-free graphs wit h n vertices and M greater than or equal to cn(3/2) edges can be made bipar tite by deleting [delta M] edges. As an immediate consequence of this fact we infer that if M/n(3/2)-->infinity but M/n(2)-->0, then the probability t hat a random graph G(n, M) contains no triangles decreases as 2(-(1+0(1))M) . We also discuss possible generalizations of the above results. (C) 2000 J ohn Wiley & Sons, Inc.