Carnegie Mellon University
Browse

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

History

Publisher Statement

All Rights Reserved

Date

1992-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC