file.pdf (1021.2 kB)
Download file

On the size of a random maximamal [sic] graph

Download (1021.2 kB)
journal contribution
posted on 01.01.1992, 00:00 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)."

History

Publisher Statement

All Rights Reserved

Date

01/01/1992

Usage metrics

Exports