Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.