file.pdf (1021.2 kB)
On the size of a random maximamal [sic] graph
journal contributionposted on 1992-01-01, 00:00 authored by Erdo╠és, Stephen Suen, P Winkler
Abstract: "Let P be a graph property which is preserved by removal of edges. A random maximal P-graph is obtained from n independent vertices by randomly adding edges, at each stage choosing uniformly among edges whose inclusion would not destroy property P, until no further edges can be added. We address the question of the number of edges of a random maximal P-graph for several properties P, in particular the cases of 'bipartite' and 'triangle-free'. A variety of techniques are used to show that the size of the random maximal bipartite graph is quadratic in n but of order only n[superscript 3/2] in the triangle-free case. Along the way we obtain a slight improvement in the lower bound of the Ramsey number r(3,t)."