file.pdf (132.66 kB)

Download file# A note on the random greedy triangle-packing algorithm

journal contribution

posted on 2010-01-01, 00:00 authored by Tom Bohman, Alan FriezeAlan Frieze, Eyal LubetzkyThe random greedy algorithm for constructing partial Steiner-Triple-System is defined as follows.We begin with a complete graph on n vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random from the collection of all remaining triangles.This stochastic process terminates once it arrives at a triangle-free graph.In this note we show that with high probability the number of edges in the final graph is at most n^{7/4+o(1)}.