On random greedy triangle packing (Q1378500)

Summary: 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 upper bound \(o(n^2)\) to the conjectured value \(n^{3/2+o(1)}\). The more general problem of random greedy packing in hypergraphs is also considered.