On Random Greedy Triangle Packing
On Random Greedy Triangle Packing
The behaviour of the random greedy algorithm for constructing a maximal packing of edge-disjoint triangles on $n$ points (a maximal partial triple system) is analysed with particular emphasis on the final number of unused edges. It is shown that this number is at most $n^{7/4+o(1)}$, "halfway" from the previous best-known …