Contents Online

# 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

#### 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)} $.