  In 1995 Kim famously proved the Ramsey bound R(3,t) \ge c t^2/\log t by
constructing an n-vertex graph that is triangle-free and has independence
number at most C \sqrt{n \log n}. We extend this celebrated result, which is
best possible up to the value of the constants, by approximately decomposing
the complete graph K_n into a packing of such nearly optimal Ramsey R(3,t)
graphs.
  More precisely, for any \epsilon>0 we find an edge-disjoint collection
(G_i)_i of n-vertex graphs G_i \subseteq K_n such that (a) each G_i is
triangle-free and has independence number at most C_\epsilon \sqrt{n \log n},
and (b) the union of all the G_i contains at least (1-\epsilon)\binom{n}{2}
edges. Our algorithmic proof proceeds by sequentially choosing the graphs G_i
via a semi-random (i.e., Rodl nibble type) variation of the triangle-free
process.
  As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun,
Liebenau, Person, and Szabo (concerning a Ramsey-type parameter introduced by
Burr, Erdos, Lovasz in 1976). Namely, denoting by s_r(H) the smallest minimum
degree of r-Ramsey minimal graphs for H, we close the existing logarithmic gap
for H=K_3 and establish that s_r(K_3) = \Theta(r^2 \log r).

Combinatorics;Discrete Mathematics;Probability