Carnegie Mellon University
file.pdf (1021.2 kB)

On the size of a random maximamal [sic] graph

Download (1021.2 kB)
journal contribution
posted on 1992-01-01, 00:00 authored by Erdô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)."


Publisher Statement

All Rights Reserved



Usage metrics