Journal of Combinatorics

Volume 1 (2010)

Number 4

A note on the random greedy triangle-packing algorithm

Pages: 477 – 488

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n4.a5

Authors

Tom Bohman (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Alan Frieze (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Eyal Lubetzky (Microsoft Research, Redmond, Wash., U.S.A.)

Abstract

The random greedy algorithm for constructing apartial Steiner-Triple-System is defined as follows.We begin with a complete graph on $n$ vertices and proceed toremove the edges of triangles one at a time, whereeach triangle removed is chosen uniformly at randomfrom 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 ofedges in the final graph is at most $ n^{7/4 +o(1)} $.

Full Text (PDF format)