Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

(i)	deg G (x)≤C pn for allx∈V(G),
(ii)	for all 2≤r≤D H and for all distinct verticesx 1, ...,x r ∈V(G),,
(iii)	for all but at mosto(n 2) pairs {x 1,x 2} ⊆V(G),, then the number of labeled copies ofH inG is.

Moreover, we discuss a setting under which an arbitrary graphH (not necessarily triangle-free) can be embedded inG. We also present an embedding result for directed graphs. Research supported by a CNP_q/NSF cooperative grant. Partially supported by MCT/CNP_q through ProNEx Programme (Proc. CNP_q 664107/1997-4) and by CNP_q (Proc. 300334/93-1 and 468516/2000-0). Partially supported by NSF Grant 0071261. Supported by NSF grant CCR-9820931.